Linear, Cone and Semidefinite Programming

On exact copositive representation of simplicial quadratic optimization problems, their strong conic duality and a new proof of the Frank-Wolfe theorem

  • Immanuel M. Bomze
  • E. Alper Yildirim
    • Categories Cone Programming, Global Optimization, Global Optimization Theory

    We are interested in exactness, strong conic duality and dual attainability in copositive relaxations of quadratic optimization problems (QPs) of a special form, in which any (feasible) QP can be recast. By using our results, the celebrated Frank-Wolfe theorem on the attainability of any bounded QP even over unbounded polyhedra, regardless of whether the objective … Read more

    Automorphisms of hyperbolic polynomials

  • Michael Orlitzky
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    The pair \( (p,e) \) is hyperbolic if \( p : \mathbb{R}^{n} \to \mathbb{R} \) is a homogeneous polynomial, if \( e \in \mathbb{R}^{n} \), if \( p(e) > 0 \), and if the roots of \( t \mapsto p(te – x) \) are real for all \( x \in \mathbb{R}^{n} \). In that case, … Read more

    Disjunctive Sum of Squares

  • Amir Ali Ahmadi
  • Sanjeeb Dash
  • Yixuan Hua
  • Bartolomeo Stellato
    • Categories Cone Programming, Convex Optimization, Semi-definite Programming Tags , , , , , , ,

    We introduce the concept of disjunctive sum of squares for certifying nonnegativity of polynomials. Unlike the popular sum of squares approach where nonnegativity is certified by a single algebraic identity, the disjunctive sum of squares approach certifies nonnegativity with multiple algebraic identities which can be found in parallel. Our main result is a disjunctive Positivstellensatz … Read more

    Convex Hulls of Binary Reflected Gray Code Intervals

  • Gustavo Angulo
    • Categories (Mixed) Integer Linear Programming, Linear Programming, Polyhedra Tags , ,

    The binary reflected Gray code orders the vertices of the unit hypercube along a Hamiltonian path in which consecutive vertices differ in exactly one coordinate. While Gray codes have been extensively studied from a combinatorial perspective, much less is known about the polyhedral structure of convex hulls of contiguous subpaths of this order. This paper … Read more

    Maximum Cuts and Fractional Cut Covers: A Computational Study of a Randomized Semidefinite Programming Approach

  • Nathan Benedetto Proença
  • Marcel K. de Carli Silva
  • Levent Tunçel
    • Categories Approximation Algorithms, Optimization Software and Modeling Systems, Semi-definite Programming

    We present experimental work on a primal-dual framework simultaneously approximating maximum cut and weighted fractional cut-covering instances. In this primal-dual framework, we solve a semidefinite programming (SDP) relaxation to either the maximum cut problem or to the weighted fractional cut-covering problem, and then independently sample a collection of cuts via the random-hyperplane technique. We then … Read more

    Finding Short Paths on Simple Polytopes

  • Alexander Black
  • Raphael Steiner
    • Categories Combinatorial Optimization, Linear Programming, Polyhedra Tags , , , , ,

    We prove that computing a shortest monotone path to the optimum of a linear program over a simple polytope is NP-hard, thus resolving a 2022 open question of De Loera, Kafer, and Sanit\`{a}. As a consequence, finding a shortest sequence of pivots to an optimal basis with the simplex method is NP-hard. In fact, we … Read more

    Pricing Discrete and Nonlinear Markets With Semidefinite Relaxations

  • Cheng Guo
  • Lauren Henderson
  • Ryan Cory-Wright
  • Boshi Yang
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Semi-definite Programming Tags , , , ,

    Nonconvexities in markets with discrete decisions and nonlinear constraints make efficient pricing challenging, often necessitating subsidies. A prime example is the unit commitment (UC) problem in electricity markets, where costly subsidies are commonly required. We propose a new pricing scheme for nonconvex markets with both discreteness and nonlinearity, by convexifying nonconvex structures through a semidefinite … Read more

    On the Single-Multi-Commodity Gap: Lifting Single- to Multicommodity Flow Instances

  • Felix P. Broesamle
  • Stefan Nickel
    • Categories Applications - OR and Management Sciences, Linear Programming, Network Optimization Tags , , , , ,

    Benchmark instances for multicommodity flow problems frequently lack the structural nuances of real-world networks or fail to maintain a rigorous mathematical relationship with their single-commodity counterparts. This paper introduces a formal meta-generation framework that addresses these limitations by lifting single-commodity minimum-cost flow instances into the multicommodity space while strictly preserving the underlying network topology, capacity … Read more

    Separable QCQPs and Their Exact SDP Relaxations

  • Masakazu Kojima
  • Sunyoung Kim
  • Naohiko Arima
    • Categories Global Optimization Theory, Quadratic Programming, Semi-definite Programming Tags , , , , ,

    This paper studies exact semidefinite programming relaxations (SDPRs) for separable quadratically constrained quadratic programs (QCQPs). We consider the construction of a larger separable QCQP from multiple QCQPs with exact SDPRs. We show that exactness is preserved when such QCQPs are combined through a separable horizontal connection, where the coupling is induced through the right-hand-side parameters … Read more

    Beyond binarity: Semidefinite programming for ternary quadratic problems

  • Frank de Meijer
  • Veronica Piccialli
  • Renata Sotirov
  • Antonio M. Sudoso
    • Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming, Semi-definite Programming Tags , , ,

    We study the ternary quadratic problem (TQP), a quadratic optimization problem with linear constraints where the variables take values in {0,±1}. While semidefinite programming (SDP) techniques are well established for {0,1}- and {±1}-valued quadratic problems, no dedicated integer semidefinite programming framework exists for the ternary case. In this paper, we introduce a ternary SDP formulation … Read more