Strong duality in Lasserre's hierarchy for polynomial optimization

详细信息    查看全文

• 作者：Cédric Josz ; Didier Henrion
• 关键词：Polynomial optimization ; Semidefinite programming ; Lasserre hierarchy ; Slater condition
• 刊名：Optimization Letters
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：10
• 期：1
• 页码：3-10
• 全文大小：364 KB
• 参考文献：1.de Klerk, E., Terlaky, T., Roos, K.: Self-dual embeddings. In: Wolkowicz, H., Saigal, R., Vandenberghe, L. (eds.) Handbook of Semidefinite Programming. Theory, Algorithms, and Applications. Kluwer, Boston (2000)
  2.Henrion, D., Lasserre, J.B.: Detecting global optimality and extracting solutions in GloptiPoly. In: Henrion, D., Garulli A. (eds.). Positive Polynomials in Control. Lecture Notes on Control and Information Sciences, vol. 312. Springer, Berlin (2005)
  3.Henrion, D., Lasserre, J.B.: Inner approximations for polynomial matrix inequalities and robust stability regions. IEEE Trans. Autom. Control 57(6), 1456–1467 (2012)MathSciNet CrossRef
  4.Lasserre, J.B.: Optimisation globale et théorie des moments. C. R. Acad. Sci. Paris Sér. I 331, 929–934 (2000)MathSciNet CrossRef MATH
  5.Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11, 796–817 (2001)MathSciNet CrossRef MATH
  6.Nie, J.: Optimality conditions and finite convergence of Lasserre’s hierarchy. Math. Program. Ser. A 146, 97–121 (2014)CrossRef MATH
  7.Schweighofer, M.: Optimization of polynomials on compact semialgebraic sets. SIAM J. Optim. 15, 805–825 (2005)MathSciNet CrossRef MATH
  8.Shapiro, A., Scheinber, K.: Duality, optimality conditions and perturbation analysis. In: Wolkowicz, H., Saigal, R., Vandenberghe, L. (eds.) Handbook of Semidefinite Programming. Theory, Algorithms, and Applications. Kluwer, Boston (2000)
  9.Trnovská, M.: Strong duality conditions in semidefinite programming. J. Electr. Eng. 56, 1–5 (2005)
  10.Waki, H., Nakata, M., Muramatsu, M.: Strange behaviors of interior-point methods for solving semidefinite programming problems in polynomial optimization. Comput. Optim. Appl. 53(3), 823–844 (2012)MathSciNet CrossRef MATH
  
• 作者单位：Cédric Josz (1) (2)
  Didier Henrion (3) (4) (5)
  
  1. French transmission system operator Réseau de Transport d’Electricité (RTE), 9 rue de la Porte de Buc, BP 561, 78000, Versailles, France
  2. INRIA Paris-Rocquencourt, BP 105, 78153, Le Chesnay, France
  3. LAAS, CNRS, 7 avenue du colonel Roche, 31400, Toulouse, France
  4. LAAS, Université de Toulouse, 31400, Toulouse, France
  5. Faculty of Electrical Engineering, Czech Technical University in Prague, Technická 2, 16626, Prague, Czech Republic
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Optimization
  Operation Research and Decision Theory
  Numerical and Computational Methods in Engineering
  Numerical and Computational Methods
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1862-4480

文摘

A polynomial optimization problem (POP) consists of minimizing a multivariate real polynomial on a semi-algebraic set \(K\) described by polynomial inequalities and equations. In its full generality it is a non-convex, multi-extremal, difficult global optimization problem. More than an decade ago, J. B. Lasserre proposed to solve POPs by a hierarchy of convex semidefinite programming (SDP) relaxations of increasing size. Each problem in the hierarchy has a primal SDP formulation (a relaxation of a moment problem) and a dual SDP formulation (a sum-of-squares representation of a polynomial Lagrangian of the POP). In this note, we show that there is no duality gap between each primal and dual SDP problem in Lasserre’s hierarchy, provided one of the constraints in the description of set \(K\) is a ball constraint. Our proof uses elementary results on SDP duality, and it does not assume that \(K\) has a strictly feasible point.