摘要
In this paper, we revisit the strong duality of the quadratically constrained quadratic programming(QCQP) problem. We first generalize a known result for the rank-one decomposition of matrices and then apply it to consider the strong duality for more general QCQP scenarios, including the cases with one constraint, two constraints while at least one being inactive on the optimal solution point, multiple constraints, and an interval constraint. A sufficient condition ensuring the strong duality of more general QCQP problems is studied as well. We also extend our results to the QCQP problems with complex variables.
In this paper, we revisit the strong duality of the quadratically constrained quadratic programming(QCQP) problem. We first generalize a known result for the rank-one decomposition of matrices and then apply it to consider the strong duality for more general QCQP scenarios, including the cases with one constraint, two constraints while at least one being inactive on the optimal solution point, multiple constraints, and an interval constraint. A sufficient condition ensuring the strong duality of more general QCQP problems is studied as well. We also extend our results to the QCQP problems with complex variables.
引文
[1] Ai W, Huang Y and Zhang S. New results on Hermitian matrix rank-one decomposition. Math.Program., 2011, 128(1):253-283.
[2] Beck A. Quadratic matrix programming. SIAM J. Optim., 2007, 17(4):1224-1238
[3] Ben-Tal A and Nemirovskii A. Lectures on Modern Convex Optimization:Analysis Algorithms,and Engineering Applications. Philadelphia,PA:MPS-,SIAM., 2001.
[4] Boyd S and Vandenberghe L. Convex Optimization. Cambridge University Press,(2004).
[5] He S, Wong M H and Zhang S. On the S-Lemma for univariate polynomials. Preprint.
[6] Huang Y, Maio A De and Zhang S. Semidefinite programming, matrix decomposition, and radar code design. Convex Optimization in Signal Processing and Communications, Cambridge University Press,(2009), 192-228.
[7] Luo Z.-Q Sturm J F and Zhang S. Multivariate nonnegative quadratic mappings. SIAM J.Optim.,2004, 14:1140-1162.
[8] Pataki G. The geometry of semidefinite programming, in Handbook of Semidefinite Programming. Interat. Ser. Oper. Res. Management Sci.27, Kluwer Academic Publishers, Boston,2000, 29-65.
[9] P'olik I and Terlaky T. A Survey of the S-Lemma. SIAM Review 2007, 49(3):371-418.
[10] Pong T and Wolkowicz H. Generalizations of the trust region subproblem. Comput. Optim.Appl., 2014, 58(2):273-322.
[11] Sturm J F and Zhang S. On cones of nonnegative quadratic functions. Math. Oper. Res.,2003, 28:246-267.
[12] Wang S and Xia Y. Strong duality for generalized trust region subproblem:S-Lemma with Interval Bounds. Optim. Lett., 2015. 9(6):1063-1073.
[13] Xia Y, Wang S and Sheu R L. The S-lemma with equality and its applications. Math. Prog.,2016, 156(1-2):513-547.
[14] Yakubovich V A. S-procedure in nonlinear control theory. Vestnik Leningrad. Univ., 1977, 4:73-93.
[15] Ye Y and Zhang S. New results on quadratic minimization. SIAM J. Optim., 2001, 14(1):,245-267.
[16] Zhang S and Huang Y. Complex quadrayic optimization and semidefinite programming. SIAM J. Optim., 2006, 16:871-890.
[17] Huang Y and Zhang S. Complex matrix decomposition and quadratic programming. Math.Ope. Res., 2007, 32:758-768.