JournalTOCs

Journal of Global Optimization

[7 followers] Follow
Full-text available via subscription

Subscription journal
ISSN (Print) 1573-2916 - ISSN (Online) 0925-5001
Published by Springer-Verlag

[2216 journals]

Higher-order optimality conditions for proper efficiency in nonsmooth vector optimization using radial sets and radial derivatives
- Abstract: Abstract We establish both necessary and sufficient optimality conditions of higher orders for various kinds of proper solutions to nonsmooth vector optimization in terms of higher-order radial sets and radial derivatives. These conditions are for global solutions and do not require continuity and convexity assumptions. Examples are provided to show advantages of the results over existing ones in a number of cases.
  PubDate: 2013-05-18
Equilibrium problems involving the Lorentz cone
- Abstract: Abstract We study a general equilibrium model formulated as a smooth system of equations coupled with complementarity conditions relative to the $n$ -dimensional Lorentz cone. For the purpose of analysis, as well as for the design of algorithms, we exploit the fact that the Lorentz cone is representable as a cone of squares in a suitable Euclidean Jordan algebra.
  PubDate: 2013-05-16
Speeding up branch and bound algorithms for solving the maximum clique problem
- Abstract: Abstract In this paper we consider two branch and bound algorithms for the maximum clique problem which demonstrate the best performance on DIMACS instances among the existing methods. These algorithms are MCS algorithm by Tomita et al. (2010) and MAXSAT algorithm by Li and Quan (2010a, b). We suggest a general approach which allows us to speed up considerably these branch and bound algorithms on hard instances. The idea is to apply a powerful heuristic for obtaining an initial solution of high quality. This solution is then used to prune branches in the main branch and bound algorithm. For this purpose we apply ILS heuristic by Andrade et al. (J Heuristics 18(4):525–547, 2012). The best results are obtained for p_hat1000-3 instance and gen instances with up to 11,000 times speedup.
  PubDate: 2013-05-16
Carbon tax based on the emission factor: a bilevel programming approach
- Abstract: Abstract We present a bilevel programming approach to design an effective carbon tax scheme based on the production emission factor, used as an intensity measure, for a competitive market with multiple players. At the upper level, the government sets a target emission factor for the industry and taxes firms if they exceed that target. At the lower level, the industry sets output levels that maximize social welfare. The bilevel model is transformed to a linear MIP by replacing the lower level optimization problem by its KKT conditions, and linearizing the complementarity slackness conditions. We test the model in the context of the cement industry. The results show that the proposed model finds the optimal tax rate that induces firms to switch to less carbon-intensive fuels and reduces the overall emissions.
  PubDate: 2013-05-10
Enhancing computations of nondominated solutions in MOLFP via reference points
- Abstract: Abstract In previous work, Costa and Alves (J Math Sci 161:(6)820–831, 2009; 2011) have presented Branch & Bound and Branch & Cut techniques that allow for the effective computation of nondominated solutions, associated with reference points, of multi-objective linear fractional programming (MOLFP) problems of medium dimensions (ten objective functions, hundreds of variables and constraints). In this paper we present some results that enhance those computations. Firstly, it is proved that the use of a special kind of achievement scalarizing function guarantees that the computation error does not depend on the dimension of the problem. Secondly, a new cut for the Branch & Cut technique is presented. The proof that this new cut is better than the one in Costa and Alves (2011) is presented, guaranteeing that it reduces the region to explore. Some computational tests to assess the impact of the new cut on the performance of the Branch & Cut technique are presented.
  PubDate: 2013-05-08
Vector quasi-equilibrium problems: separation, saddle points and error bounds for the solution set
- Abstract: Abstract In this paper, we employ the image space analysis (for short, ISA) to investigate vector quasi-equilibrium problems (for short, VQEPs) with a variable ordering relation, the constrained condition of which also consists of a variable ordering relation. The quasi relatively weak VQEP (for short, qr-weak VQEP) are defined by introducing the notion of the quasi relative interior. Linear separation for VQEP (res., qr-weak VQEP) is characterized by utilizing the quasi interior of a regularization of the image and the saddle points of generalized Lagrangian functions. Lagrangian type optimality conditions for VQEP (res., qr-weak VQEP) are then presented. Gap functions for VQEP (res., qr-weak VQEP) are also provided and moreover, it is shown that an error bound holds for the solution set of VQEP (res., qr-weak VQEP) with respect to the gap function under strong monotonicity.
  PubDate: 2013-05-01
