The Gold Standard of Polynomial Optimization

Chapter index

Consider p(x)=x⁴−2x². Asking for its minimum is incomplete until we know which x are permitted. Over all real numbers, its minimum is −1 at x=−1 and x=1. Over the interval [0,½], its minimum is −7/16 at x=½. Over the integers, the unrestricted answer happens to remain −1, but that agreement is a feature of this example, not a general rule.

A standard problem minimises p(x) over a set K described by gᵢ(x)≥0 and hⱼ(x)=0. Each expression is a polynomial in real decision variables. Such a set is called a basic semialgebraic set. The word describes the representation; it does not promise that K is convex, connected or easy to search.

Write what the symbols mean

For a design problem, x might contain dimensions, operating settings or allocation amounts. Record their units and permissible ranges. A term such as x₁x₂ couples two variables, while x₁² penalises the first variable on its own. Degree counts the total exponents in a monomial: x₁²x₂³ has degree five.

The existing guide to polynomial structure, factors and multiplicity develops the algebra needed to read these expressions accurately. Factorisation can reveal an optimum that an expanded formula hides, but it must be interpreted over the stated domain.

A continuous polynomial reaches a minimum on a nonempty compact feasible set. Without compactness or another existence argument, distinguish a minimum from an unattained infimum and from an objective unbounded below. For example, minimising x over all real x has no finite lower bound. Naming an optimisation algorithm does not repair that mathematical absence.

Before computing, therefore, write four lines: variables, objective, feasible set and assumptions supporting existence. This small specification prevents later certificates from answering a different question from the one intended.

Contents · Next chapter

Differentiation identifies stationary points, but a zero derivative does not by itself identify a global minimum. For p(x)=x⁴−2x², the derivative is 4x(x²−1), giving candidates −1,0,1. The second derivative is 12x²−4. The two outer candidates are local minima, while zero is a local maximum.

Direct substitution gives p(−1)=p(1)=−1 and p(0)=0. In one variable, checking stationary points, boundaries and behaviour at infinity can settle many problems. In several variables, the stationary equations may have many roots, and a numerical method may discover only some of them.

Why a dense plot is not a proof

A graph samples a finite collection of locations and connects their displayed values. A narrow dip between samples can be missed. Increasing resolution supplies better exploratory evidence, but it does not establish a universal inequality without an error bound or an exact argument.

The polynomial graphs guide connects factors, multiplicity and end behaviour. Those features help generate candidates and detect mistakes. Global certification adds the statement that no unexamined location can improve the answer.

For minimisation, any feasible candidate gives an upper bound on the best value. A proof that p(x)≥γ throughout K gives a lower bound γ. If a candidate has value U, then γ≤p*≤U, and the possible objective improvement is at most U−γ.

Suppose a numerical search returns a feasible point costing −0.9998 and an independently checked certificate gives γ=−1. The remaining improvement is at most 0.0002. That conclusion does not require knowing which minimiser the search approached. It concerns objective value, not necessarily distance to one unique decision.

Keep these two sources of evidence separate in a report. The search finds a witness; the certificate limits every alternative. Their agreement is much more informative than the number of iterations a solver performed.

Previous chapter · Contents · Next chapter

The expression x⁴−2x² becomes transparent after adding one: p(x)+1=(x²−1)². A square is nonnegative for every real x, so p(x)≥−1 globally. At x=±1 the square vanishes, proving that the lower bound is attained.

This identity is a complete certificate. A reader can expand its right-hand side, check the coefficients and verify the candidate. There is no dependence on a plotting window, initial guess or floating-point stopping rule. The polynomial remains nonconvex near zero, yet its global minimum is easy to prove.

Check an approximate candidate

At x=0.9, p(x)=0.6561−1.62=−0.9639. Its gap above the certified minimum is 0.0361. The certificate predicts exactly the same number: (0.81−1)²=0.0361. This equality locates the error in a single algebraic remainder.

Now change the polynomial to pₐ(x)=x⁴−2ax², where a is a fixed real parameter. If a≥0, pₐ(x)+a²=(x²−a)², and the minimum is −a² at x=±√a. If a<0, both x⁴ and −2ax² are nonnegative, so the minimum is zero at x=0.

