betaFeedback

WorksMathematics

When is Polynomial Optimization SoS-Exact? Sufficient Regularization and Strict Gram Representations

Abstract

Global minimization of multivariate polynomials is computationally difficult in general, and nonnegativity does not necessarily imply a sum-of-squares (SoS) representation. We show that adding sufficiently strong Euclidean regularization to a polynomial provides a general mechanism for overcoming such challenges. Namely, for any multivariate polynomial PP of degree at most pp with a nonzero linear coefficient, and any even integer 2d>p2d>p, we prove that mσ(s)=P(s)+σ2d∥s∥22dm_σ(s)=P(s)+\fracσ{2d}\|s\|_2^{2d} is SoS exact for all sufficiently large σσ. Furthermore, the shifted polynomial mσ−min⁡mσm_σ-\min m_σ admits a positive-definite Gram representation on appropriately-shifted nonconstant monomials. Consequently, the global minimum and minimizer can be recovered exactly by a single degree-dd semidefinite programming (SDP) representation, whose size is polynomial in the dimension for fixed dd, without requiring higher levels of the SoS hierarchy. The proof develops a degree-independent mechanism based on the Bregman remainder of the regularizer: its strict Gram margin absorbs the lower-degree polynomial perturbations. We further establish an analogous exact SDP regime for polynomial optimization over sufficiently small Euclidean balls, connecting large regularization with small-radius trust-region problems. Finally, we investigate how the algebraic structure of the regularizer governs the existence of a strict Gram margin, extending the mechanism beyond Euclidean norms while identifying limitations of coordinate-separable regularization.

Introduction

Global minimization of a multivariate polynomial is a fundamental yet computationally challenging problem, even at relatively low degrees. For instance, minimizing a homogeneous cubic over the Euclidean sphere is NP-hard [19]; testing nonnegativity of quartic polynomials is NP-hard [17]; and even deciding whether a quartic polynomial has a local minimizer is strongly NP-hard [3]. Despite these general hardness results, certain polynomial classes admit exact and computationally tractable formulations due to their underlying algebraic structure. This raises a fundamental question: beyond the classical tractable cases, can one identify broader classes of multivariate polynomials whose global minima can be computed and certified exactly?

A classical illustration of such algebraic structure dates back to Hilbert’s celebrated work in 1888. He showed that nonnegative polynomials need not be sums of squares (SoS), and characterized the three classical cases in which the two notions coincide: univariate polynomials of arbitrary degree, quadratic polynomials in any number of variables, and bivariate quartics [14]. This distinction has fundamental consequences for global optimization. Indeed, if a polynomial hh attains its global minimum h∗h^*, then the shifted polynomial h−h∗h-h^* is nonnegative. When this nonnegative polynomial admits an SoS representation, its global minimum can be computed and certified through semidefinite programming (SDP) [21, 16]. Beyond Hilbert’s classical cases, it is therefore natural to ask whether additional algebraic structure can guarantee SoS exactness and, consequently, exact global minimization by a tractable SDP.

In this paper, we show that sufficiently strong regularization provides precisely such a mechanism. We consider a broad class of multivariate polynomials of arbitrary even degree, obtained by adding a higher-degree Euclidean regularizer to a polynomial of lower degree. Let PP be an arbitrary multivariate polynomial of degree at most pp, and let 2d>p2d > p be an even integer. We study the regularized polynomial

mσ(s):=P(s)+σ2d∥s∥2d,σ>0,(1)m_{\sigma}(s) := P(s) + \frac{\sigma}{2d}\lVert s\rVert^{2d}, \qquad\sigma> 0, \tag*{(1)}

where ∥⋅∥\lVert\cdot\rVert denotes the Euclidean norm. Since the regularization term has higher degree than PP, mσm_{\sigma} is coercive and therefore always attains a global minimum. Our main result shows that, under a nonzero linear-term assumption, sufficiently strong regularization makes mσm_{\sigma} SoS exact, with its unique global minimizer recoverable from a single SDP of polynomial size for every fixed dd. To be precise, let

sσ∗∈arg⁡min⁡u∈Rn mσ(u),mσ∗:=mσ(sσ∗),qσ:=mσ−mσ∗,s_{\sigma}^{*} \in\underset{u\in\mathbb{R}^{n}}{\arg\min}\ m_{\sigma}(u), \qquad m_{\sigma}^{*} := m_{\sigma}(s_{\sigma}^{*}), \qquad q_{\sigma} := m_{\sigma} - m_{\sigma}^{*},