Antiplane shear deformation of piezoelectric bodies in contact with a conductive support
- Abstract: Abstract We consider a mathematical model which describes the frictional contact between a piezoelectric body and an electrically conductive support. We model the material’s behavior with an electro-elastic constitutive law; the frictional contact is described with a boundary condition involving Clarke’s generalized gradient and the electrical condition on the contact surface is modelled using the subdifferential of a proper, convex and lower semicontinuous function. We derive a variational formulation of the model and then, using a fixed point theorem for set valued mappings, we prove the existence of at least one weak solution. Finally, the uniqueness of the solution is discussed; the investigation is based on arguments in the theory of variational-hemivariational inequalities.
  PubDate: 2013-05-01
An extension of the proximal point algorithm with Bregman distances on Hadamard manifolds
- Abstract: Abstract In this paper we present an extension of the proximal point algorithm with Bregman distances to solve constrained minimization problems with quasiconvex and convex objective function on Hadamard manifolds. The proposed algorithm is a modified and extended version of the one presented in Papa Quiroz and Oliveira (J Convex Anal 16(1): 49–69, 2009). An advantage of the proposed algorithm, for the nonconvex case, is that in each iteration the algorithm only needs to find a stationary point of the proximal function and not a global minimum. For that reason, from the computational point of view, the proposed algorithm is more practical than the earlier proximal method. Another advantage, for the convex case, is that using minimal condition on the problem data as well as on the proximal parameters we get the same convergence results of the Euclidean proximal algorithm using Bregman distances.
  PubDate: 2013-05-01
Weak and strong convergence theorems for asymptotically pseudo-contraction mappings in the intermediate sense in Hilbert spaces
- Abstract: Abstract In this paper, we prove both weak and strong convergence theorems for finding a common element of the solution set for a generalized equilibrium problem, the fixed point set of an asymptotically k-strict pseudo-contraction mapping in the intermediate sense, and the solution set of the variational inequality for a monotone and Lipschitz-continuous mapping by using a new hybrid extragradient method. Our results generalize and improve related results in the literatures.
  PubDate: 2013-05-01
Portfolio selection under model uncertainty: a penalized moment-based optimization approach
- Abstract: Abstract We present a new approach that enables investors to seek a reasonably robust policy for portfolio selection in the presence of rare but high-impact realization of moment uncertainty. In practice, portfolio managers face difficulty in seeking a balance between relying on their knowledge of a reference financial model and taking into account possible ambiguity of the model. Based on the concept of Distributionally Robust Optimization (DRO), we introduce a new penalty framework that provides investors flexibility to define prior reference models using the distributional information of the first two moments and accounts for model ambiguity in terms of extreme moment uncertainty. We show that in our approach a globally-optimal portfolio can in general be obtained in a computationally tractable manner. We also show that for a wide range of specifications our proposed model can be recast as semidefinite programs. Computational experiments show that our penalized moment-based approach outperforms classical DRO approaches in terms of both average and downside-risk performance using historical data.
  PubDate: 2013-05-01
From approximate balls to approximate ellipses
- Abstract: Abstract A ball spans a set of n points when none of the points lie outside it. In Zarrabi-Zadeh and Chan (Proceedings of the 18th Canadian conference on computational geometry (CCCG’06), pp 139–142, 2006) proposed an algorithm to compute an approximate spanning ball in the streaming model of computation, and showed that the radius of the approximate ball is within 3/2 of the minimum. Spurred by this, in this paper we consider the 2-dimensional extension of this result: computation of spanning ellipses. The ball algorithm is simple to the point of being trivial, but the extension of the algorithm to ellipses is non-trivial. Surprisingly, the area of the approximate ellipse computed by this approach is not within a constant factor of the minimum and we provide an elegant proof of this. We have implemented this algorithm, and experiments with a variety of inputs, except for a very pathological one, show that it can nevertheless serve as a good heuristic for computing an approximate ellipse.
  PubDate: 2013-05-01
