×

A multilevel analysis of the Lasserre hierarchy. (English) Zbl 1430.90456

Summary: This paper analyzes the relation between different orders of the Lasserre hierarchy for polynomial optimization (POP). Although for some cases solving the semidefinite programming relaxation corresponding to the first order of the hierarchy is enough to solve the underlying POP, other problems require sequentially solving the second or higher orders until a solution is found. For these cases, and assuming that the lower order semidefinite programming relaxation has been solved, we develop prolongation operators that exploit the solutions already calculated to find initial approximations for the solution of the higher order relaxation. We can prove feasibility in the higher order of the hierarchy of the points obtained using the operators, as well as convergence to the optimal as the relaxation order increases. Furthermore, the operators are simple and inexpensive for problems where the projection over the feasible set is “easy” to calculate (for example integer \(\{0, 1\}\) and \(\{- 1, 1 \}\) POPs). Our numerical experiments show that it is possible to extract useful information for real applications using the prolongation operators. In particular, we illustrate how the operators can be used to increase the efficiency of an infeasible interior point method by using them as an initial point. We use this technique to solve quadratic integer \(\{0, 1\}\) problems, as well as MAX-CUT and integer partition problems.

MSC:

90C22 Semidefinite programming
90C26 Nonconvex programming, global optimization
90C20 Quadratic programming

References:

[1] Ahmadi, A. A., & Majumdar, A. (2017). DSOS and SDSOS optimization: More tractable alternatives to sum of squares and semidefinite optimization. arXiv:1706.02586; Ahmadi, A. A., & Majumdar, A. (2017). DSOS and SDSOS optimization: More tractable alternatives to sum of squares and semidefinite optimization. arXiv:1706.02586
[2] Benson, H. Y.; Shanno, D. F., An exact primal-dual penalty method approach to warmstarting interior-point methods for linear programming, Computational Optimization and Applications, 38, 3, 371-399 (2007) · Zbl 1171.90546
[3] Boukouvala, F.; Misener, R.; Floudas, C. A., Global optimization advances in mixed-integer nonlinear programming, MINLP, and constrained derivative-free optimization, CDFO, European Journal of Operational Research, 252, 3, 701-727 (2016) · Zbl 1346.90677
[4] Burer, S.; Monteiro, R., A nonlinear programming algorithm for solving semidefinite programming via low-rank factorization, Mathematical Programming (series B), 95, 329-357 (2003) · Zbl 1030.90077
[5] Campos, J. S.; Parpas, P., A multigrid approach to SDP relaxations of sparse polynomial optimization problems, SIAM Journal on Optimization, 28, 1, 1-29 (2018) · Zbl 1398.90118
[6] Caprara, A., Constrained 0-1 quadratic programming: Basic approaches and extensions, European Journal of Operational Research, 187, 3, 1494-1503 (2008) · Zbl 1138.90455
[7] van Dam, E. R.; Sotirov, R., Semidefinite programming and eigenvalue bounds for the graph partition problem, Mathematical Programming, 151, 2, 379-404 (2015) · Zbl 1328.90103
[8] de Klerk, E., Exploiting special structure in semidefinite programming: A survey of theory and applications, European Journal of Operational Research, 201, 1, 1-10 (2010) · Zbl 1177.90315
[9] De Klerk, E.; Laurent, M., On the lasserre hierarchy of semidefinite programming relaxations of convex polynomial optimization problems, SIAM Journal on Optimization, 21, 3, 824-832 (2011) · Zbl 1230.90199
[10] Lasserre, J. B., Global optimization with polynomials and the problem of moments, SIAM Journal on Optimization, 11, 3, 796-817 (2001) · Zbl 1010.90061
[11] Lasserre, J. B., An explicit equivalent positive semidefinite program for nonlinear 0-1 programs, SIAM Journal on Optimization, 12, 3, 756-769 (2002) · Zbl 1007.90046
[12] Lasserre, J. B., Convergent SDP-relaxations in polynomial optimization with sparsity, SIAM Journal on Optimization, 17, 3, 822-843 (2006) · Zbl 1119.90036
[13] Lasserre, J. B., Convexity in semialgebraic geometry and polynomial optimization, SIAM Journal on Optimization, 19, 4, 1995-2014 (2009) · Zbl 1181.90216
[14] Lasserre, J. B., A MAX-CUT formulation of 0/1 programs, Operations Research Letters, 44, 2, 158-164 (2016) · Zbl 1408.90222
[15] Lasserre, J. B.; Toh, K.-C.; Yang, S., A bounded degree SOS hierarchy for polynomial optimization, EURO Journal on Computational Optimization, 5, 1-2, 87-117 (2017) · Zbl 1368.90132
[16] Nie, J., Optimality conditions and finite convergence of lasserres hierarchy, Mathematical programming, 146, 1-2, 97-121 (2014) · Zbl 1300.65041
[17] Rendl, F.; Rinaldi, G.; Wiegele, A., Solving max-cut to optimality by intersecting semidefinite and polyhedral relaxations, Mathematical Programming, 121, 2, 307 (2010) · Zbl 1184.90118
[18] Schweighofer, M., Optimization of polynomials on compact semialgebraic sets, SIAM Journal on Optimization, 15, 3, 805-825 (2005) · Zbl 1114.90098
[19] Skajaa, A.; Andersen, E. D.; Ye, Y., Warmstarting the homogeneous and self-dual interior point method for linear and conic quadratic problems, Mathematical Programming Computation, 5, 1, 1-25 (2013) · Zbl 1269.90080
[20] Sturm, J. F., Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optimization Methods and Software, 11, 1-4, 625-653 (1999) · Zbl 0973.90526
[21] Toh, K.-C.; Todd, M. J.; Tütüncü, R. H., On the implementation and usage of SDPT3-a MATLAB software package for semidefinite-quadratic-linear programming, version 4.0, Handbook on semidefinite, conic and polynomial optimization, 715-754 (2012), Springer · Zbl 1334.90117
[22] Waki, H.; Kim, S.; Kojima, M.; Muramatsu, M., Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity, SIAM Journal on Optimization, 17, 1, 218-242 (2006) · Zbl 1109.65058
[23] Waki, H.; Kim, S.; Kojima, M.; Muramatsu, M.; Sugimoto, H., Algorithm 883: SparsePOP—A sparse semidefinite programming relaxation of polynomial optimization problems, ACM Transactions on Mathematical Software, 35, 2, 15 (2008)
[24] Weisser, T.; Lasserre, J. B.; Toh, K.-C., Sparse-BSOS: A bounded degree SOS hierarchy for large scale polynomial optimization with sparsity, Mathematical Programming Computation (2017)
[25] Wen, Z.; Goldfarb, D.; Yin, W., Alternating direction augmented Lagrangian methods for semidefinite programming, Mathematical Programming Computation, 2, 203-230 (2010) · Zbl 1206.90088
[26] Yang, L.; Sun, D.; Toh, K.-C., SDPNAL+: A majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints, Mathematical Programming Computation, 7, 3, 331-366 (2015) · Zbl 1321.90085
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.