The square identity still gives a lower bound −a² when a<0, but it is not sharp: equality would require x²=a, impossible for real x. A valid identity can therefore produce a correct but unnecessarily weak bound. Checking attainability is a separate step.

At a=0 the two nonzero minimisers merge at zero. The minimum value is continuous across this change, while the structure of the minimiser set changes. This is a useful reminder that smooth-looking objective values do not guarantee an unchanged decision pattern.

An effective learner should be able to explain all three cases without appealing to a remembered graph. The controlling facts are the nonnegativity of squares and whether the equality condition is feasible over the real numbers.

Previous chapter · Contents · Next chapter

A polynomial is a sum of squares, abbreviated SOS, when it can be written as q₁(x)²+⋯+qₖ(x)² for real polynomials qᵢ. Such a representation immediately proves global nonnegativity. Its value is not merely that it looks positive; each summand has a sign that is fixed everywhere.

For example, r(x,y)=(x²−y)²+(y−2)² has lower bound zero. Equality requires x²=y and y=2, giving the two minimisers (√2,2) and (−√2,2). Expanding produces x⁴−2x²y+2y²−4y+4, whose mixed negative term is compatible with global nonnegativity.

Coefficient signs are not function signs

The term −2x²y can be negative or positive depending on y. Judging the whole polynomial by individual coefficients would miss the way terms combine. Conversely, a positive constant term does not prevent negative values elsewhere. Algebraic relationships, rather than a visual count of signs, control the conclusion.

Not every globally nonnegative multivariate polynomial is SOS. The classic distinction matters operationally: failure to find a decomposition in a chosen SOS search does not prove that the polynomial takes a negative value. It proves only that the requested certificate has not been established, or, with an exact infeasibility argument, that it does not exist within that search class.

Parrilo’s introduction to SOS programs and polynomial inequalities explains the relationship between these certificates and semidefinite programming. The distinction between nonnegativity and SOS is essential when interpreting relaxation bounds.

For a practical exercise, expand r and then recover its two squares. Substitute both minimisers and also test (0,2), where r=4. The certificate explains why the apparently natural choice y=2 is insufficient by itself: the first square imposes a second condition linking x and y.

This is the first place where a global proof also reveals the geometry of all solutions. Zero cost requires every square to vanish simultaneously, so the certificate supplies equations for recovering candidate minimisers.

Previous chapter · Contents · Next chapter

Choose a vector z(x) containing monomials up to a selected degree. A representation p(x)=z(x)ᵀQz(x), with Q symmetric positive semidefinite, proves that p is SOS. Indeed, factoring Q as RᵀR writes the expression as the squared Euclidean norm of Rz(x).

The unknown entries of Q enter the polynomial coefficients linearly. Requiring the expanded expression to match p therefore gives linear equations, while Q being positive semidefinite gives a convex matrix constraint. This is the basic bridge from polynomial certificates to semidefinite optimisation.

Match a small Gram matrix explicitly

For p(x)=(x²−1)², take z=(1,x,x²). One Gram matrix is Q=[[1,0,−1],[0,0,0],[−1,0,1]]. Its quadratic form is 1−2x²+x⁴. Moreover Q=vvᵀ with v=(1,0,−1), so Q is positive semidefinite without needing a numerical eigenvalue routine.

The factorisation gives zᵀQz=(vᵀz)²=(1−x²)². Checking coefficients and checking positive semidefiniteness are different obligations. A matrix can match the polynomial but be indefinite; another can be positive semidefinite but expand to the wrong coefficients.

A Gram matrix need not be unique. Different products of monomials can contribute to the same coefficient. The x² coefficient, for instance, receives contributions from the product of 1 and x² and from x times x. This freedom can help a solver find a positive semidefinite representation.

To search for a lower bound, replace p by p−γ and maximise γ while matching coefficients with a positive semidefinite Gram matrix. For x⁴−2x², γ=−1 is feasible using the matrix above. A feasible point x=1 gives the matching upper bound, completing the proof.

Do not confuse the convexity of this matrix search with convexity of the original polynomial. The original quartic is nonconvex; the certificate search is convex because the unknowns are matrix coefficients and a scalar bound.

Previous chapter · Contents · Next chapter

