Invariants of SDP exactness in quadratic programming

DOI10.1016/J.JSC.2023.102258MaRDI QIDQ6184179zbMATH OpenOpenAlexFDO

Authors Julia Lindberg, Jose Israel Rodriguez

Publication date 5 January 2024

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2211.05645

zbMATH Keywords

convex relaxationsquadratic programmingsemidefinite programming

Mathematics Subject Classification ID

Quadratic programming (90C20) Semidefinite programming (90C22)

Abstract: In this paper we study the Shor relaxation of quadratic programs by fixing a feasible set and considering the space of objective functions for which the Shor relaxation is exact. We first give conditions under which this region is invariant under the choice of generators defining the feasible set. We then describe this region when the feasible set is invariant under the action of a subgroup of $G{L}_n(mathbbR)$. We conclude by applying these results to quadratic binary programs. We give an explicit description of objective functions where the Shor relaxation is exact and use this knowledge to design an algorithm that produces candidate solutions for binary quadratic programs.

Recommendations

• Exactness criteria for SDP-relaxations of quadratic extremum problems
• KKT-based primal-dual exactness conditions for the Shor relaxation
• Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs
• Exact SDP relaxations of quadratically constrained quadratic programs with forest structures
• The geometry of SDP-exactness in quadratic optimization

Cites work

• A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
• Convex hull of two quadratic constraints is an LMI set
• Duallity and sensitivity in nonconvex quadratic optimization over an ellipsoid
• Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs
• Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxa\-tions
• Exactness of semidefinite relaxations for nonlinear optimization problems with underlying graph structure
• Exploiting Symmetries in SDP-Relaxations for Polynomial Optimization
• Exploiting symmetry in the power flow equations using monodromy
• Global optimization with polynomials and the problem of moments
• scientific article; zbMATH DE number 4070633 (Why is no real title available?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• On a positive semidefinite relaxation of the cut polytope
• On Convex Hulls of Epigraphs of QCQPs
• On the local stability of semidefinite relaxations
• On the tightness of SDP relaxations of QCQPs
• Optimality conditions and finite convergence of Lasserre's hierarchy
• Quadratic programming is in NP
• Semidefinite programming relaxation for nonconvex quadratic programs
• Semidefinite programming relaxations for semialgebraic problems
• Some results for quadratic problems with one or two quadratic constraints
• The geometry of SDP-exactness in quadratic optimization
• The unconstrained binary quadratic programming problem: a survey
• TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity

Cited in

(2)

• The equivalence of optimal perspective formulation and Shor's SDP for quadratic programs with indicator variables
• On exact and inexact RLT and SDP-RLT relaxations of quadratic programs with box constraints

This page was built for publication: Invariants of SDP exactness in quadratic programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6184179)