Semi-definite Programming

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

    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

    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

    Compact Lifted Relaxations for Low-Rank Optimization

  • Ryan Cory-Wright
  • Jean Pauphilet
    • Categories Semi-definite Programming Tags , ,

    We develop tractable convex relaxations for rank-constrained quadratic optimization problems over $n \times m$ matrices, a setting for which tractable relaxations are typically only available when the objective or constraints admit spectral (permutation-invariant) structure. We derive lifted semidefinite relaxations that do not require such spectral terms. Although a direct lifting introduces a large semidefinite constraint … Read more

    Quasinormality and pseudonormality for nonlinear semidefinite programming

  • Daiana Santos
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , ,

    Quasinormality is a classical constraint qualification originally introduced by Hestenes in 1975 and subsequently extensively studied in nonlinear programming and in problems with abstract constraints. In this paper, we extend this concept to the setting of nonlinear semidefinite programming (NSDP). We show that the proposed condition is strictly weaker than Robinson’s constraint qualification, while still … Read more

    Separating Hyperplanes for Mixed-Integer Polynomial Optimization Problems

  • Carl Eggen
  • Jan Kronqvist
  • Andreas Lundell
  • Stefan Volkwein
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Semi-definite Programming Tags , , ,

    Algorithms based on polyhedral outer approximations provide a powerful approach to solving mixed-integer nonlinear optimization problems. An initial relaxation of the feasible set is strengthened by iteratively adding linear inequalities and separating infeasible points. However, when the constraints are nonconvex, computing such separating hyperplanes becomes challenging. In this article, the moment-/sums-of-squares hierarchy is used in … Read more

    Tight semidefinite programming relaxations for sparse box-constrained quadratic programs

  • Aida Khajavirad
    • Categories (Mixed) Integer Nonlinear Programming, Semi-definite Programming Tags , , , , ,

    We introduce a new class of semidefinite programming (SDP) relaxations for sparse box-constrained quadratic programs, obtained by a novel integration of the Reformulation Linearization Technique into standard SDP relaxations while explicitly exploiting the sparsity of the problem. The resulting relaxations are not implied by the existing LP and SDP relaxations for this class of optimization … Read more

    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

    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