期刊
MATHEMATICAL PROGRAMMING
卷 193, 期 1, 页码 33-73出版社
SPRINGER HEIDELBERG
DOI: 10.1007/s10107-020-01589-9
关键词
Quadratically constrained quadratic programming; Semidefinite program; Relaxation; Lagrange function; Convex hull
类别
资金
- NSF [CMMI 1454548]
- ONR [N00014-19-1-2321]
This paper studies the conditions of SDP relaxation for QCQP problems, proving the tightness of SDP relaxation when the quadratic eigenvalue multiplicity is large enough, presenting similar sufficient conditions that the projected epigraph of SDP gives the convex hull of the original QCQP's epigraph. Our results also imply new sufficient conditions for the tightness and convex hull exactness of second order cone program relaxation of simultaneously diagonalizable QCQPs.
Quadratically constrained quadratic programs (QCQPs) are a fundamental class of optimization problems well-known to be NP-hard in general. In this paper we study conditions under which the standard semidefinite program (SDP) relaxation of a QCQP is tight. We begin by outlining a general framework for proving such sufficient conditions. Then using this framework, we show that the SDP relaxation is tight whenever the quadratic eigenvalue multiplicity, a parameter capturing the amount of symmetry present in a given problem, is large enough. We present similar sufficient conditions under which the projected epigraph of the SDP gives the convex hull of the epigraph in the original QCQP. Our results also imply new sufficient conditions for the tightness (as well as convex hull exactness) of a second order cone program relaxation of simultaneously diagonalizable QCQPs.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据