where sσ∗s_{\sigma}^{*} denotes a minimizer and mσ∗m_{\sigma}^{*}, its optimal value. The shifted polynomial qσq_{\sigma} is nonnegative by construction. We say that mσm_{\sigma} is SoS exact if qσq_{\sigma} is a sum of squares of polynomials of degree at most dd. Equivalently, the global minimum mσ∗m_{\sigma}^{*} is attained exactly by a single degree-dd SoS representation, with no higher-order relaxations required. Furthermore, the SDP recovers not only the exact global minimum but also its unique global minimizer. In particular, the optimal moment matrix has rank one, and the minimizer can be read directly from the moments corresponding to the linear monomials. Our main result can be stated as follows; the precise statements are given in Corollaries 4.2 and 4.3.

Theorem 1.1 (Main result, informal). Let PP be a polynomial of degree at most pp with nonzero linear coefficient g:=∇P(0)≠0g := \nabla P(0) \ne0, let 2d>p2d > p be even, and let mσm_{\sigma} be defined in (1). Then there exists a threshold σ∗>0\sigma^{*} > 0 such that, for every σ≥σ∗\sigma\ge\sigma^{*}:

(i) The shifted polynomial mσ−mσ∗m_{\sigma} - m_{\sigma}^{*} is a sum of squares of polynomials of degree at most dd. Furthermore, it admits a positive-definite Gram representation on the nonconstant monomials centred at global minimizer sσ∗s_{\sigma}^{*}.

(ii) A single degree-dd moment SDP attains the exact global minimum and has a unique rank-one optimal moment matrix, from which sσ∗s_{\sigma}^{*} can be recovered directly. For fixed dd, this SDP has size polynomial in nn.

The threshold σ∗\sigma^{*} is given explicitly in terms of the coefficients of PP. Numerical evidence in the quartic case suggests that exactness may occur at substantially smaller regularization parameters [26].

The class in (1) arises naturally in higher-order nonlinear optimization, where Taylor models combined with regularization provide a standard globalization mechanism. Any polynomial of degree at most pp can be written exactly in Taylor form,

P(s)=Tp(s):=∑j=0p1j!Tj[s]j,(2)P(s) = \mathcal{T}_{p}(s) := \sum_{j=0}^{p} \frac{1}{j!} T_j[s]^j, \tag*{(2)}

where TjT_j is a symmetric jjth-order tensor determined by the coefficients of PP (see § 2). For a Taylor approximation of a smooth function ff at xx, we have Tj=∇jf(x)T_j = \nabla^j f(x). The associated regularized model is

mσ(s)=Tp(s)+σp′∥s∥p′,(3)m_{\sigma}(s) = \mathcal{T}_{p}(s) + \frac{\sigma}{p'}\lVert s\rVert^{p'}, \tag*{(3)}

where σ>0\sigma> 0 and our polynomial setting takes the even exponent p′=2d>pp' = 2d > p. Thus the PP in (1) and the Tp\mathcal{T}_p here are identical. Beginning with cubic regularization of Newton’s method [20], higher-order adaptive regularization methods have developed a rich convergence and complexity theory [4, 5, 6, 11]. Yet the global solution of their polynomial subproblems remains a central computational challenge. Nesterov [18] explicitly asked whether tools from algebraic geometry, particularly sums of squares, could be used to minimize such subproblems. Our result provides a positive answer in the sufficiently regularized regime. We also study the complementary trust-region globalization strategy [10], which minimizes the same Taylor polynomial over ∥s∥≤Δ\lVert s\rVert\le\Delta. For sufficiently small radii, we establish a correspondence with the large-regularization regime; see § 5.

Classically, convexity is one of the principal sources of tractability in optimization [23]. We emphasize, however, that our framework does not rely on convexifying the polynomial model. Instead, we retain the regularized Taylor polynomial itself and prove that sufficiently strong Euclidean regularization makes its shifted nonnegative polynomial SoS exact, even when the model remains nonconvex. Thus regularization can do more than provide boundedness or globalization: it can enforce algebraic exactness without requiring convexity. This provides a different route from the SoS-convex higher-order Newton framework of Ahmadi, Chaudhry and Zhang [1]. Their approach constructs an SoS-convex polynomial subproblem through suitable corrections and regularization, whereas our result establishes an exact SoS representation for the original regularized model, without assuming convexity or SoS-convexity.