A supplement to a regularization method for the proximal point algorithm
- Abstract: Abstract The purpose of this paper is to show that the iterative scheme recently studied by Xu (J Glob Optim 36(1):115–125, 2006) is the same as the one studied by Kamimura and Takahashi (J Approx Theory 106(2):226–240, 2000) and to give a supplement to these results. With the new technique proposed by Maingé (Comput Math Appl 59(1):74–79, 2010), we show that the convergence of the iterative scheme is established under another assumption. It is noted that if the computation error is zero or the approximate computation is exact, our new result is a genuine generalization of Xu’s result and Kamimura–Takahashi’s result.
  PubDate: 2013-05-01
Optimising a nonlinear utility function in multi-objective integer programming
- Abstract: Abstract In this paper we develop an algorithm to optimise a nonlinear utility function of multiple objectives over the integer efficient set. Our approach is based on identifying and updating bounds on the individual objectives as well as the optimal utility value. This is done using already known solutions, linear programming relaxations, utility function inversion, and integer programming. We develop a general optimisation algorithm for use with k objectives, and we illustrate our approach using a tri-objective integer programming problem.
  PubDate: 2013-05-01
New horizons in sphere-packing theory, part II: lattice-based derivative-free optimization via global surrogates
- Abstract: Abstract Derivative-free algorithms are frequently required for the optimization of nonsmooth scalar functions in n dimensions resulting, for example, from physical experiments or from the statistical averaging of numerical simulations of chaotic systems such as turbulent flows. The core idea of all efficient algorithms for problems of this type is to keep function evaluations far apart until convergence is approached. Generalized pattern search (GPS) algorithms, a modern class of methods particularly well suited to such problems, accomplish this by coordinating the search with an underlying grid which is refined, and coarsened, as appropriate. One of the most efficient subclasses of GPS algorithms, known as the surrogate management framework (SMF; see Booker et al. in Struct Multidiscip Optim 17:1–13, 1999), alternates between an exploratory search over an interpolating function which summarizes the trends exhibited by existing function evaluations, and an exhaustive poll which checks the function on neighboring points to confirm or confute the local optimality of any given candidate minimum point (CMP) on the underlying grid. The original SMF algorithm implemented a GPS step on an underlying Cartesian grid, augmented with a Kriging-based surrogate search. Rather than using the n-dimensional Cartesian grid (the typical choice), the present work introduces for this purpose the use of lattices derived from n-dimensional sphere packings. As reviewed and analyzed extensively in Part I of this series (see Belitz, PhD dissertation, University of California, San Diego, 2011, Chap. 2), such lattices are significantly more uniform and have many more nearest neighbors than their Cartesian counterparts. Both of these facts make them far better suited for coordinating GPS algorithms, as demonstrated here in a variety of numerical tests.
  PubDate: 2013-05-01
Convex underestimators of polynomials
- Abstract: Abstract Convex underestimators of a polynomial on a box. Given a non convex polynomial ${f\in \mathbb{R}[{\rm x}]}$ and a box ${{\rm B}\subset \mathbb{R}^n}$ , we construct a sequence of convex polynomials ${(f_{dk})\subset \mathbb{R}[{\rm x}]}$ , which converges in a strong sense to the “best” (convex and degree-d) polynomial underestimator ${f^{*}_{d}}$ of f. Indeed, ${f^{*}_{d}}$ minimizes the L 1-norm ${\Vert f-g\Vert_1}$ on B, over all convex degree-d polynomial underestimators g of f. On a sample of problems with non convex f, we then compare the lower bounds obtained by minimizing the convex underestimator of f computed as above and computed via the popular α BB method and some of its other refinements. In most of all examples we obtain significantly better results even with the smallest value of k.
  PubDate: 2013-05-01
