On the hardness of deciding the finite convergence of Lasserre hierarchies

Luis Felipe Vargas

doi:10.3934/naco.2024024

Article Contents

2026, Volume 16: 35-48. Doi: 10.3934/naco.2024024

This volume Previous Article Moment-SOS hierarchy and exit location of stochastic processes Next Article Nonconvergence of a sum-of-squares hierarchy for global polynomial optimization based on push-forward measures

On the hardness of deciding the finite convergence of Lasserre hierarchies

Luis Felipe Vargas

Istituto Dalle Molle di Studi sull'Intelligenza Artificiale, (IDSIA USI-SUPSI), Switzerland

Received: January 2024

Revised: May 2024

Early access: June 12, 2024

Published online: June 12, 2024

The author is supported by [European Union's Framework Programme for Research and Innovation Horizon 2020 under the Marie Skłodowska-Curie Actions Grant Agreement No. 813211 (POEMA) and by the Swiss National Science Foundation project n. 200021_207429 / 1 "Ideal Membership Problems and the Bit Complexity of Sum of Squares Proofs"].

Abstract / Introduction Full Text(HTML) Related Papers Cited by

Abstract

A polynomial optimization problem (POP) asks for minimizing a polynomial function given a finite set of polynomial constraints (equations and inequalities). This problem is well-known to be hard in general, as it encodes many hard combinatorial problems. The Lasserre hierarchy is a sequence of semidefinite relaxations for solving (POP). Under the standard Archimedean condition, this hierarchy is guaranteed to converge asymptotically to the optimal value of (POP) (Lasserre, 2001) and, moreover, finite convergence holds generically (Nie, 2012). In this paper, we aim to investigate whether there is an efficient algorithmic procedure to decide whether the Lasserre hierarchy of (POP) has finite convergence. We show that unless P = NP there cannot exist such an algorithmic procedure that runs in polynomial time. We show this already for the standard quadratic programs. Our approach relies on characterizing when finite convergence holds for the so-called Motzkin-Straus formulation (and some variations of it) for the stability number of a graph.

Keywords:

Mathematics Subject Classification: Primary: 90C23, 90c20, 68Q17, 11E25.

Citation:

Full Text(HTML)

Related Papers

Cited by

References

[1]	A. Ahmadi and J. Zhang, On the complexity of finding a local minimizer of a quadratic function over a polytope, Mathematical Programming, 196 (2022), 783-792. doi: 10.1007/s10107-021-01714-2.
[2]	A. Ahmadi and J. Zhang, Complexity aspects of local minima and related notions, Advances in Mathematics, 397 (2022), Article ID: 108119. doi: 10.1016/j.aim.2021.108119.
[3]	D. P. Bertsekas, Nonlinear Programming, Athena Scientific, Belmont, MA, 1999.
[4]	I. Bomze and E. de Klerk, Solving standard quadratic optimization problems via linear, semidefinite and copositive programming, Journal of Global Optimization, 24 (2002), 163-185. doi: 10.1023/A:1020209017701.
[5]	L. E. Gibbons, D. W. Hearn, P. M. Pardalos and M. V. Ramana, Continuous characterizations of the maximum clique problem, Mathematics of Operations Research, 22 (1997), 754-768. doi: 10.1287/moor.22.3.754.
[6]	D. Henrion and J. B. Lasserre, GloptiPoly: global optimization over polynomials with Matlab and SeDuMi, ACM Trans. Math. Soft., 29 (2003), 165-194. doi: 10.1145/779359.779363.
[7]	D. Henrion and J. B. Lasserre, Detecting global optimality and extracting solutions in GloptiPoly, Positive Polynomials in Control. Lecture Notes in Control and Information Science, 312 (2005), 293-310, Springer, Berlin. doi: 10.1007/10997703_15.
[8]	R. Karp, Reducibility Among Combinatorial Problems, Plenum Press, New York, 1972.
[9]	E. de Klerk and D. Pasechnik, Approximation of the stability number of a graph via copositive programming, SIAM Journal on Optimization, 12 (2002), 875-892. doi: 10.1137/S1052623401383248.
[10]	T. -L. Kriel and M. Schweighofer, On the exactness of Lasserre relaxations and pure states over real closed fields, Foundations of Computational Mathematics, 19 (2018), 1223-1263. doi: 10.1007/s10208-018-9406-z.
[11]	T. -L. Kriel and M. Schweighofer, On the exactness of Lasserre relaxations for compact convex basic closed semialgebraic sets, SIAM Journal of Optimization, 28 (2018), 1796-1816. doi: 10.1137/17M1128290.
[12]	J. B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM Journal on Optimization, 11 (2001), 796-817. doi: 10.1137/S1052623400366802.
[13]	J. B. Lasserre, Moments, Positive Polynomials and Their Applications, Imperial College Press, 2009.
[14]	M. Laurent, Semidefinite representations for finite varieties, Mathematical Programming, 109 (2007), 1-26. doi: 10.1007/s10107-004-0561-4.
[15]	M. Laurent, Sums of squares, moment matrices and optimization over polynomials, in Emerging Applications of Algebraic Geometry, IMA Vol. Math. Appl. 149, M. Putinar and S. Sullivant, eds., Springer, Cham, (2009), 157-270. doi: 10.1007/978-0-387-09686-5_7.
[16]	M. Laurent and L. F. Vargas, Finite convergence of sum-of-squares hierarchies for the stability number of a graph, SIAM J. Optim., 32 (2022), 491-518. doi: 10.1137/21M140345X.
[17]	M. Marshall, Optimization of polynomial functions, Canad. Math. Bull., 46 (2003), 575-587. doi: 10.4153/CMB-2003-054-7.
[18]	M. Marshall, Representations of non-negative polynomials having finitely many zeros, Annales de la faculté des sciences de Toulouse Mathématiques, 15, 599-609.
[19]	T. S. Motzkin and E. G. Straus, Maxima for graphs and a new proof of a theorem of Turán, Canadian J. Math., 17 (1965), 533-540. doi: 10.4153/CJM-1965-053-6.
[20]	K. G. Murty and S.N. Kabadi, Some NP-complete problems in quadratic and nonlinear programming, Math. Programming, 39 (1987), 117-129. doi: 10.1007/BF02592948.
[21]	J. Nie, Optimality conditions and finite convergence of Lasserre's hierarchy, Mathematical Programming, 146 (2012), 97-121. doi: 10.1007/s10107-013-0680-x.
[22]	J. Nie., Polynomial optimization with real varieties., SIAM Journal on Optimization, 23 (2013), 1634-1646. doi: 10.1137/120898772.
[23]	M. Putinar, Positive polynomials on compact semi-algebraic sets, Ind. Univ. Math. J., 42 (1993), 969-984. doi: 10.1512/iumj.1993.42.42045.
[24]	C. Scheidere, Distinguished representations of non-negative polynomials, J. Algebra, 289 (2005), 558-573. doi: 10.1016/j.jalgebra.2005.01.043.
[25]	C. Scheiderer, Sums of squares on real algebraic surfaces, Manuscripta Math., 119 (2006), 395-410. doi: 10.1007/s00229-006-0630-5.
[26]	M. Schwieghofer and L. F. Vargas, Sum-of-squares certificates for copositivity via test states, arXiv: 2310.12853, 2023.
[27]	L. F. Vargas, Sum-of-Squares Representations for Copositive Matrices and Independent Sets in Graphs, PhD Thesis, Tilburg University, 2023.