Global nonnegativity can be stronger than necessary. If decisions lie in K, it is enough to prove p−γ nonnegative on K. A useful certificate has the form p−γ=σ₀+Σσᵢgᵢ+Σtⱼhⱼ, where each σ is SOS and each t is an unrestricted polynomial.

On K, the gᵢ are nonnegative, the hⱼ vanish, and every SOS multiplier is nonnegative. Consequently every term that remains has the required sign. This certificate is sufficient whenever the identity is exact; no convergence theorem is needed to verify a particular displayed identity.

A boundary optimum needs the boundary information

Minimise x over [0,1], represented by x≥0 and 1−x≥0. The lower bound zero follows from x=1·x, where the multiplier 1 is the square of the constant polynomial 1. The feasible point x=0 attains it.

The polynomial x is not globally nonnegative, so searching only for a global SOS representation of x would fail. The failure would reflect an unnecessarily strong demand, not a difficult original problem. Including the domain changes the available proof.

For another example, maximise x² on [−2,2], or equivalently minimise −x² subject to 4−x²≥0. The identity −x²−(−4)=4−x² proves a lower bound −4. The endpoints attain it. Again, the multiplier is simply 1.

Equality constraints allow unrestricted multipliers because their contribution vanishes on the feasible set regardless of sign. If x²=1, then x²−1 itself is zero on K. Requiring its equality multiplier to be SOS would impose an unnecessary restriction on the certificate search.

Verify an equality-constrained two-variable example

Minimise x²+y² subject to x+y=4, with both variables real. The identity x²+y²−8=½(x−y)²+½(x+y+4)(x+y−4) provides the certificate. On the equality set, the second term vanishes; the first is a square multiplied by a positive constant. Thus the cost is at least eight.

Equality in the bound requires x=y together with x+y=4, giving x=y=2. At the feasible trial x=3,y=1, the cost is ten and the certificate remainder is ½(3−1)²=2. The objective gap and the squared imbalance agree exactly.

Here the equality multiplier is the polynomial ½(x+y+4). Its sign away from the equality set is irrelevant because the constraint factor vanishes wherever the decision is allowed. If the requirement changes to x+y=6, both the proposed bound and the identity must change. Substitution gives the new minimum eighteen at x=y=3. The familiar instruction to balance the variables is therefore supported by an explicit domain-specific proof, rather than an assumption that equal allocation is always optimal.

The sign convention must remain consistent. This chapter uses g≥0. A formula copied from a source using g≤0 requires a corresponding sign change. Before trusting a bound, evaluate every constraint at an obvious feasible point and check that the claimed nonnegative products really are nonnegative there.

Previous chapter · Contents · Next chapter

Return to p(x)=x⁴−2x², now restricted to 0≤x≤½. Let t=x². Then 0≤t≤¼ and p=t²−2t. The difference from the endpoint value is p+7/16=(t−¼)(t−7/4).

Both factors are nonpositive on the permitted interval, so their product is nonnegative. This proves p≥−7/16, attained at x=½. The unrestricted bound −1 remains valid but is weaker; it cannot detect that the unrestricted minimisers are excluded.

Express the same proof as a weighted SOS identity

Use the equivalent constraints x≥0 and g(x)=¼−x²≥0. Since t−¼=−g and t−7/4=−(g+3/2), we obtain p+7/16=g²+(3/2)g. The first term is a square. The coefficient 3/2 is also SOS, being the square of √(3/2).

This explicit certificate proves the lower bound everywhere g≥0, including the slightly larger symmetric interval [−½,½]. That is acceptable: a proof on a larger set remains a proof on the intended smaller set. The additional x≥0 constraint is still needed to describe the original decisions and select the relevant minimiser.

At x=0.4, p=0.0256−0.32=−0.2944. Its difference from −0.4375 is 0.1431. Here g=0.09, and g²+1.5g=0.0081+0.135=0.1431, independently confirming the arithmetic.

Notice how the certificate exposes the mechanism of suboptimality. The endpoint has g=0. Moving into the interval creates positive slack, and the displayed remainder translates that slack into objective loss. It is more informative than a statement that a numerical search happened to return 0.5.

