×

zbMATH — the first resource for mathematics

A new bounded degree hierarchy with SOCP relaxations for global polynomial optimization and conic convex semi-algebraic programs. (English) Zbl 1433.90122
Summary: In this paper, we propose a bounded degree hierarchy of both primal and dual conic programming relaxations involving both semi-definite and second-order cone constraints for solving a nonconvex polynomial optimization problem with a bounded feasible set. This hierarchy makes use of some key aspects of the convergent linear programming relaxations of polynomial optimization problems [J. B. Lasserre, Moments, positive polynomials and their applications. London: Imperial College Press (2010; Zbl 1211.90007)] associated with Krivine-Stengle’s certificate of positivity in real algebraic geometry and some advantages of the scaled diagonally dominant sum of squares (SDSOS) polynomials, cf. ([A. A. Ahmadi and G. Hall, “On the construction of converging hierarchies for polynomial optimization basedon certificates of global positivity”, arXiv:1709.09307]; [A. A. Ahmadi and A. Majumdar, SIAM J. Appl. Algebra Geom. 3, No. 2, 193–230 (2019; Zbl 07067257)]). We show that the values of both primal and dual relaxations converge to the global optimal value of the original polynomial optimization problem under some technical assumptions. Our hierarchy, which extends the so-called bounded degree Lasserre hierarchy [J. B. Lasserre et al., EURO J. Comput. Optim. 5, No. 1–2, 87–117 (2017; Zbl 1368.90132)], has a useful feature that the size and the number of the semi-definite and second-order cone constraints of the relaxations are fixed and independent of the step or level of the approximation in the hierarchy. As a special case, we provide a convergent bounded degree second-order cone programming (SOCP) hierarchy for solving polynomial optimization problems. We then present finite convergence at step one of the SOCP hierarchy for classes of polynomial optimization problems. This includes one-step convergence for a new class of first-order SDSOS-convex polynomial programs. In this case, we also show how a global solution is recovered from the level one SOCP relaxation. We finally derive a corresponding convergent conic linear programming hierarchy for conic-convex semi-algebraic programs. Whenever the semi-algebraic set of the conic-convex program is described by concave polynomial inequalities, we show further that the values of the relaxation problems converge to the common value of the convex program and its Lagrangian dual under a constraint qualification.
MSC:
90C26 Nonconvex programming, global optimization
90C22 Semidefinite programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ahmadi, AA; Hall, G., On the construction of converging hierarchies for polynomial optimization based on certificates of global positivity, Math. Oper. Res. (2019)
[2] Ahmadi, AA; Majumdar, A., DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization, SIAM J. Appl. Algebra Geom., 3, 193-230 (2019) · Zbl 07067257
[3] Ahmadi, AA; Parrilo, PA, A complete characterization of the gap between convexity and SOS-convexity, SIAM J. Optim., 23, 811-833 (2013) · Zbl 1295.52009
[4] Belousov, EG; Klatte, D., A Frank-Wolfe type theorem for convex polynomial programs, Comput. Optim. Appl., 22, 37-48 (2002) · Zbl 1029.90054
[5] Bertsimas, D.; Freund, RM; Sun, XA, An accelerated first-order method for solving SOS relaxations of unconstrained polynomial optimization problems, Optim. Methods Softw., 28, 424-441 (2013) · Zbl 1273.90198
[6] Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004) · Zbl 1058.90049
[7] Chuong, TD; Jeyakumar, V., Convergent conic linear programming relaxations for cone convex polynomial programs, Oper. Res. Lett., 45, 220-226 (2017) · Zbl 1409.90131
[8] Chuong, TD; Jeyakumar, V., Generalized Lagrangian duality for nonconvex polynomial programs with polynomial multipliers, J. Global Optim., 72, 655-678 (2018) · Zbl 1433.90158
[9] D’Angelo, P., Putinar, M.: Polynomial Optimization on Odd-Dimensional Spheres, in Emerging Applications of Algebraic Geometry. Springer, New York (2008)
[10] Fidalgo, C.; Kovacec, A., Positive semidefinite diagonal minus tail forms are sums of squares, Math. Z., 269, 629-645 (2011) · Zbl 1271.11045
[11] Floudas, C.A., Pardalos, P.M., Adjiman, C.S., Esposito, W.R., Gumus, Z.H., Harding, S.T., Klepeis, J.L., Meyer, C.A., Schweiger, C.A.: Handbook of Test Problems in Local and Global Optimization. Kluwer Academic Publishers, Dordrecht (1999)
[12] Ghaddar, B.; Vera, JC; Anjos, MF, A dynamic inequality generation scheme for polynomial programming, Math. Program., 156, 21-57 (2016) · Zbl 1342.90143
[13] Ghasemi, M.; Marshall, M., Lower bounds for polynomials using geometric programming, SIAM J. Optim., 22, 460-473 (2012) · Zbl 1272.12004
[14] Henrion, D.; Lasserre, JB; Loefberg, J., GloptiPoly 3: moments, optimization and semidefinite programming, Optim. Methods Softw., 24, 761-779 (2009) · Zbl 1178.90277
[15] Horn, R., Johnson, C.R.: Matrix Analysis, 2nd edn, p. xviii+643. Cambridge University Press, Cambridge (2013) · Zbl 1267.15001
[16] Hu, S.; Li, G.; Qi, L., A tensor analogy of Yuan’s theorem of the alternative and polynomial optimization with sign structure, J. Optim. Theory Appl., 168, 446-474 (2016) · Zbl 1338.90317
[17] Helton, JW; Nie, JW, Semidefinite representation of convex sets, Math. Program., 122, 21-64 (2010) · Zbl 1192.90143
[18] Jeyakumar, V., Constraint qualifications characterizing Lagrangian duality in convex optimization, J. Optim. Theory Appl., 136, 31-41 (2008) · Zbl 1194.90069
[19] Jeyakumar, V.; Lee, GM; Li, G., Alternative theorems for quadratic inequality systems and global quadratic optimization, SIAM J. Optim., 2, 667-690 (2009) · Zbl 1197.90315
[20] Jeyakumar, V.; Li, G., Exact conic programming relaxations for a class of convex polynomial cone programs, J. Optim. Theory Appl., 172, 156-178 (2017) · Zbl 1388.90093
[21] Jeyakumar, V.; Kim, S.; Lee, GM; Li, G., Solving global optimization problems with sparse polynomials and unbounded semialgebraic feasible sets, J. Global Optim., 65, 175-190 (2016) · Zbl 1369.90136
[22] Josa, C.; Molzahn, D., Lasserre hierarchy for large scale polynomial optimization in real and complex variables, SIAM J. Optim., 28, 1017-1048 (2018) · Zbl 1395.90196
[23] Krivine, JL, Anneaux préordonnés, J. Anal. Math., 12, 307-326 (1964) · Zbl 0134.03902
[24] Kim, S.; Kojima, M., Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxations, Comput. Optim. Appl., 26, 143-154 (2003) · Zbl 1043.90060
[25] Kuang, X.; Ghaddar, B.; Naoum-Sawaya, J.; Zuluaga, LF, Alternative SDP and SOCP approximations for polynomial optimization, Eur. J. Comp. Optim., 7, 153-175 (2019)
[26] Lasserre, JB, A Lagrangian relaxation view of linear and semidefinite hierarchies, SIAM J. Optim, 23, 1742-1756 (2013) · Zbl 1282.90139
[27] Lasserre, J.B.: Moments, Positive Polynomials and Their Applications. World Scientific, Singapore (2010) · Zbl 1211.90007
[28] Lasserre, JB, Representation of nonnegative convex polynomial, Arch. Math., 91, 126-130 (2008) · Zbl 1159.14033
[29] 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
[30] Lasserre, JB; Toh, KC; Yang, S., A bounded degree SOS hierarchy for polynomial optimization, Eur. J. Comput. Optim., 5, 87-117 (2017) · Zbl 1368.90132
[31] Mordukhovich, B.S., Nam, N.M.: An Easy Path to Convex Analysis and Applications, Synthesis Lectures on Mathematics and Statistics, 14. Morgan & Claypool Publishers, Williston (2014)
[32] Megretski, A.: SPOT (Systems polynomial optimization tools) Manual, 2010, http://web.mit.edu/ameg/www/images/spot_manual.pdf
[33] Nie, JW, Polynomial matrix inequality and semidefinite representation, Math. Oper. Res., 36, 398-415 (2011) · Zbl 1244.90180
[34] Nie, JW; Wang, L., Regularization methods for SDP relaxations in large-scale polynomial optimization, SIAM J. Optim., 22, 408-428 (2012) · Zbl 1250.65080
[35] Parrilo, PA, Semidefinite programming relaxations for semialgebraic problems, Math. Program., 96, 293-320 (2003) · Zbl 1043.14018
[36] Shapiro, A., First and second order analysis of nonlinear semidefinite programs, Math. Program., 77, 301-320 (1997) · Zbl 0888.90127
[37] Waki, H.; Kim, S.; Kojima, M.; Muramatsu, M., Sums of squares and semidefinite programming relaxations for polynomial optimization problems with structured sparsity, SIAM J. Optim., 17, 218-242 (2006) · Zbl 1109.65058
[38] Weisser, T.; Lasserre, J.; Toh, K., Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity, Math. Program. Comput., 5, 1-32 (2017) · Zbl 1402.90136
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.