The geometry of SDP-exactness in quadratic optimization

DOI10.1007/S10107-019-01399-8zbMATH Open1445.90075arXiv1804.01796OpenAlexW2963321289WikidataQ127881061 ScholiaQ127881061MaRDI QIDQ2191775FDOQ2191775

Diego Cifuentes, Corey Harris, Bernd Sturmfels

Publication date: 26 June 2020

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Abstract: Consider the problem of minimizing a quadratic objective subject to quadratic equations. We study the semialgebraic region of objective functions for which this problem is solved by its semidefinite relaxation. For the Euclidean distance problem, this is a bundle of spectrahedral shadows surrounding the given variety. We characterize the algebraic boundary of this region and we derive a formula for its degree.

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

zbMATH Keywords

semidefinite programmingconvex relaxationquadratic optimizationalgebraic degree

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Semidefinite programming (90C22) Intersection theory, characteristic classes, intersection multiplicities in algebraic geometry (14C17) Semialgebraic sets and related spaces (14P10)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Spectral Bundle Method for Semidefinite Programming
• Global optimization with polynomials and the problem of moments
• The Euclidean distance degree of an algebraic variety
• Semidefinite Optimization and Convex Algebraic Geometry
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• On symmetric and skew-symmetric determinantal varieties
• The algebraic degree of semidefinite programming
• Algebraic Degree of Polynomial Optimization
• On a positive semidefinite relaxation of the cut polytope
• Generic Spectrahedral Shadows
• Theta Bodies for Polynomial Ideals
• A general formula for the algebraic degree in semidefinite programming
• The cut locus of an ellipsoid
• Spectrahedral Shadows
• Sums of squares and varieties of minimal degree

Cited In (9)

• A Correlatively Sparse Lagrange Multiplier Expression Relaxation for Polynomial Optimization
• Parametric analysis of semidefinite optimization
• Iterated linear optimization
• On the tightness of semidefinite relaxations for rotation estimation
• On the local stability of semidefinite relaxations
• A general formula for the algebraic degree in semidefinite programming
• Invariants of SDP exactness in quadratic programming
• Bad projections of the PSD cone
• Exactness criteria for SDP-relaxations of quadratic extremum problems

This page was built for publication: The geometry of SDP-exactness in quadratic optimization

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