Try changing the upper bound to c with 0<c<1. Replacing ¼ by c² gives p(x)−p(c)=(c²−x²)²+2(1−c²)(c²−x²). Both coefficients have the required signs. The transfer chapter will examine what changes when c passes through one.

Previous chapter · Contents · Next chapter

The moment approach replaces a single point by quantities that would be averages of monomials under a probability measure supported on K. For one variable, write yₖ as the expected value of xᵏ and set y₀=1. A point a corresponds to the special sequence yₖ=aᵏ.

If a polynomial square is nonnegative, its expectation must be nonnegative. For z=(1,x,x²), this says that the moment matrix M₂=[[y₀,y₁,y₂],[y₁,y₂,y₃],[y₂,y₃,y₄]] is positive semidefinite. The expectation of the quartic objective is y₄−2y₂, a linear expression in the moments.

Mix the two global minimisers

Put probability one half at −1 and one half at 1. Then y₀=1, y₁=0, y₂=1, y₃=0 and y₄=1. The expected objective is −1. The matrix is [[1,0,1],[0,1,0],[1,0,1]], which is positive semidefinite because it averages two outer products z(a)z(a)ᵀ.

The first moment y₁ is zero, but zero is not a minimiser of the quartic. This example explains why reading the mean as the solution can fail. The moments can describe a mixture of several optimal decisions rather than one decision at their average.

A finite relaxation keeps only finitely many moments and necessary matrix conditions. Not every feasible truncated array must come from a genuine measure with the intended support. Enlarging the feasible description in this way can lower the relaxed optimum below the true minimum.

Lasserre’s original paper on global polynomial optimisation and moments develops this approach. For the present example, the identity from chapter 3 explains the bound directly: the expected value of (x²−1)² cannot be negative, so y₄−2y₂≥−1 whenever the relevant moment matrix enforces that square’s nonnegativity.

Previous chapter · Contents · Next chapter

Moments of arbitrary real points are not enough when the problem restricts x. If g(x)≥0 on K, then the expected value of g(x)q(x)² must be nonnegative for every polynomial q. At a chosen degree, these requirements form a localising matrix.

For the interval [−1,1], use g=1−x². With q=a+bx, expansion gives the matrix [[y₀−y₂,y₁−y₃],[y₁−y₃,y₂−y₄]]. Positive semidefiniteness of this matrix ensures the corresponding quadratic form is nonnegative for every a,b.

Reject an impossible support claim

A point mass at x=2 has y₀=1 and y₂=4. Its ordinary moment matrices are positive semidefinite: it is a genuine measure on the real line. But y₀−y₂=−3, violating even the simplest localising condition for [−1,1]. The support constraint distinguishes the relevant measures from irrelevant ones.

The symmetric mixture at ±1 gives a zero localising matrix, because 1−x² vanishes at both support points. This is consistent with both points lying exactly on the interval boundary. A singular or zero localising matrix can reflect valid boundary support rather than a numerical defect.

For an equality h=0, the expected values of h times the permitted test monomials should vanish. These linear equations encode support on the equality set. Forgetting them changes the relaxation, sometimes dramatically, even when the objective and ordinary moment matrix remain unchanged.

Degree bookkeeping matters. A relaxation containing moments through degree 2d can only form products whose total degree fits that limit. If g has degree two, q can have degree at most d−1 in the usual localising construction. Asking for unavailable higher moments without adding them produces an incomplete or inconsistent model.

When debugging, expand one entry by hand. For example, the bottom-right entry above is the expectation of x²(1−x²)=x²−x⁴. This simple check catches misplaced indices more effectively than inspecting a large symbolic matrix at a glance.

Previous chapter · Contents · Next chapter

Increasing the allowed certificate degree enlarges the family of SOS bounds that can be searched. Equivalently, higher moment relaxations impose additional consistency conditions. Under suitable assumptions, these increasingly strong relaxations approach the global optimum. The conditions and the chosen hierarchy must be stated, not hidden behind the word convergence.

For a commonly used quadratic-module hierarchy, an Archimedean condition supplies a boundedness certificate of the form R−||x||² within the module. A valid redundant ball constraint can enforce this condition when a bounding ball for K is known. Compactness of K alone should not be casually substituted for every representation-specific hypothesis.

