×

Optimality conditions and finite convergence of Lasserre’s hierarchy. (English) Zbl 1300.65041

This paper studies the relationship between the classic nonlinear programming theory and Lasserre’s hierarchy of semidefinite relaxations in polynomial optimization. Under some mild conditions, the author proves that Lasserre’s hierarchy has finite convergence.

MSC:

65K05 Numerical mathematical programming methods
90C22 Semidefinite programming
90C26 Nonconvex programming, global optimization

Software:

SeDuMi; GloptiPoly
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bertsekas, D.: Nonlinear Programming, 2nd edn. Athena Scientific, Belmont (1995) · Zbl 0935.90037
[2] Bochnak, J., Coste, M., Roy, M.-F.: Real Algebraic Geometry. Springer, New York (1998) · Zbl 0912.14023 · doi:10.1007/978-3-662-03718-8
[3] Cox, D., Little, J., O’Shea, D.: Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Third edition. Undergraduate Texts in Mathematics. Springer, New York (1997)
[4] Cox, D., Little, J., O’Shea, D.: Using Algebraic Geometry. Graduate Texts in Mathematics, vol. 185. Springer, New York (1998) · Zbl 0920.13026 · doi:10.1007/978-1-4757-6911-1
[5] Gelfand, I., Kapranov, M., Zelevinsky, A.: Discriminants, resultants, and multidimensional determinants. Mathematics: Theory & Applications, Birkhäuser (1994) · Zbl 0827.14036
[6] Hartshorne, R.: Algebraic Geometry. Graduate Texts in Mathematics, vol. 52. Springer, New York (1977) · Zbl 0367.14001 · doi:10.1007/978-1-4757-3849-0
[7] Henrion, D., Lasserre, J., Loefberg, J.: GloptiPoly 3: moments, optimization and semidefinite programming. http://homepages.laas.fr/henrion/software/gloptipoly3 · Zbl 1178.90277
[8] Henrion, D., Lasserre, J.B.: GloptiPoly: global optimization over polynomials with Matlab and SeDuMi. ACM Trans. Math. Soft. 29, 165-194 (2003) · Zbl 1070.65549 · doi:10.1145/779359.779363
[9] Henrion, D., Lasserre, J.B.: Detecting global optimality and extracting solutions in GloptiPoly. Positive polynomials in control. Lecture Notes in Control and Information Science, vol. 312, pp. 293-310, Springer, Berlin (2005) · Zbl 1119.93301
[10] Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3), 796-817 (2001) · Zbl 1010.90061 · doi:10.1137/S1052623400366802
[11] Lasserre, J.B.: Moments, Positive Polynomials and Their Applications. Imperial College Press, London (2009) · doi:10.1142/p665
[12] Laurent, M.: Semidefinite representations for finite varieties. Math. Program. 109, 1-26 (2007) · Zbl 1152.90007 · doi:10.1007/s10107-004-0561-4
[13] Laurent, M.; Putinar, M. (ed.); Sullivant, S. (ed.), Sums of squares, moment matrices and optimization over polynomials, No. 149, 157-270 (2009), Berlin · Zbl 1163.13021 · doi:10.1007/978-0-387-09686-5_7
[14] Marshall, M.: Representation of non-negative polynomials with finitely many zeros. Annales de la Faculte des Sciences Toulouse 15, 599-609 (2006) · Zbl 1130.13015 · doi:10.5802/afst.1131
[15] Marshall, M.: Positive Polynomials and Sums of Squares Mathematical Surveys and Monographs, vol. 146. American Mathematical Society, Providence (2008) · doi:10.1090/surv/146
[16] Marshall, M.: Representation of non-negative polynomials, degree bounds and applications to optimization. Canad. J. Math. 61, 205-221 (2009) · Zbl 1163.13019 · doi:10.4153/CJM-2009-010-4
[17] Nie, J., Ranestad, K.: Algebraic degree of polynomial optimization. SIAM J. Optim. 20(1), 485-502 (2009) · Zbl 1190.14051 · doi:10.1137/080716670
[18] Nie, J.: Discriminants and nonnegative polynomials. J. Symb. Comput. 47(2), 167-191 (2012) · Zbl 1245.14061 · doi:10.1016/j.jsc.2011.08.023
[19] Nie, J.: An exact Jacobian SDP relaxation for polynomial optimization. Math. Program. Ser. A 137, 225-255 (2013) · Zbl 1266.65094 · doi:10.1007/s10107-011-0489-4
[20] Nie, J.: Certifying convergence of Lasserre’s hierarchy via flat truncation. Mathematical Programming, to appear · Zbl 1305.65151
[21] Nie, J.: Polynomial optimization with real varieties. Preprint (2012) · Zbl 1286.65079
[22] Putinar, M.: Positive polynomials on compact semi-algebraic sets. Ind. Univ. Math. J. 42, 969-984 (1993) · Zbl 0796.12002 · doi:10.1512/iumj.1993.42.42045
[23] Reznick, B.: Some Concrete Aspects of Hilbert’s 17th problem. In: Contemp. Math., vol. 253, pp. 251-272. American Mathematical Society, Providence (2000) · Zbl 0972.11021
[24] Scheiderer, C.: Non-existence of degree bounds for weighted sums of squares representations. J. Complex. 21, 823-844 (2005) · Zbl 1093.13024
[25] Scheiderer, C.: Distinguished representations of non-negative polynomials. J. Algebra 289, 558-573 (2005) · Zbl 1082.14058 · doi:10.1016/j.jalgebra.2005.01.043
[26] Scheiderer, C.: Sums of squares of regular functions on real algebraic varieties. Trans. Am. Math. Soc. 352, 1039-1069 (1999) · Zbl 0941.14024 · doi:10.1090/S0002-9947-99-02522-2
[27] Scheiderer, C.: Positivity and sums of squares: a guide to recent results. In: Putinar, M., Sullivant, S. (eds.) Emerging Applications of Algebraic Geometry, in: IMA Volumes Math. Appl., vol. 149, pp. 271-324. Springer, New York (2009) · Zbl 1156.14328
[28] Sturmfels, B.: Solving Systems of Polynomial Equations. CBMS Regional Conference Series in Mathematics, vol. 97. American Mathematical Society, Providence (2002) · Zbl 1101.13040
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.