In addition to the result in Theorem 1.1, our contributions reveal three complementary aspects of this algebraic exactness mechanism.

  1. A mechanism linking optimality and algebraic geometry. Our central technical result shows that the Bregman remainder of the Euclidean regularizer admits a positive-definite Gram representation on the full vector of nonconstant monomials. When the regularization is sufficiently large, this strict Gram margin absorbs the remaining Taylor terms, yielding an exact SoS representation of the shifted nonnegative polynomial. This mechanism is distinct from our earlier quartic analysis [26], which relies on identities specific to degree four. The Bregman/strict-Gram argument developed here applies at every even regularization degree and extends to broader classes of regularizers; see § 3.2. Thus the present result is not merely a higher-degree extension of the quartic case, but a degree-independent approach to establishing SoS exactness.

  1. Small-radius trust-region problems admit exact SDP solutions. The same mechanism governs polynomial optimization over a Euclidean ball. Minimizing a degree-pp polynomial over ∥s∥≤Δ\lVert s\rVert\le\Delta is a higher-order trust-region subproblem and is NP-hard in general for p≥3p \ge3 [19]. In § 5, we show that when the linear coefficient is nonzero and the radius Δ\Delta is sufficiently small, the global minimizer is unique, lies on the sphere ∥s∥=Δ\lVert s\rVert= \Delta, and can be recovered exactly from a rank-one solution of a degree-dd moment relaxation (Proposition 5.2). At an active trust-region solution, the multiplier λΔ\lambda_{\Delta} determines the matched regularization parameter σ=λΔ/Δ2d−2\sigma= \lambda_{\Delta}/\Delta^{2d-2}. As Δ↓0\Delta\downarrow0, this parameter tends to infinity, connecting small trust regions with the large-regularization regime of our main theorem. The radius threshold is explicit in the tensor norms of the Taylor coefficients. Thus, the two classical globalization strategies share the same algebraic mechanism for SoS exactness.

  1. The choice of regularization matters. The mechanism depends on the algebraic structure of the regularizer, not merely on its strength. Euclidean regularization produces the strict Gram margin underlying our SoS exactness result, whereas other regularizers need not possess this property, regardless of how large the regularization parameter becomes. In § 3.2, we investigate which regularizers admit such a margin: weighted Euclidean norms and regularizers constructed from spanning families of linear forms inherit the strict Gram property, while coordinate-separable regularization, although coercive and SoS-convex, does not control all mixed monomial directions needed for a full positive-definite Gram representation. This distinction holds across the even regularization degrees considered here. It shows that the choice of regularizer, often treated as a modelling tool, plays a decisive role in the algebraic structure underlying SoS exactness.

Background and Notation. We recall only the basic notions used throughout the paper: SoS polynomials, monomial vectors, Gram representations, and SoS-convexity. Unless stated otherwise, ∥⋅∥\lVert\cdot\rVert denotes the Euclidean norm.

Definition 1.1 (Sum of squares and Gram representation). Let h∈R[x]h \in\mathbb{R}[x] be a polynomial of degree at most 2d2d. We say that hh is a sum of squares (SoS) if there exist polynomials h1,…,hrh_1,\ldots,h_r of degree at most dd such that

h(x)=∑i=1rhi(x)2.h(x)=\sum_{i=1}^{r}h_i(x)^2.

We denote by Σ[x]2d\Sigma[x]_{2d} the cone of SoS polynomials of degree at most 2d2d. For k≥0k \ge0, let [x]k[x]_k denote the normalized vector of monomials of total degree kk, chosen so that ∥[x]k∥2=∥x∥2k\|[x]_k\|^2=\|x\|^{2k}. We write zd(x):=(1,[x]1T,…,[x]dT)Tz_d(x):=(1,[x]_1^{\mathsf T},\ldots,[x]_d^{\mathsf T})^{\mathsf T} for the full monomial vector of degree at most dd. Then hh is SoS if and only if it admits a Gram representation

h(x)=zd(x)TQzd(x)h(x)=z_d(x)^{\mathsf T}Qz_d(x)

for some symmetric Q⪰0Q \succeq0. See, e.g., [21, 16].

Definition 1.2 (Nonconstant monomials and strict Gram representation). We denote by

