Instance-specific linear relaxations of semidefinite optimization problems

  • We introduce a generic technique to obtain linear relaxations of semidefinite programs with provable guarantees based on the commutativity of the constraint and the objective matrices. We study conditions under which the optimal value of the SDP and the proposed linear relaxation match, which we then relax to provide a flexible methodology to derive effective linear relaxations. We specialize these results to provide linear programs that approximate well-known semidefinite programs for the max cut problem proposed by Poljak and Rendl, and the Lovász theta number; we prove that the linear program proposed for max cut certifies a known eigenvalue bound for the maximum cut value and is in fact stronger. Our ideas can be used to warm-start algorithms that solve semidefinite programs by iterative polyhedral approximation of the feasible region. We verify this capability through multiple experiments on the max cut semidefinite program, the Lovász theta number and on three families of semidefinite programs obtained as convex relaxations of certain quadratically constrained quadratic problems.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Daniel de Roux, Robert Carr, R. Ravi
DOI:https://doi.org/10.1007/s12532-025-00275-1
ISSN:1867-2949
Parent Title (English):Mathematical Programming Computation
Publisher:Springer Science and Business Media LLC
Document Type:Article
Language:English
Year of Completion:2025
Volume:17
Issue:2
Page Number:51
First Page:385
Last Page:435
Mathematical Programming Computation :MPC 2025 - Issue 2
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.