Global Optimization Theory

Think co(mpletely )positive ! Matrix properties, examples and a clustered bibliography on copositive optimization

  • Immanuel M. Bomze
  • Werner Schachinger
  • Gabriele Uchida
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Linear, Cone and Semidefinite Programming

    Copositive optimization is a quickly expanding scientific research domain with wide-spread applications ranging from global nonconvex problems in engineering to NP-hard combinatorial optimization. It falls into the category of conic programming (optimizing a linear functional over a convex cone subject to linear constraints), namely the cone of all completely positive symmetric nxn matrices, and its … Read more

    An Infeasible-Point Subgradient Method Using Adaptive Approximate Projections

  • Dirk A. Lorenz
  • Marc E. Pfetsch
  • Andreas M. Tillmann
    • Categories Convex Optimization, Global Optimization Theory, Nonsmooth Optimization Tags , , , , ,

    We propose a new subgradient method for the minimization of convex functions over a convex set. Common subgradient algorithms require an exact projection onto the feasible region in every iteration, which can be efficient only for problems that admit a fast projection. In our method we use inexact adaptive projections requiring to move within a … Read more

    A new look at nonnegativity on closed sets and polynomial optimization

  • Jean-Bernard Lasserre
    • Categories Global Optimization Applications, Global Optimization Theory, Nonlinear Optimization

    We first show that a continuous function “f” is nonnegative on a closed set K if and only if (countably many) moment matrices of some signed measure dnu = fdmu are all positive semidefinite (if K is compact mu is an arbitrary finite Borel measure with support exactly K). In particular, we obtain a convergent … Read more

    On global optimizations of the rank and inertia of the matrix function $A_1- B_1XB^*_1$ subject to a pair of matrix equations $[\,B_2XB^*_2, \, B_3XB^*_3 \,] = [\,A_2, \, A_3\,]$

  • Yongge Tian
    • Categories Global Optimization Theory

    For a given linear matrix function $A_1 – B_1XB^*_1$, where $X$ is a variable Hermitian matrix, this paper derives a group of closed-form formulas for calculating the global maximum and minimum ranks and inertias of the matrix function subject to a pair of consistent matrix equations $B_2XB^*_2 = A_2$ and $B_3XB_3^* = A_3$. As applications, … Read more

    Inverse polynomial optimization

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

    We consider the inverse optimization problem associated with the polynomial program $f^*=\min \{f(x):x\inK\}$ and a given current feasible solution $y\in K$. We provide a numerical scheme to compute an inverse optimal solution. That is, we compute a polynomial $\tilde{f}$ (which may be of same degree as $f$ if desired) with the following properties: (a) $y$ … Read more

    Lifted Inequalities for 0−1 Mixed-Integer Bilinear Covering Sets

  • Kwanghun Chung
  • Jean-Philippe P. Richard
  • Mohit Tawarmalani
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Global Optimization Theory Tags , ,

    In this paper, we study 0-1 mixed-integer bilinear covering sets. We derive several families of facet-defining inequalities via sequence-independent lifting techniques. We then show that these sets have polyhedral structures that are similar to those of certain fixed-charge single-node flow sets. As a result, we obtain new facet-defining inequalities for these sets that generalize well-known … Read more

    SOME REGULARITY RESULTS FOR THE PSEUDOSPECTRAL ABSCISSA AND PSEUDOSPECTRAL RADIUS OF A MATRIX

  • Mert Gurbuzbalaban
  • Michael L. Overton
    • Categories Global Optimization Theory, Nonlinear Optimization, Nonsmooth Optimization Tags , , , , ,

    The $\epsilon$-pseudospectral abscissa $\alpha_\epsilon$ and radius $\rho_\epsilon$ of an n x n matrix are respectively the maximal real part and the maximal modulus of points in its $\epsilon$-pseudospectrum, defined using the spectral norm. It was proved in [A.S. Lewis and C.H.J. Pang. Variational analysis of pseudospectra. SIAM Journal on Optimization, 19:1048-1072, 2008] that for fixed … Read more

    On the relation between concavity cuts and the surrogate dual for convex maximization problems

  • Marco Locatelli
  • Fabio Schoen
    • Categories Global Optimization, Global Optimization Theory Tags , ,

    In this note we establish a relation between two bounds for convex maximization problems, the one based on a concavity cut, and the surrogate dual bound. Both bounds have been known in the literature for a few decades but, to the authors’ knowledge, the relation between them has not been previously observed in the literature. … Read more

    NP-hardness of Deciding Convexity of Quartic Polynomials and Related Problems

  • Amir Ali Ahmadi
  • Alex Olshevsky
  • Pablo A. Parrilo
  • John N. Tsitsiklis
    • Categories Convex Optimization, Global Optimization Theory Tags , , ,

    We show that unless P=NP, there exists no polynomial time (or even pseudo-polynomial time) algorithm that can decide whether a multivariate polynomial of degree four (or higher even degree) is globally convex. This solves a problem that has been open since 1992 when N. Z. Shor asked for the complexity of deciding convexity for quartic … Read more

    Reduced RLT Representations for Nonconvex Polynomial Programming Problems

  • Evrim Dalkiran
  • Leo Liberti
  • Hanif D. Sherali
    • Categories Global Optimization Theory Tags , , , , ,

    This paper explores equivalent, reduced size Reformulation-Linearization Technique (RLT)-based formulations for polynomial programming problems. Utilizing a basis partitioning scheme for an embedded linear equality subsystem, we show that a strict subset of RLT defining equalities imply the remaining ones. Applying this result, we derive significantly reduced RLT representations and develop certain coherent associated branching rules … Read more