From simulated annealing to stochastic continuation: a new trend in combinatorial optimization
- Abstract: Abstract Simulated annealing (SA) is a generic optimization method that is quite popular because of its ease of implementation and its global convergence properties. However, SA is widely reported to converge very slowly, and it is common practice to allow extra freedom in its design at the expense of losing global convergence guarantees. A natural way to increase the flexibility of SA is to allow the objective function and the communication mechanism to be temperature-dependent, the idea being to gradually reveal the complexity of the optimization problem and to increase the mixing rate at low temperatures. We call this general class of annealing processes stochastic continuation (SC). In the first part of this paper, we introduce SC starting from SA, and we derive simple sufficient conditions for the global convergence of SC. Our main result is interesting in two respects: first, the conditions for global convergence are surprisingly weak—in particular, they do not involve the variations of the objective function with temperature—and second, exponential cooling makes it possible to be arbitrarily close to the best possible convergence speed exponent of SA. The second part is devoted to the application of SC to the problem of producing aesthetically pleasing drawings of undirected graphs. We consider the objective function defined by Kamada and Kawai (Inf Process Lett 31(1):7–15, 1989), which measures the quality of a drawing as a weighted sum of squared differences between Euclidean and graph-theoretic inter-vertex distances. Our experiments show that SC outperforms SA with optimal communication setting both in terms of minimizing the objective function and in terms of standard aesthetic criteria.
  PubDate: 2013-05-01
Aircraft deconfliction with speed regulation: new models from mixed-integer optimization
- Abstract: Abstract Detecting and solving aircraft conflicts, which occur when aircraft sharing the same airspace are too close to each other according to their predicted trajectories, is a crucial problem in Air Traffic Management. We focus on mixed-integer optimization models based on speed regulation. We first solve the problem to global optimality by means of an exact solver. Since the problem is very difficult to solve, we also propose a heuristic procedure where the problem is decomposed and it is locally exactly solved. Computational results show that the proposed approach provides satisfactory results.
  PubDate: 2013-04-30
An illumination problem: optimal apex and optimal orientation for a cone of light
- Abstract: Abstract Let $\{a_i:i\in I\}$ be a finite set in $\mathbb R ^n$ . The illumination problem addressed in this work is about selecting an apex $z$ in a prescribed set $Z\subseteq \mathbb R ^n$ and a unit vector $y\in \mathbb R ^n$ so that the conic light beam $$\begin{aligned} C(z,y,s):= \{x \in \mathbb R ^n : s\,\Vert x-z\Vert - \langle y, x-z\rangle \le 0\} \end{aligned}$$ captures every $a_i$ and, at the same time, it has a sharpness coefficient $ s\in [0,1]$ as large as possible.
  PubDate: 2013-04-25
Interior-point algorithms for $P_{*}(\kappa )$ -LCP based on a new class of kernel functions
- Abstract: Abstract In this paper, we propose interior-point algorithms for $P_* (\kappa )$ -linear complementarity problem based on a new class of kernel functions. New search directions and proximity measures are defined based on these functions. We show that if a strictly feasible starting point is available, then the new algorithm has $\mathcal{O }\bigl ((1+2\kappa )\sqrt{n}\log n \log \frac{n\mu ^0}{\epsilon }\bigr )$ and $\mathcal{O }\bigl ((1+2\kappa )\sqrt{n} \log \frac{n\mu ^0}{\epsilon }\bigr )$ iteration complexity for large- and small-update methods, respectively. These are the best known complexity results for such methods.
  PubDate: 2013-04-24
Evolutionary annealing: global optimization in measure spaces
- Abstract: Abstract Stochastic optimization methods such as evolutionary algorithms and Markov Chain Monte Carlo methods usually involve a Markov search of the optimization domain. Evolutionary annealing is an evolutionary algorithm that leverages all the information gathered by previous queries to the cost function. Evolutionary annealing can be viewed either as simulated annealing with improved sampling or as a non-Markovian selection mechanism for evolutionary algorithms. This article develops the basic algorithm and presents implementation details. Evolutionary annealing is a martingale-driven optimizer, where evaluation yields a source of increasingly refined information about the fitness function. A set of experiments with twelve standard global optimization benchmarks is performed to compare evolutionary annealing with six other stochastic optimization methods. Evolutionary annealing outperforms other methods on asymmetric, multimodal, non-separable benchmarks and exhibits strong performance on others. It is therefore a promising new approach to global optimization.
  PubDate: 2013-04-21