On the strength of Burer’s lifted convex relaxation to quadratic programming with ball constraints
研究了带多个球约束的二次规划问题，证明了Burer提出的提升凸松弛在理论上比基于Kronecker积的RLT不等式更紧，并指出某些RLT不等式是冗余的。
Abstract We study quadratic programs with m ball constraints, and the strength of a lifted convex relaxation for it recently proposed by Burer (2024). Burer shows this relaxation is exact when $$m=2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>m</mml:mi> <mml:mo>=</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> . For general m , Burer (2024) provides numerical evidence that this lifted relaxation is tighter than the Kronecker product based Reformulation Linearization Technique (RLT) inequalities introduced by Anstreicher (2017), and conjectures that this must be theoretically true as well. In this note, we provide an affirmative answer to this question and formally prove that this lifted relaxation indeed implies the Kronecker inequalities in the original space. Our proof is based on a decomposition of non-rank-one extreme rays of the lifted relaxation for each pair of ball constraints. Burer (2024) also numerically observes that for this lifted relaxation, an RLT-based inequality proposed by Zhen et al. (2021) is redundant, and conjectures this to be theoretically true as well. We also provide a formal proof that Zhen et al. (2021)’s as well as Jiang and Li (2019)’s SST inequalities are redundant for this lifted relaxation. In addition, we establish that Burer’s lifted relaxation is a particular case of the moment-sum-of-squares hierarchy.