global optimization

Sums of Squares and Semidefinite Programming Relaxations for Polynomial Optimization Problems with Structured Sparsity

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

    Unconstrained and inequality constrained sparse polynomial optimization problems (POPs) are considered. A correlative sparsity pattern graph is defined to find a certain sparse structure in the objective and constraint polynomials of a POP. Based on this graph, sets of supports for sums of squares (SOS) polynomials that lead to efficient SOS and semidefinite programming (SDP) … Read more

    A Trust-Region Algorithm for Global Optimization

  • Bernardetta Addis
  • Sven Leyffer
    • Categories Stochastic Approaches Tags , ,

    We consider the global minimization of a bound-constrained function with a so-called funnel structure. We develop a two-phase procedure that uses sampling, local optimization, and Gaussian smoothing to construct a smooth model of the underlying funnel. The procedure is embedded in a trust-region framework that avoids the pitfalls of a fixed sampling radius. We present … Read more

    A Simplicial Branch-and-Bound Algorithm for Solving Quadratically Constrained Quadratic Programs

  • Jeff Linderoth
    • Categories Global Optimization Theory Tags , , ,

    We propose a branch-and-bound algorithm for solving nonconvex quadratically-constrained quadratic programs. The algorithm is novel in that branching is done by partitioning the feasible region into the Cartesian product of two-dimensional triangles and rectangles. Explicit formulae for the convex and concave envelopes of bilinear functions over triangles and rectangles are derived and shown to be … Read more

    An Extension of Sums of Squares Relaxations to Polynomial Optimization Problems over Symmetric Cones

  • Masakazu Kojima
  • Masakazu Muramatsu
    • Categories Global Optimization Theory, Semi-definite Programming Tags , , , , , ,

    This paper is based on a recent work by Kojima which extended sums of squares relaxations of polynomial optimization problems to polynomial semidefinite programs. Let ${\cal E}$ and ${\cal E}_+$ be a finite dimensional real vector space and a symmetric cone embedded in ${\cal E}$; examples of $\calE$ and $\calE_+$ include a pair of the … Read more

    A comparison of complete global optimization solvers

  • Waltraud Huyer
  • Arnold Neumaier
  • Oleg Shcherbina
  • Tamás Vinkó
    • Categories Global Optimization Tags , , ,

    Results are reported of testing a number of existing state of the art solvers for global constrained optimization and constraint satisfaction on a set of over 1000 test problems in up to 1000 variables. Citationsubmitted to the special issue on Global Optimization of Math. ProgrammingArticleDownload View PDF

    Local Optimization Method with Global Multidimensional

  • Adil Bagirov
  • Alex Rubinov
  • Jiapu Zhang
    • Categories Global Optimization Tags , , , ,

    This paper presents a new method for solving global optimization problems. We use a local technique based on the notion of discrete gradients for finding a cone of descent directions and then we use a global cutting angle algorithm for finding global minimum within the intersection of the cone and the feasible region. We present … Read more

    Sums of Squares Relaxations of Polynomial Semidefinite Programs

  • Masakazu Kojima
    • Categories Constrained Nonlinear Optimization, Global Optimization Theory, Semi-definite Programming Tags , , , , , , ,

    A polynomial SDP (semidefinite program) minimizes a polynomial objective function over a feasible region described by a positive semidefinite constraint of a symmetric matrix whose components are multivariate polynomials. Sums of squares relaxations developed for polynomial optimization problems are extended to propose sums of squares relaxations for polynomial SDPs with an additional constraint for the … Read more

    Local optima smoothing for global optimization

  • Bernardetta Addis
  • Marco Locatelli
  • Fabio Schoen
    • Categories Stochastic Approaches Tags , , , , ,

    It is widely believed that in order to solve large scale global optimization problems an appropriate mixture of local approximation and global exploration is necessary. Local approximation, if first order information on the objective function is available, is efficiently performed by means of local optimization methods. Unfortunately, global exploration, in absence of some kind of … Read more

    Generalized Lagrangian Duals and Sums of Squares Relaxations of Sparse Polynomial Optimization Problems

  • Sunyoung Kim
  • Masakazu Kojima
  • Hayato Waki
    • Categories Global Optimization Theory, Semi-definite Programming Tags , , , , , , ,

    Sequences of generalized Lagrangian duals and their SOS (sums of squares of polynomials) relaxations for a POP (polynomial optimization problem) are introduced. Sparsity of polynomials in the POP is used to reduce the sizes of the Lagrangian duals and their SOS relaxations. It is proved that the optimal values of the Lagrangian duals in the … Read more

    Sharpening the Karush-John optimality conditions

  • Arnold Neumaier
  • Hermann Schichl
    • Categories Constrained Nonlinear Optimization Tags , ,

    A refined version of the Karush-John first order optimality conditions is presented which reduces the number of constraints for which a constraint qualification is needed. This version is a generalization both of the Karush-John conditions and of the first order optimality conditions for concave constraints. ArticleDownload View PDF