Global Optimization

We present a unified approach to a class of nonconvex global optimization problems with composite monotonic constraints. (By composite monotonic function is meant a function which is the composition of a monotonic function on ℝⁿ with a mapping from ℝⁿ → ℝ^m with m ≤ n.) This class includes problems with constraints involving products of linear functions, sums of ratio functions, etc., and also problems of constrained optimization over efficient/weakly efficient points. The approach is based on transforming the problem into a monotonic optimization problem in the space ℝ^p, which can then be efficiently solved by recently developed techniques. Nontrivial numerical examples are presented to illustrate the practicability of the approach.

In this paper we propose two variants of Local Search Method for reverse convex problems. The first is based on well-known theorem of H. Tuy as well as on Linearization Principle. The second variant is due to an idea of J. Rosen. We demonstrate the practical effectiveness of the proposed methods computationally.

In this chapter some transformation techniques, useful in deterministic global optimization, are discussed. With the given techniques, a general class of nonconvex MINLP (mixed integer non-linear programming) problems can be solved to global optimality. The transformations can be applied to signomial functions and the feasible region of the original problem can be convexified and overestimated by the transformations. The global optimal solution of the original nonconvex problem can be found by solving a sequence of convexified MINLP sub-problems. In each such iteration a part of the infeasible region is cut off and the algorithm terminates when a solution point is sufficiently close to or within the feasible region of the original problem. The principles behind the algorithm are given in this chapter and numerical examples are used to illustrate how the global optimal solution is obtained with the algorithm.

In this paper, we present a novel approach for solving nonlinear mixed integer stochastic programming problems. In particular, we consider two stage stochastic problem with nonlinearities both in the objective function and constraints, pure integer first stage and mixed-integer second stage variables. We formulate the problem by a scenario based representation, adding linear nonanticipativity constraints coming from splitting the first stage decision variables. In the separation phase we fully exploit the partial decomposable structure of SMINLPs. This allows to deal with a separable nondifferentiable problem, which can be solved by Lagrangian dual based procedure. In particular, we propose a specialization of the Randomized Incremental Subgradient Method- proposed by Bertsekas(2001)- which takes dynamically into account the information relative to the scenarios. The coordination phase is aimed at enforcing coordination among the solutions of the scenario subproblems. More specifically, we use a branch and bound in order to enforce the feasibility of the relaxed nonanticipativity constraints. In order to make more efficient the over-all method, we embed the Lagrangian iteration in a branch and bound scheme, by avoiding the exact solution of the dual problem and we propose an early branching rule and a worm start procedure to use within the Branch and Bound tree. Although SMINLPs have many application contexts, this class of problem has not been adequately treated in the literature. We propose a stochastic formulation of the Trim Loss Problem, which is new in the literature. A formal mathematical formulation is provided in the framework of two-stage stochastic programming which explicitly takes into account the uncertainty in the demand. Preliminary computational results illustrate the ability of the proposed method to determine the global optimum significantly decreasing the solution time. Furthermore, the proposed approach is able to solve instances of the problem intractable with conventional approaches.

We describe an application of Variable Neighbourhood Search (VNS) methodology to continuous global optimization problems with box constraints. A general VNS algorithm is implemented within the software package GLOB. The tests are performed on some standard test functions and on a class of NP-hard global optimization problems arising in practice. The computational results show the potential of the new software.

Global Optimization software packages for solving Mixed-Integer Non-linear Optimization Problems are usually complex pieces of codes. Some of the difficulties involved in coding a good GO software are: embedding third-party local optimization codes within the main global optimization algorithm; providing efficient memory representations of the optimization problem; making sure that every part of the code is fully reentrant. Finding good software engineering solutions for these difficulties is not enough to make sure that the outcome will be a GO software that works well. However, starting from a sound software design makes it easy to concentrate on improving the efficiency of the global optimization algorithm implementation. In this paper we discuss the main issues that arise when writing a global optimization software package, namely software architecture and design, symbolic manipulation of mathematical expressions, choice of local solvers and implementation of global solvers.

The AutoGraphiX (AGX) system for computer assisted or, for some of its functions, fully automated graph theory was developed at GERAD, Montreal since 1997. We report here on a new version (AGX 2) of that system. It contains many enhancements, as well as a new function for automated proof of simple propositions. Among other results, AGX 2 led to several hundred new conjectures, ranking from easy ones, proved automatically, to others requiring longer unassisted or partially assisted proofs, to open ones. Many examples are given, illustrating AGX 2’s functions and the results obtained.

Metaheuristics are strategies to design heuristic procedures to find high quality solutions to an optimization problem. This chapter focuses on the implementation aspects of heuristic algorithms based on metaheuristics, using an object oriented approach. This programming paradigm takes advantage of the common parts shared by codes that implement different metaheuristic procedures. We give a class hierarchy for metaheuristics that permits quickly generate algorithms from existing metaheuristic codes for specific problems by extending a few classes and adding the problem functionality. It also allows the development of new metaheuristic algorithms without programming from scratch the basis of the procedure. It consists of selecting an appropriate class with the closest functionality, and extending it to add the core of the algorithm. The purpose of this hierarchy is thus to provide an extensible model for a quick implementation of metaheuristics and the problem structures associated with them.

The OVO (Order-Value Optimization) problem consists in the min-imization of the Order-Value function f(x), defined by \( f\left( x \right) = f_{i_p \left( x \right)} \left( x \right) \), where \( f_{i_1 \left( x \right)} \left( x \right) \leqslant ... \leqslant f_{i_m \left( x \right)} \left( x \right) \). The functions f₁,..., f_m are defined on Ω ⊂ ℝⁿ and p is an integer between 1 and m. When x is a vector of portfolio positions and f_i(x) is the predicted loss under the scenario i, the Order-Value function is the discrete Value-at-Risk (VaR) function, which is largely used in risk evaluations. The OVO problem is continuous but nonsmooth and, usually, has many local minimizers. A local method with guaranteed convergence to points that satisfy an optimality condi-tion was recently introduced by Andreani, Dunder and Martinez. The local method must be complemented with a global minimization strategy in order to be effective when m is large. A global optimization method is defined where local minimizations are improved by a tunneling strategy based on the harmonic oscillator initial value problem. It will be proved that the solution of this initial value problem is a smooth and dense trajectory if Ω is a box. An application of OVO to the problem of find-ing hidden patterns in data sets that contain many errors is described. Challenging numerical experiments are presented.

The molecular distance geometry problem can be stated as the deter-mination of the three-dimensional structure of a molecule using a set of distances between pairs of atoms. It can be formulated as a global minimization problem, where the main difficulty is the exponential increasing of local minimizers with the size of the molecule. The aim of this study is to generate new instances for the molecular distance geometry problem that can be used in order to test algorithms designed to solve it.