错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Equivalent sufficient conditions for global optimality of quadratically constrained quadratic programs

  • Sunyoung Kim,
  • Masakazu Kojima

摘要

We study the equivalence of several well-known sufficient optimality conditions for a general quadratically constrained quadratic program (QCQP). The conditions are classified in two categories. The first is for determining an optimal solution and the second is for finding an optimal value. The first category includes the existence of a saddle point of the Lagrangian function and the existence of a rank-1 optimal solution of the primal SDP relaxation of QCQPs. The second category includes \(\eta _p = \zeta \) η p = ζ , \(\eta _d = \zeta \) η d = ζ , and \(\varphi = \zeta \) φ = ζ , where \(\zeta \) ζ , \(\eta _p\) η p , \(\eta _d\) η d , and \(\varphi \) φ denote the optimal values of QCQPs, the primal SDP relaxation, the dual SDP relaxation and the Lagrangian dual, respectively. We show the equivalence of these conditions with or without assuming the existence of an optimal solution of QCQP and/or the Slater constraint qualification for the primal SDP relaxation. The results on the conditions are also extended to the doubly nonnegative relaxation of equality constrained QCQPs in nonnegative variables.