Sums of SquaresSanjay LallStanford UniversityEE364bApril 19, 20112 Sum of Squares S. Lall, Stanford 2011.04.18.01polynomial programmingA familiar problemminimize f0(x)subject to fi(x) ≤ 0 for all i = 1, . . . , mhi(x) = 0 for all i = 1, . . . , pin this section, objective, inequality and equality constraint functions areallpolynomials3 Sum of Squares S. Lall, Stanford 2011.04.18.01polynomial nonnegativitydoes there exist x ∈ Rnsuch that f(x) < 0• if not, f is called positive semidefinite or PSDf(x) ≥ 0 for all x ∈ Rn• the problem is NP-hard, but decidable4 Sum of Squares S. Lall, Stanford 2011.04.18.01certificatesdoes there exist x ∈ Rnsuch that f(x) < 0• answer yes is easy to verify; exhibit x such that f(x) < 0• answer no is hard; we need a certificate or a witnessi.e, a proof that there is no feasible point5 Sum of Squares S. Lall, Stanford 2011.04.18.01Sum of Squares Decompositionf is nonnegative if there are polynomials g1, . . . , gssuch thatf =sXi=1g2ia checkable certificate, called asum-of-squares (SOS) decomposition• how do we find the gi• when does such a certificate exist?6 Sum of Squares S. Lall, Stanford 2011.04.18.01examplewe can write any polynomial as a quadratic function of monomialsf = 4x4+ 4x3y − 7x2y2− 2xy3+ 10y4=x2xyy2T4 2 −λ2 −7 + 2λ −1−λ −1 10x2xyy2= zTQ(λ)z• above equation holds for all λ ∈ R• if for some λ we have Q(λ) º 0, then we can factorize Q(λ)7 Sum of Squares S. Lall, Stanford 2011.04.18.01example, continuede.g., with λ = 6, we haveQ(λ) =4 2 −62 5 −1−6 −1 10=0 22 11 −3·0 2 12 1 −3¸so we have an SOS decompositionf =x2xyy2T0 22 11 −3·0 2 12 1 −3¸x2xyy2=°°°°·2xy + y22x2+ xy − 3y2¸°°°°2=¡2xy + y2¢2+¡2x2+ xy − 3y2¢28 Sum of Squares S. Lall, Stanford 2011.04.18.01sum of squares and semidefinite programmingsuppose f ∈ R[x1, . . . , xn], of degree 2dlet z be a vector of all monomials of degree less than or equal to df is SOS if and only if there exists Q such thatQ º 0f = zTQz• this is an SDP in standard primal form• the number of components of z is¡n+dd¢• comparing terms gives affine constraints on the elements of Q9 Sum of Squares S. Lall, Stanford 2011.04.18.01sum of squares and semidefinite programmingif Q is a feasible point of the SDP, then to construct the SOS representationfactorize Q = V VT, and write V =£v1. . . vr¤, so thatf = zTV VTz= kVTzk2=rXi=1(vTiz)2• one can factorize using e.g., Cholesky or eigenvalue decomposition• the number of squares r equals the rank of Q10 Sum of Squares S. Lall, Stanford 2011.04.18.01examplef = 2x4+ 2x3y − x2y2+ 5y4=x2xyy2Tq11q12q13q12q22q23q13q23q33x2xyy2= q11x4+ 2q12x3y + (q22+ 2q13)x2y2+ 2q23xy3+ q33y4so f is SOS if and only if there exists Q satisfying the SDPQ º 0 q11= 2 2q12= 22q12+ q22= −1 2q23= 0q33= 511 Sum of Squares S. Lall, Stanford 2011.04.18.01convexitythe sets of PSD and SOS polynomials are a convex cones; i.e.,f, g PSD =⇒ λf + µg is PSD for all λ, µ ≥ 0let Pn,dbe the set of PSD polynomials of degree ≤ dlet Σn,dbe the set of SOS polynomials of degree ≤ d• both Pn,dand Σn,dare convex cones in RNwhere N =¡n+dd¢• we know Σn,d⊂ Pn,d, and testing if f ∈ Pn,dis NP-hard• but testing if f ∈ Σn,dis an SDP (but a large one)12 Sum of Squares S. Lall, Stanford 2011.04.18.01polynomials in one variableif f ∈ R[x], then f is SOS if and only if f is PSDexampleall real roots must have even multiplicity, and highest coeff. is positivef = x6− 10x5+ 51x4− 166x3+ 342x2− 400x + 200= (x − 2)2¡x − (2 + i)¢¡x − (2 − i)¢¡x − (1 + 3i)¢¡x − (1 − 3i)¢now reorder complex conjugate roots= (x − 2)2¡x − (2 + i)¢¡x − (1 + 3i)¢¡x − (2 − i)¢¡x − (1 − 3i)¢= (x − 2)2¡(x2− 3x − 1) − i(4x − 7)¢¡(x2− 3x − 1) + i(4x − 7)¢= (x − 2)2¡(x2− 3x − 1)2+ (4x − 7)2¢so every PSD scalar polynomial is the sum ofone or two squares13 Sum of Squares S. Lall, Stanford 2011.04.18.01quadratic polynomialsa quadratic polynomial in n variables is PSD if and only if it is SOSbecause it is PSD if and only iff = xTQxwhere Q ≥ 0and it is SOS if and only iff =Xi(vTix)2= xT³XivivTi´x14 Sum of Squares S. Lall, Stanford 2011.04.18.01some backgroundIn 1888, Hilbert showed that PSD=SOS if and only if• d = 2, i.e., quadratic polynomials• n = 1, i.e., univariate polynomials• d = 4, n = 2, i.e., quartic polynomials in two variablesdn\2 4 6 81 yes yes yes yes2yes yes no no3yes no no no4yes no no no• in general f is PSD does not imply f is SOS15 Sum of Squares S. Lall, Stanford 2011.04.18.01some background• Connections with Hilbert’s 17th problem, solved by Artin: every PSDpolynomial is a SOS ofrational functions.• If f is not SOS, then can try with gf, for some g.• For fixed f, can optimize over g too• Otherwise, can use a “universal” construction of P´olya-Reznick.More about this later.−1−0.500.51−1−0.500.5100.20.40.60.811.2xM(x,y,1)y16 Sum of Squares S. Lall, Stanford 2011.04.18.01The Motzkin PolynomialA positive semidefinite polynomial,that isnot a sum of squares.M(x, y) = x2y4+ x4y2+ 1 − 3x2y2• Nonnegativity follows from the arithmetic-geometric inequalityapplied to (x2y4, x4y2, 1)• Introduce a nonnegative factor x2+ y2+ 1• Solving the SDPs we obtain the decomposition:(x2+ y2+ 1) M(x, y) = (x2y − y)2+ (xy2− x)2+ (x2y2− 1)2++14(xy3− x3y)2+34(xy3+ x3y − 2xy)217 Sum of Squares S. Lall, Stanford 2011.04.18.01The Univariate Case:f(x) = a0+ a1x + a2x2+ a3x3+ · · · + a2dx2d=1x...xdTq00q01. . . q0dq01q11. . . q1d............q0dq1d. . . qdd1x...xd=dXi=0µXj+k=iqjk¶xi• In the univariate case, the SOS condition is exactly equivalent to non-negativity.• The matrices Aiin the SDP have a Hankel structure. This can beexploited for efficient computation.18 Sum of Squares S. Lall, Stanford 2011.04.18.01About SOS/SDP• The resulting SDP problem is polynomially sized (in n, for fixed d).• By properly choosing the monomials, we can exploit structure (sparsity,symmetries, ideal structure).• An important feature: the problem is still a SDP if the coefficients ofF are variable, and the dependence is affine.• Can optimize over SOS polynomials in affinely described families.For instance, if we have p(x) =