More degree has a measurable cost

The number of monomials in n variables of total degree at most d is the binomial coefficient C(n+d,d). For n=3,d=2, the basis contains ten monomials, producing a ten-by-ten Gram matrix. For n=10,d=4, it contains 1001 monomials, producing a matrix with over half a million distinct symmetric entries before exploiting structure.

The contrast explains why a low-degree toy calculation does not imply that a large engineering model is inexpensive. Sparse interactions, symmetry and specialised formulations may help, but they must preserve the required certificate logic. Removing apparently inconvenient terms without justification changes the mathematical claim.

Finite convergence occurs for some problems and formulations, but it is not an unconditional promise. A sequence of valid bounds can improve indefinitely without attaining the exact optimum at a predetermined small degree. Likewise, a solver’s numerical success at one order does not prove the assumptions of an asymptotic theorem.

The LAAS-CNRS overview of moments and positive polynomials connects the two sides of the hierarchy and its applications. Use it as a route into the theory while keeping a separate record of what your particular finite computation has actually certified.

Previous chapter · Contents · Next chapter

A lower bound is valuable even when a relaxation does not immediately return a feasible minimiser. To complete an optimisation task, obtain a candidate in the original variable space and check every original constraint. Do not substitute a vector of moments for a vector of decisions merely because both are arrays of numbers.

For the quartic mixture, the moment matrix has the relation corresponding to x²−1. Solving x²−1=0 yields the candidate support points −1 and 1. Both are feasible in the unrestricted problem, and both have objective −1, matching the lower bound.

Rank contains information, but tolerance matters

A rank-one moment matrix associated with a point measure can make extraction straightforward. Higher rank can represent several support points. General extraction procedures use additional rank and consistency conditions; a numerical rank estimate alone should not be treated as an exact theorem about a measure.

If eigenvalues are near the chosen tolerance, repeat the assessment with justified scaling and, where appropriate, higher precision or an exact reconstruction. Changing a threshold until the desired rank appears is not verification. Record the threshold and explain how the candidate was checked afterwards.

Candidate validation should include the unscaled original problem. A transformed variable u may correspond to x=10u+3. Feasibility and objective values reported in u-coordinates must be translated back before operational interpretation. Bounds require the same treatment if the objective was divided by a constant or shifted.

If extraction fails, report the valid lower bound and the best independently feasible upper bound separately. The gap tells the reader what remains unresolved. It is more honest and more useful than labelling the relaxation’s first moments as the optimal design without checking them.

The supporting equations in an SOS certificate offer another extraction route: where a sum of nonnegative terms attains zero, each contributing positive-weight square must vanish. Boundary terms may vanish through either their multiplier or their constraint factor, so examine those alternatives rather than assuming every factor must separately be zero.

Previous chapter · Contents · Next chapter

A floating-point Gram matrix that is nearly positive semidefinite and nearly matches coefficients is evidence, not automatically an exact proof. Both discrepancies matter. A tiny negative eigenvalue can invalidate nonnegativity; a small coefficient residual can become large when multiplied by large powers of an unbounded variable.

On a bounded domain, coefficient residuals can sometimes be converted into rigorous error allowances. If a residual polynomial is e(x)=Σeαxα and every |xᵢ|≤Rᵢ, then |e(x)|≤Σ|eα|ΠRᵢ^αᵢ. Subtracting a valid residual bound from a proposed lower bound can restore a conservative certificate, provided the matrix nonnegativity is also rigorously established.

Work a residual allowance

Suppose an exact nonnegative certificate proves q(x)≥0 on [−1,1], but the target relation is p(x)−γ=q(x)+e(x), with e(x)=0.001x²−0.002x. The triangle bound gives |e|≤0.003. Therefore p≥γ−0.003 on the interval. The correction is conservative and explicit.

For |x|≤10, the same coefficient bound becomes 0.1+0.02=0.12. Coefficients that seemed negligible on a normalised interval are no longer negligible. This is why domain scaling belongs in the certificate record rather than being dismissed as a cosmetic implementation detail.

An exact polynomial optimum also inherits the limitations of the model. A fitted response curve may be unreliable outside its calibration range, or its coefficients may have uncertainty large enough to change the preferred decision. The specialist article on crop yields, fertiliser rates and response curves illustrates why response shape and real operating conditions must be considered together.

