Skip to content

Hao Hu, Xinxin Li, Facial reduction for the Shor SDP relaxation of QCQPs

Full Text: PDF
DOI: 10.23952/asvao.5.2023.2.05
Volume 5, Issue 2, 1 August 2023, Pages 181-191

 

Abstract. We propose a special facial reduction algorithm (FRA) for the Shor semidefinite programming (SDP) relaxation of the quadratically constrained quadratic program (QCQP). Under the mild assumption, our special FRA only requires solving a linear programming problem instead of a semidefinite program. In particular, when applied to the binary quadratic program, the proposed special FRA needs fewer assumptions. From a computational perspective, this result improves the scalability and stability of the SDP approach for QCQP problems. In addition, we also discover a new class of semidefinite programs whose singularity degree can be computed easily. This new class complements the limited examples of singularity degrees in the literature. As a by-product, our special FRA can be used to upper bound the dimension of any set defined by quadratic inequalities.

 

How to Cite this Article:
H. Hu, X. Li, Facial reduction for the Shor SDP relaxation of QCQPs, Appl. Set-Valued Anal. Optim. 5 (2023), 181-191.