vd(x):=([x]1T,…,[x]dT)Tv_d(x):=([x]_1^{\mathsf T},\ldots,[x]_d^{\mathsf T})^{\mathsf T}

the vector of all nonconstant monomials of degrees 1,…,d1,\ldots,d. Its dimension is Nn,d=∑k=1d(n+k−1k)=(n+dd)−1N_{n,d}=\sum_{k=1}^{d}\binom{n+k-1}{k}=\binom{n+d}{d}-1. When nn and dd are fixed, we write N:=Nn,dN:=N_{n,d}. For a polynomial qq with zero constant and linear terms, we say that qq admits a strict Gram representation on vdv_d if

q(x)=vd(x)TQvd(x)q(x)=v_d(x)^{\mathsf T}Qv_d(x)

for some symmetric Q≻0Q \succ0. The matrix QQ is called a Gram matrix of qq. For a chosen strict Gram representation, λmin⁡(Q)>0\lambda_{\min}(Q)>0 is called its Gram margin. The Gram matrix need not be unique, so the margin is attached to the chosen representation.

Definition 1.3 (SoS-convexity). A polynomial hh is SoS-convex if yT∇2h(x)yy^{\mathsf T}\nabla^2h(x)y is an SoS polynomial jointly in (x,y)(x,y). Equivalently, its Hessian is an SoS matrix [2]. We use the standard implication that the first-order Bregman remainder of an SoS-convex polynomial is SoS; the precise references are recalled in Remark 3.1.

How Regularization Creates SoS Exactness: An Overview

Before turning to the technical results, we give a short overview of the mechanism behind the proof. The aim is to explain why increasing regularization can change the SoS behaviour of the model even when the model itself remains nonconvex.

The phenomenon is perhaps easiest to understand geometrically. Suppose that the Taylor model has negative curvature at the base point s=0s=0. Since the Hessian of the higher-order regularization term

σ2d∥s∥2d,d≥2,\frac{\sigma}{2d}\|s\|^{2d},\qquad d\ge2,

vanishes at the origin, increasing σ\sigma does not remove this negative curvature. Hence the regularized polynomial may remain locally nonconvex at the base point for every finite value of σ\sigma; see also [9]. Nevertheless, its algebraic behaviour can change substantially as the regularization increases. Interestingly, Parrilo [22, Sec. 5.1] observed numerically that certain quartically regularized polynomial models appear to be SoS once the regularization is sufficiently large.

Figure 1 gives a one-dimensional slice of a multivariate regularized polynomial at different regularization strengths. The panels illustrate a change in geometry from “not SoS” to “SoS exact” as regularization increases. Note that the SoS labels refer to the full multivariate optimality gap, not to the plotted univariate restriction: every nonnegative univariate polynomial is already SoS.

One-dimensional slices of multivariate regularized polynomial models

Figure 1. One-dimensional slices of multivariate regularized polynomial models as the regularization parameter increases. The red dot marks the base point s=0s = 0, where the negative quadratic curvature is unchanged by the higher-order regularizer; the star marks a global minimizer.

From polynomials to Taylor models. Any polynomial P:Rn→RP:\mathbb{R}^n\to\mathbb{R} of degree at most pp can be written exactly as a finite Taylor expansion,

P(s)=∑∣α∣≤pcαsα=∑j=0p1j!Tj[s]j,P(s)=\sum_{|\alpha|\le p}c_\alpha s^\alpha=\sum_{j=0}^{p}\frac{1}{j!}T_j[s]^j,

where α=(α1,…,αn)\alpha= (\alpha_1,\ldots,\alpha_n) is a multi-index, ∣α∣=∑i=1nαi|\alpha| = \sum_{i=1}^{n} \alpha_i, α!=∏i=1nαi!\alpha! = \prod_{i=1}^{n} \alpha_i!, and sα=∏i=1nsiαis^\alpha= \prod_{i=1}^{n} s_i^{\alpha_i}. Here TjT_j is the symmetric jjth-order tensor determined by the coefficients of PP: for indices i1,…,iji_1,\ldots,i_j with multiplicities α1,…,αn\alpha_1,\ldots,\alpha_n, set