Distinguish three questions in the final interpretation: was the mathematical model solved, does its uncertainty permit a stable decision, and does the model represent the actual system adequately? A sum-of-squares identity answers the first question for its specified coefficients and domain. It does not by itself answer the other two.

Previous chapter · Contents · Next chapter

Let p(x)=x⁴−2x² on 0≤x≤c, where c>0. Predict the answer before manipulating formulas. If c<1, the interval stops before the positive unrestricted minimiser, so the upper endpoint should be optimal. If c≥1, x=1 becomes feasible and the global bound −1 becomes attainable.

For 0<c≤1, set g=c²−x². Expanding gives p(x)−p(c)=g²+2(1−c²)g. Because g≥0 and 1−c²≥0, this proves p(x)≥p(c). The endpoint x=c attains equality.

Explain why the same certificate stops working

When c>1, the coefficient 2(1−c²) is negative. The displayed identity remains algebraically true, but its nonnegativity argument no longer holds. An identity and a sign certificate are different objects. Copying the identity without checking its changed coefficient would falsely certify the endpoint.

Take c=1.2. The endpoint value is 1.2⁴−2·1.2²=−0.8064, while x=1 has value −1. The endpoint is feasible but suboptimal by 0.1936. The unrestricted certificate p+1=(x²−1)² remains valid and is now sharp on the interval.

At c=0.8, the endpoint value is 0.4096−1.28=−0.8704. The same unrestricted bound −1 is valid but has a gap of 0.1296. The interval certificate closes that gap because it uses information about the excluded region.

Now change the domain to −c≤x≤c. The minimum value is unchanged, but the minimisers come in pairs except at degenerate cases. If an application requires a positive setting, that physical constraint selects one member; it is not legitimate to discard a negative solution solely because it looks inconvenient after solving an unrestricted model.

To demonstrate transfer, explain which facts changed at c=1: feasibility of the unrestricted minimiser, the sign of a certificate multiplier, and the location of the optimum. A learner who can track those three changes understands more than a formula for one endpoint.

Previous chapter · Contents · Next chapter

Is polynomial optimization always convex?

No. A polynomial objective can have several local minima, and polynomial constraints can define disconnected sets. SOS and moment methods often build convex relaxations or certificate searches around the original nonconvex problem. The convexity belongs to that auxiliary construction and should not be attributed automatically to the original decision space.

Does failure of an SOS search prove a negative value exists?

No. The chosen degree or certificate family may be too restrictive, numerical difficulties may intervene, or the polynomial may be nonnegative without belonging to that SOS class. A negative feasible evaluation proves failure of nonnegativity; inability to find a particular proof is a different kind of evidence.

Can the mean of optimal moments be used as the decision?

Not without checking. The equal mixture at −1 and 1 has mean zero, which is not optimal for the quartic. Recover support points or obtain another feasible candidate, then compare its objective with the lower bound. Always return to the original constraints.

What should a beginner practise first?

Begin with square completion and factor signs on intervals. Reproduce the quartic certificates, expand them back into coefficients and check their equality conditions. Then construct the three-by-three Gram matrix by hand. Finally calculate the moments of a two-point distribution and verify the corresponding matrix entries.

A useful small project is a certificate notebook with one page per problem. Record the exact polynomial, its domain, a feasible candidate, a proposed lower bound, the expanded identity and the equality conditions. Add a changed-domain version on the same page. This makes hidden dependencies visible without requiring a large optimisation package.

For further study, use MIT’s algebraic techniques and semidefinite optimisation lectures for the progression from positive semidefinite matrices to polynomial certificates. Follow the linked Parrilo and Lasserre sources for the foundational formulations. Read theorem hypotheses beside the numerical examples rather than treating them as optional formalities.

In an applied project, retain the distinction between exploration and proof. Plots, local searches and simulations help find good candidates and reveal modelling mistakes. Exact identities, rigorously controlled numerical bounds and checked feasibility establish what can be claimed globally. A dependable result explains both how the candidate was found and why unexamined feasible alternatives cannot improve it beyond the stated gap.

Previous chapter · Contents · Gold Standard master