Finite convergence of the Moment-SOS hierarchy under hidden convexity This research is supported by the AI Interdisciplinary Institute ANITI funding through the ANITI AI Cluster program under the Grant agreement ANR-23-IACL-0002, and also by the Marie-Sklodovska-Curie European doctoral network TENORS, grant 101120296. This research is also part of the programme DesCartes and is supported by the National Research Foundation, Prime Minister’s Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme.
\firstname Srećko \lastname Đurašinović, \firstname Jean \middlename B. \lastname Lasserre · 2026
Read Finite convergence of the Moment-SOS hierarchy under hidden convexity This research is supported by the AI Interdisciplinary Institute ANITI funding through the ANITI AI Cluster program under the Grant agreement ANR-23-IACL-0002, and also by the Marie-Sklodovska-Curie European doctoral network TENORS, grant 101120296. This research is also part of the programme DesCartes and is supported by the National Research Foundation, Prime Minister’s Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme. by \firstname Srećko \lastname Đurašinović, \firstname Jean \middlename B. \lastname Lasserre (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-00284.txt.
Introduction
Ðurašinović and Lasserre study polynomial optimization over a compact set defined by SOS-concave polynomials. The function to be minimized need not be convex overall. They show that when the objective's Hessian admits a specific quadratic-module form, a hidden local convexity, the Moment-SOS hierarchy reaches the exact answer in finitely many steps. It needs no advance knowledge of that convexity. Strong convexity on the feasible set suffices for that form. The authors give an explicit order where exactness occurs, yielding certified global minimizers.
Catalog record
| CREATOR | \firstname Srećko \lastname Đurašinović, \firstname Jean \middlename B. \lastname Lasserre |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 37345 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.00284
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Finite convergence of the Moment-SOS hierarchy under hidden convexity This research is supported by the AI Interdisciplinary Institute ANITI funding through the ANITI AI Cluster program under the Grant agreement ANR-23-IACL-0002, and also by the Marie-Sklodovska-Curie European doctoral network TENORS, grant 101120296. This research is also part of the programme DesCartes and is supported by the National Research Foundation, Prime Minister’s Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme. \firstname Srećko \lastname Đurašinović, \firstname Jean \middlename B. \lastname Lasserre Abstract Résumé One considers polynomial optimization problems with compact feasible set 𝛀 \mathbf{\Omega} defined by SOS-concave polynomials g j g_{j} , and with a globally non-convex polynomial objective f f . We show that if f f is strongly convex on 𝛀 \mathbf{\Omega} , or SOS-convex on 𝛀 \mathbf{\Omega} when the constraints g j g_{j} are at most quadratic, then the Moment-SOS hierarchy converges in finitely many steps, without à priori knowledge of this hidden (local) convexity. In addition, in the latter case, the exact order for which the relaxation is exact is provided by the degree of a Putinar-like certificate of convexity. This demonstrates that a general-purpose hierarchy can adapt to favorable hidden properties of a specific instance without being informed of them, yielding certified global minimizers. keywords Polynomial optimization; Moment-SOS hierarchy; Semidefinite relaxations; Hidden convexity. 1 Introduction Given multivariate polynomials f,g_{j}\in\mathbb{R}[\mathbf{x}] , j=1,\ldots,m , consider the polynomial optimization problem (POP) \displaystyle f^{*}\,=\,\min_{\mathbf{x}\in\mathbf{\Omega}}\,f(\mathbf{x}), (1.1) where the feasible set \mathbf{\Omega}=\{\,\mathbf{x}\in\mathbb{R}^{d}:g_{j}(\mathbf{x})\geq 0\,,\>j=1,\ldots,m\,\} is compact and convex, but f is not convex. If f is convex on \mathbf{\Omega} , Problem ( 1.1 ) is convex but not a “convex program“ as the latter definition usually assumes that f and the -g_{j} ’s are convex on the whole space \mathbb{R}^{d} . This distinction is not a subtlety. Indeed, suppose that the g_{j} ’s are concave polynomials and that the Slater’s condition holds. Then the KKT-optimality conditions \displaystyle\nabla f(\mathbf{x}^{*})-\sum_{j=1}^{m}\lambda^{*}_{j}\nabla g_{j}(\mathbf{x}^{*})\,=\,0,\>\lambda^{*}_{j}\,g_{j}(\mathbf{x}^{*})=0,\>j=1,\dots,m\,,\>{\boldsymbol{\lambda}}^{*}\geq 0, (1.2) at local minimizer \mathbf{x}^{*}\in\mathbf{\Omega} (for some {\boldsymbol{\lambda}}^{*}\geq 0 ) have a quite different interpretation depending on whether f is convex on \mathbb{R}^{d} or on \mathbf{\Omega} only. In the former case, \displaystyle\mathcal{L}(\mathbf{x},{\boldsymbol{\lambda}}^{*})-f^{*}\,:=\,f(\mathbf{x})-f^{*}-\sum_{j=1}^{m}\lambda^{*}_{j}\,g_{j}(\mathbf{x})\,\geq\,0,\quad\forall\mathbf{x}\in\mathbb{R}^{d}, (1.3) that is, \mathbf{x}^{*} is also a global minimizer of the Lagrangian \mathcal{L}(\cdot,{\boldsymbol{\lambda}}^{*}) on the whole \mathbb{R}^{d} , because \mathcal{L}(\cdot,{\boldsymbol{\lambda}}^{*}) is convex and \nabla\mathcal{L}(\mathbf{x}^{*},{\boldsymbol{\lambda}}^{*})=0 . In the latter case, while convex on \mathbf{\Omega} , \mathcal{L}(\cdot,{\boldsymbol{\lambda}}^{*}) is not necessarily convex on \mathbb{R}^{d} (typically when \mathrm{deg}(f)>\max_{j}\{\mathrm{deg}(g_{j})\} ). Consider, for instance, f^{*}=\min\{\,x^{3}:\>x(1-x)\geq 0\} with (x^{*},\lambda^{*})=(0,0) . For algorithms which converge to a local minimizer \mathbf{x}^{*}\in\mathbf{\Omega} that satisfies ( 1.2 ), global optimality of \mathbf{x}^{*} is guaranteed if f is convex on \mathbf{\Omega} . But if this (local) convexity on \mathbf{\Omega} is hidden, one is left with an à priori local minimizer only. Recall that checking whether a given polynomial is convex is NP-hard [ 1 ] . The Moment-SOS hierarchy Let g_{0}:\mathbf{x}\mapsto 1 be a constant polynomial. Recall that the degree- n semidefinite relaxation of moment-SOS hierarchy to solve the POP ( 1.1 ), reads : \displaystyle\rho_{n}=\min_{{{\boldsymbol{\phi}}}}\,\{\,\phi(f):\,\phi(1)=1,\>\mathbf{M}_{n-d_{j}}(g_{j}\,{\boldsymbol{\phi}})\succeq 0,\>j=0,\ldots,m\}, (1.4) where {\boldsymbol{\phi}}=(\phi_{{\boldsymbol{\alpha}}})_{{\boldsymbol{\alpha}}\in\mathbb{N}^{d}_{2n}} , \mathbf{M}_{n-d_{j}}(g_{j}\,{\boldsymbol{\phi}}) is the degree- (n-d_{j}) localizing matrix associated with {\boldsymbol{\phi}} and the polynomial g_{j} , and d_{j}=\lceil\mathrm{deg}(g_{j})/2\rceil , j=0,\ldots,m , d_{f}=\lceil\mathrm{deg}(f)/2\rceil . Then, \rho_{n}\leq f^{*} for all n\geq\max[d_{f},\max_{j}d_{j}] , and if the quadratic module defined by the g_{j} ’s is Archimedean (see discussion around ( 2.8 )), \rho_{n}\uparrow f^{*} as n\to+\infty . For more details on the Moment-SOS hierarchy and its applications, the interested reader is referred to, for example, [ 9 ] . Remark 1.1 As proved in [ 10 ] , finite convergence is a generic property of the Moment-SOS hierarchy in the general case, with no convexity assumption, neither on f nor on the g_{j} ’s. However, when considering a specific instance (f,g_{1},\ldots,g_{m}) of POP, one does not know whether that instance is regular, even if theoretically, given the class (m,s) of POPs ( 1.1 ) with m inequality constraints and with \sup[\mathrm{deg}(f),\mathrm{deg}(g_{j})]<s , genericity could be tested (but at a prohibitive computational cost). Convex and SOS-convex POPs Convex or SOS-convex problems form a typical class for which the Moment-SOS hierarchy has finite convergence. For instance, if f and -g_{j} are SOS-convex (see ( 1.5 )), finite convergence takes place at the first semidefinite relaxation of the hierarchy [ 7 ] . If f is only convex, finite convergence is guaranteed, but without knowing at which step of the hierarchy convergence takes place. We remind that, while convexity is hard to detect [ 1 ] , SOS-convexity can be, in principle, checked efficiently. Of course, when the information that f and -g_{j} are convex is known à priori, some algorithms can be more efficient than the Moment-SOS hierarchy, but the interesting observation is when the convexity of f is hidden . Indeed, the Moment-SOS hierarchy blindly recognizes SOS-convex POPs, i.e., without à priori knowledge of this SOS-convexity , as it converges at the first step of the hierarchy. It is a nice feature of a general purpose method to be able to adapt its behavior by benefiting from strong properties of some specific instances, without being “informed” of such properties. In [ 5 ] , the authors have extended some results of [ 7 ] . They prove finite convergence of the Moment-SOS hierarchy for convex programs when (i) Slater’s condition holds, (ii) the quadratic module associated with the g_{j} ’s is Archimedean, and (iii) \nabla^{2}f(\mathbf{x}^{*})\succ 0 at every minimizer \mathbf{x}^{*} . Also, if \mathbf{\Omega}\subset\mathbf{B}(0,R) , the same result holds under conditions (ii) and (iii) (but now satisfied by the Lagrangian \mathcal{L} rather than by f ). Two key ingredients in [ 5 ] are a result of Scheiderer [ 11 ] and the (convex) Farkas Lemma [ 3 , Prop. 5.3.1] . Finally, it is shown in [ 6 ] that if both f and \mathbf{\Omega} are convex (without the g_{j} ’s are not necessarily concave), all points that satisfy the KKT-optimality conditions are global minimizers. Contribution Let us start by introducing the notion of SOS-convexity on \mathbf{\Omega} . Namely, a polynomial f\in\mathbb{R}[\mathbf{x}] is said to be SOS-convex on \mathbf{\Omega} if \displaystyle\nabla^{2}f(\mathbf{x})\,=\,\sum_{j=0}^{m}\mathbf{L}_{j}(\mathbf{x})\mathbf{L}_{j}(\mathbf{x})^{\top}\,g_{j}(\mathbf{x}),\quad\forall\mathbf{x}\in\mathbb{R}^{d}, (1.5) for some integers r_{j}\in\mathbb{N} and matrix polynomials \mathbf{L}_{j}\in\mathbb{R}[\mathbf{x}]^{d\times r_{j}} , j=0,\ldots,m . This definition is a natural extension of global SOS-convexity on \mathbb{R}^{d} (introduced in [ 4 ] , see also [ 7 ] ) to local SOS-convexity on \mathbf{\Omega} . Notice that ( 1.5 ) can be viewed as a Putinar-type algebraic certificate that f is convex on \mathbf{\Omega} . In particular, if f is strongly convex on \mathbf{\Omega} , then by the Putinar’s matrix Positivstellensatz [ 8 , Theorem 2.19] , ( 1.5 ) holds and so f is SOS-convex on \mathbf{\Omega} . In principle, checking whether ( 1.5 ) holds can be done efficiently by solving a semidefinite program of finite size determined by an à priori bound on the maximum degree appearing in entries of matrix polynomials \mathbf{L}_{j}(\mathbf{x}) . The scope of this work is determined by the class of POPs for which : — the g_{j} ’s are all SOS-concave and so \mathbf{\Omega} is convex. Typical examples of such feasible sets include the simplex, the Euclidean unit ball, convex polytopes, intersection of ellipsoids, etc. — f is not convex on \mathbb{R}^{d} but is SOS-convex on \mathbf{\Omega}