Global Optimization

Global and Convex Optimization in Modeling Environments: Compiler-Based, Excel, and Mathematica Implementations

  • János Pintér
    • Categories Applications - Science and Engineering, Global Optimization, Optimization Software and Modeling Systems

    We present a review of several software products that serve to analyze and solve nonlinear (specifically including global) optimization problems across different hardware and software platforms. The implementations discussed are LGO, as a stand-alone, but compiler-dependent modeling and solver environment; its Excel platform implementation; and MathOptimizer, a native solver package for Mathematica users. The discussion … Read more

    The Inverse Optimal Value Problem

  • Shabbir Ahmed
  • Yongpei Guan
    • Categories Global Optimization, Linear Programming, Linear, Cone and Semidefinite Programming Tags , , ,

    This paper considers the following inverse optimization problem: given a linear program, a desired optimal objective value, and a set of feasible cost coefficients, determine a cost-coefficient vector such that the corresponding optimal objective value of the linear program is closest to the given value. The above problem, referred here as the inverse optimal value … Read more

    Parallel Interval Continuous Global Optimization Algorithms

  • Abdeljalil Benyoub
    • Categories Branch and Cut Algorithms, Global Optimization, Parallel Algorithms Tags , , , , ,

    We theorically study, on a distributed memory architecture, the parallelization of Hansen’s algorithm for the continuous global optimization with inequality constraints, using interval arithmetic. We propose a parallel algorithm based on a dynamic redistribution of the working list among the processors. On the other hand, we exploit the reduction technique, developped by Hansen, for computing … Read more

    Efficient Algorithms for Large Scale Global Optimization: Lennard-Jones clusters

  • Marco Locatelli
  • Fabio Schoen
    • Categories Chemical Engineering, Stochastic Approaches Tags , , , , ,

    A standard stochastic global optimization method is applied to the challenging problem of finding the minimum energy conformation of cluster of identical atoms interacting through the Lennard-Jones potential. The method proposed is based on the use of a two-phase local search procedure which is capable of significantly enlarge the basin of attraction of the global … Read more

    A General Framework for Convex Relaxation of Polynomial Optimization Problems over Cones

  • Sunyoung Kim
  • Masakazu Kojima
  • Hayato Waki
    • Categories Global Optimization, Linear, Cone and Semidefinite Programming Tags , , , , , , ,

    The class of POPs (Polynomial Optimization Problems) over cones covers a wide range of optimization problems such as $0$-$1$ integer linear and quadratic programs, nonconvex quadratic programs and bilinear matrix inequalities. This paper presents a new framework for convex relaxation of POPs over cones in terms of linear optimization problems over cones. It provides a … Read more

    Global Optimization: Software, Test Problems, and Applications

  • János Pintér
    • Categories Global Optimization, Global Optimization Applications, Optimization Software and Modeling Systems Tags , , , ,

    We provide a concise review of the most prominent global optimization (GO) strategies currently available. This is followed by a discussion of GO software, test problems and several important types of applications, with additional pointers. The exposition is concentrated around topics related to continuous GO, although in certain aspects it is also pertinent to analogous … Read more

    GloptiPoly – Global Optimization over Polynomials withMatlab and SeDuMi

  • Didier Henrion
  • Jean-Bernard Lasserre
    • Categories Global Optimization, Problem Solving Environments, Semi-definite Programming

    GloptiPoly is a Matlab/SeDuMi add-on to build and solve convex linear matrix inequality relaxations of the (generally non-convex) global optimization problem of minimizing a multivariable polynomial function subject to polynomial inequality, equality or integer constraints. It generates a series of lower bounds monotonically converging to the global optimum. Numerical experiments show that for most of … Read more

    The Sample Average Approximation Method for Stochastic Programs with Integer Recourse

  • Shabbir Ahmed
  • Alexander Shapiro
    • Categories Integer Programming, Stochastic Approaches, Stochastic Programming Tags , , ,

    This paper develops a solution strategy for two-stage stochastic programs with integer recourse. The proposed methodology relies on approximating the underlying stochastic program via sampling, and solving the approximate problem via a specialized optimization algorithm. We show that the proposed scheme will produce an optimal solution to the true problem with probability approaching one exponentially … Read more

    A sequential convexification method (SCM) for continuous global optimization

  • Wenxing Zhu
    • Categories Global Optimization Tags , , ,

    A new method for continuous global minimization problems, acronymed SCM, is introduced. This method gives a simple transformation to convert the original objective function to an auxiliary function with gradually fewer local minimizers. All Local minimizers except a prefixed one of the auxiliary function is in the region where the function value of the original … Read more

    Semidefinite programming vs LP relaxations for polynomial programming

  • Jean-Bernard Lasserre
    • Categories Global Optimization Theory, Linear Programming, Semi-definite Programming

    We consider the global minimization of a multivariate polynomial on a semi-algebraic set \Omega defined with polynomial inequalities. We then compare two hierarchies of relaxations, namely, LP-relaxations based on products of the original constraints, in the spirit of the RLT procedure of Sherali and Adams and recent SDP (semi definite programming) relaxations introduced by the … Read more