References

  1. [1]Amir Ali Ahmadi, Abraar Chaudhry, and Jeffrey Zhang. Higher-order newton methods with polynomial work per iteration. Advances in Mathematics, 452:109808, 2024.
  2. [2]Amir Ali Ahmadi and Pablo A. Parrilo. A complete characterization of the gap between convexity and sos-convexity. SIAM Journal on Optimization, 23(2):811–833, 2013.
  3. [3]Amir Ali Ahmadi and Jeffrey Zhang. On the complexity of finding a local minimizer of a quadratic function over a polytope. Mathematical Programming, 195(1-2):783–792, 2022.DOI
  4. [4]Ernesto G Birgin, JL Gardenghi, José Mario Martínez, Sandra Augusta Santos, and Ph L Toint. Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models. Mathematical Programming, 163(1):359–368, 2017.DOI
  5. [5]Coralia Cartis, Nicholas I. M. Gould, and Philippe L. Toint. Universal regularization methods: Varying the power, the smoothness and the accuracy. SIAM Journal on Optimization, 29(1):595–615, 2019.arxiv.org/abs/1811.07057
  6. [6]Coralia Cartis, Nicholas Ian Mark Gould, and Ph L Toint. Evaluation complexity of algorithms for nonconvex optimization. MOS-SIAM Series on Optimization., 2022.DOI
  7. [7]Coralia Cartis, Nick IM Gould, and Ph L Toint. A concise second-order complexity analysis for unconstrained optimization using high-order regularized models. Optimization Methods and Software, 35(2):243–256, 2020.DOI
  8. [8]Coralia Cartis and Wenqi Zhu. Cubic-quartic regularization models for solving polynomial subproblems in third-order tensor methods. Mathematical Programming, 2025.arxiv.org/abs/2312.10283
  9. [9]Coralia Cartis and Wenqi Zhu. Global optimality characterizations and algorithms for minimizing quartically-regularized third-order taylor polynomials. Mathematics of Computation, 2026. 32 pp.arxiv.org/abs/2504.20259
  10. [10]Andrew R Conn, Nicholas IM Gould, and Philippe L Toint. Trust region methods. SIAM, 2000.DOI
  11. [11]Nikita Doikov and Yurii Nesterov. Local convergence of tensor methods. Mathematical Programming, 193(1):315–336, 2022.
  12. [12]Joe Harris. Algebraic Geometry: A First Course, volume 133 of Graduate Texts in Mathematics. Springer, 1992.
  13. [13]J William Helton and Jiawang Nie. Semidefinite representation of convex sets. Mathematical Programming, 122:21–64, 2010.
  14. [14]David Hilbert. Über die darstellung definiter formen als summe von formenquadraten. Mathematische Annalen, 32(3):342–350, 1888.
  15. [15]J. M. Landsberg. Tensors: Geometry and Applications, volume 128 of Graduate Studies in Mathematics. American Mathematical Society, 2012.DOI
  16. [16]Jean B Lasserre. Global optimization with polynomials and the problem of moments. SIAM Journal on optimization, 11(3):796–817, 2001.DOI
  17. [17]Katta G Murty and Santosh N Kabadi. Some np-complete problems in quadratic and nonlinear programming. Mathematical Programming: Series A and B, 39(2):117–129, 1987.
  18. [18]Yurii Nesterov. Implementable tensor methods in unconstrained convex optimization. Mathematical Programming, 186:157–183, 2021.
  19. [19]Yurii Nesterov et al. Random walk in a simplex and quadratic optimization over convex polytopes. Technical report, CORE, 2003.
  20. [20]Yurii Nesterov and Boris T. Polyak. Cubic regularization of newton method and its global performance. Mathematical Programming, 108(1):177–205, 2006.DOI
  21. [21]Pablo A Parrilo. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. PhD thesis, California Institute of Technology, 2000.DOI
  22. [23]R. Tyrrell Rockafellar. Lagrange multipliers and optimality. SIAM Review, 35(2):183–238, 1993.DOI
  23. [24]Jorge Nocedal Stephen J Wright. Numerical optimization, 2006.
  24. [25]Jinling Zhou, Xin Liu, Jiawang Nie, and Xindong Tang. A tight sdp relaxation for the cubic-quartic regularization problem. Mathematical Programming, pages 1–41, 2026.arxiv.org/abs/2511.00168
  25. [26]Wenqi Zhu and Coralia Cartis. Sufficiently regularized nonnegative quartic polynomials are sum-of-squares. arXiv preprint arXiv:2601.20418, 2026.arxiv.org/abs/2601.20418

Paper details

vlnc:W_9qcperra
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY-SA 4.0
Usage

views · 4

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents