Solving Stengle’s Example in Rational Arithmetic: Exact Values of the Moment-SOS Relaxations

  • Didier Henrion
    • Categories Semi-definite Programming Tags , , , ,

    We revisit Stengle’s classical univariate polynomial optimization example $\min 1-x^2$ s.t. $(1-x^2)^3\ge 0$ whose constraint description is degenerate at the minimizers. We prove that the moment-SOS hierarchy of relaxation order $r\ge 3$ has the exact value $-1/r(r-2)$. For this we construct in rational arithmetic a dual polynomial sum-of-squares (SOS) certificate and a primal moment sequence … Read more

    A Proximal-Gradient Method for Solving Regularized Optimization Problems with General Constraints

  • Daniel P. Robinson
  • Frank E. Curtis
  • Xiaoyi Qu
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Nonsmooth Optimization Tags , , , , , ,

    We propose, analyze, and test a proximal-gradient method for solving regularized optimization problems with general constraints. The method employs a decomposition strategy to compute trial steps and uses a merit function to determine step acceptance or rejection. Under various assumptions, we establish a worst-case iteration complexity result, prove that limit points are first-order KKT points, … Read more

    An active-set method for box-constrained multiobjective optimization

  • N. S. Fazzio
  • Leandro Fonseca Prudente
  • María Laura Schuverdt
    • Categories Multi-Criteria Optimization Tags , , ,

    We propose an active-set algorithm for smooth multiobjective optimization problems subject to box constraints. The method works on one face of the feasible set at a time, treating it as a lower-dimensional region on which the problem simplifies. At each iteration, the algorithm decides whether to remain on the current face or to move to … Read more

    Global optimization of low-rank polynomials

  • Llorenç Balada Gaggioli
  • Didier Henrion
  • Milan Korda
    • Categories Global Optimization, Semi-definite Programming

    This work considers polynomial optimization problems where the objective admits a low-rank canonical polyadic tensor decomposition. We introduce LRPOP (low-rank polynomial optimization), a new hierarchy of semidefinite programming relaxations for which the size of the semidefinite blocks is determined by the canonical polyadic rank rather than the number of variables. As a result, LRPOP can … Read more

    Primal-dual resampling for solution validation in convex stochastic programming

  • Yi Chu
  • Susan R. Hunter
  • Raghu Pasupathy
    • Categories Convex Optimization, Optimization in Data Science, Stochastic Programming Tags , ,

    Suppose we wish to determine the quality of a candidate solution to a convex stochastic program in which the objective function is a statistical functional parameterized by the decision variable and known deterministic constraints may be present. Inspired by stopping criteria in primal-dual and interior-point methods, we develop cancellation theorems that characterize the convergence of … Read more

    Exact and approximate formulations for the close-enough TSP

  • Domingo Araya
  • Gustavo Angulo
  • Margarita P Castro
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms Tags , ,

    This work addresses the Close-Enough Traveling Salesman Problem (CETSP), a variant of the classic traveling salesman problem in which we seek to visit neighborhoods of points in the plane (defined as disks) rather than specific points. We present two exact formulations for this problem based on second-order cone programming (SOCP), along with approximated mixed-integer linear … Read more

    Facial reduction for nice (and non-nice) convex programs

  • Ying Lin
  • Tianxiang Liu
  • Bruno F. Lourenço
    • Categories Convex and Nonsmooth Optimization, Convex Optimization Tags , , ,

    Consider the primal problem of minimizing the sum of two closed proper convex functions \(f\) and \(g\). If the relative interiors of the domains of \(f\) and \(g\) intersect, then the primal problem and its corresponding Fenchel dual satisfy strong duality. When these relative interiors fail to intersect, pathologies and numerical difficulties may occur. In … Read more

    Semidefinite hierarchies for diagonal unitary invariant bipartite quantum states

  • Jonas Britz
  • Monique Laurent
    • Categories Semi-definite Programming Tags , , , , , , , , ,

    We investigate questions about the cone \(\mathrm{SEP}_n\) of separable bipartite states, consisting of the Hermitian matrices acting on \(\mathbb{C}^n\otimes\mathbb{C}^n\) that can be written as conic combinations of rank one matrices of the form \(xx^*\otimes yy^*\) with \(x,y\in\mathbb{C}^n\). Bipartite states that are not separable are said to be entangled. Detecting quantum entanglement is a fundamental task … Read more

    Stability analysis of parameterized models relative to nonconvex constraints

  • Zijian Shi
  • Miantao Chao
    • Categories Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization Tags , , , , ,

    For solution mappings of parameterized models (such as optimization problems, variational inequalities, and generalized equations), standard stability inevitably fails as the parameter approaches the boundary of the feasible domain. One remedy is relative stability restricted to a constraint set (e.g., the feasible domain), which is our focus in this paper. We establish generalized differentiation criteria … Read more

    Weight reduction inequalities revisited

  • Shreyas Bhowmik
  • Sachin Jayaswal
    • Categories 0-1 Programming Tags , , , ,

    In this paper, we propose an extension of the classical weight reduction inequalities for the binary knapsack polytope for settings where the maximum-weight item in the associated pack is not unique. We derive sufficient conditions under which the extended inequalities are facet-defining and identify conditions under which they strictly dominate the original weight reduction inequalities. … Read more