×

zbMATH — the first resource for mathematics

Certifying convergence of Lasserre’s hierarchy via flat truncation. (English) Zbl 1305.65151
In this paper, the author presents a new typical approach for solving the optimization of minimizing a polynomial optimization subject to polynomial constraints. The certificate for checking finite and asymptotical convergence of Lassees’s hierarchy based on either Putinar’s or Schmudgens’s Positivstellensatz is established. The author also proves that flat truncation can be used as a certificate to check exactness of standard SOS relaxations and Jacobin SDP relaxations.

MSC:
65K05 Numerical mathematical programming methods
90C22 Semidefinite programming
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Bochnak, J., Coste, M., Roy, M.-F.: Real Algebraic Geometry. Springer, Berlin (1998) · Zbl 0912.14023
[2] Conway, J.B.: A Course in Functional Analysis. Springer, Berlin (1990) · Zbl 0706.46003
[3] Curto, R; Fialkow, L, Truncated K-moment problems in several variables, J. Oper. Theory, 54, 189-226, (2005) · Zbl 1119.47304
[4] Helton, J.W., Nie, J.: A semidefinite approach for truncated K-moment problem, (2011). [Preprint] · Zbl 1259.44005
[5] Henrion, D., Lasserre, J.: Detecting global optimality and extracting solutions in GloptiPoly. In: Positive Polynomials in Control. Lecture Notes in Control and Information Science vol. 312, pp. 293-310. Springer, Berlin (2005) · Zbl 1119.93301
[6] Henrion, D., Lasserre, J., Loefberg, J.: GloptiPoly 3: moments, optimization and semidefinite programming. Optim. Methods Softw. 24(4-5), 761-779 (2009) · Zbl 1178.90277
[7] Lasserre, JB; Laurent, M; Rostalski, P, Semidefinite characterization and computation of zero-dimensional real radical ideals, Found. Comput. Math., 8, 607-647, (2008) · Zbl 1176.14010
[8] Lasserre, JB, Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11, 796-817, (2001) · Zbl 1010.90061
[9] Lasserre, J.B.: Moments, Positive Polynomials and Their Applications. Imperial College Press, London (2009)
[10] Laurent, M, Semidefinite representations for finite varieties, Math. Program., 109, 1-26, (2007) · Zbl 1152.90007
[11] Laurent, M; Putinar, M (ed.); Sullivant, S (ed.), Sums of squares, moment matrices and optimization over polynomials, 157-270, (2009), Berlin · Zbl 1163.13021
[12] Nie, J; Demmel, J; Sturmfels, B, Minimizing polynomials via sum of squares over the gradient ideal, Math. Program. Ser. A, 106, 587-606, (2006) · Zbl 1134.90032
[13] Nie, J; Schweighofer, M, On the complexity of putinar’s positivstellensatz, J. Complex., 23, 135-150, (2007) · Zbl 1143.13028
[14] Nie, J; Ranestad, K, Algebraic degree of polynomial optimization, SIAM J. Optim., 20, 485-502, (2009) · Zbl 1190.14051
[15] Nie, J.: An exact Jacobian SDP relaxation for polynomial optimization. Math. Program. Ser. A (to appear) · Zbl 1266.65094
[16] Parrilo, PA; Sturmfels, B; Basu, S (ed.); Gonzalez-Vega, L (ed.), Minimizing polynomial functions, 83-99, (2003), Providence · Zbl 1099.13516
[17] Putinar, M, Positive polynomials on compact semi-algebraic sets, Ind. Univ. Math. J., 42, 969-984, (1993) · Zbl 0796.12002
[18] Scheiderer, C, Sums of squares of regular functions on real algebraic varieties, Trans. Am. Math. Soc., 352, 1039-1069, (1999) · Zbl 0941.14024
[19] Schmüdgen, K, The K-moment problem for compact semialgebraic sets, Math. Ann., 289, 203-206, (1991) · Zbl 0744.44008
[20] Schweighofer, M, Optimization of polynomials on compact semialgebraic sets, SIAM J. Optim., 15, 805-825, (2005) · Zbl 1114.90098
[21] Sturm, JF, Sedumi 1.02: A MATLAB toolbox for optimization over symmetric cones, Optim. Methods Softw., 11&12, 625-653, (1999) · Zbl 0973.90526
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.