Sum of squares optimization

Optimization problem

The problem can be expressed as

subject to

Here "SOS" represents the class of sum-of-squares (SOS) polynomials. The vector c ∈ R n and polynomials { a k , j } are given as part of the data for the optimization problem. The quantities u ∈ R n are the decision variables. SOS programs can be converted to semidefinite programs (SDPs) using the duality of the SOS polynomial program and a relaxation for constrained polynomial optimization using positive-semidefinite matrices, see the following section.

Dual problem: constrained polynomial optimization

Suppose we have an n -variate polynomial p ( x ) : R n → R , and suppose that we would like to minimize this polynomial over a subset A ⊆ R n . Suppose furthermore that the constraints on the subset A can be encoded using m polynomial inequalities of degree at most 2 d , each of the form a i ( x ) ≥ b i where a i : R n → R is a polynomial of degree at most 2 d and b i ∈ R . A natural, though generally non-convex program for this optimization problem is the following:

subject to:

where x ⊗ d is the d -wise Kronecker product of x with itself, C is a matrix of coefficients of the polynomial p ( x ) that we want to minimize, and A i is a matrix of coefficients of the polynomial a i ( x ) encoding the i th constraint on the subset A ⊂ R n . The additional, fixed index in our search space, x ∅ = 1 , is added for the convenience of writing the polynomials p ( x ) and a i ( x ) in a matrix representation.

This program is generally non-convex, because the constraints (1) are not convex. One possible convex relaxation for this minimization problem uses semidefinite programming to replace the Kronecker product x ⊗ d ( x ⊗ d ) ⊤ with a positive-semidefinite matrix X : we index each monomial of size at most 2 d by a multiset S of at most 2 d indices, S ⊂ [ n ] ≤ d . For each such monomial, we create a variable X S in the program, and we arrange the variables X S to form the matrix X ∈ R [ n ] ≤ d × [ n ] ≤ d , where we identify the rows and columns of X with multi-subsets of [ n ] . We then write the following semidefinite program in the variables X S :

subject to:

where again C is the matrix of coefficients of the polynomial p ( x ) that we want to minimize, and A i is the matrix of coefficients of the polynomial a i ( x ) encoding the i th constraint on the subset A ⊂ R n .

The third constraint ensures that the value of a monomial that appears several times within the matrix is equal throughout the matrix, and is added to make X behave more like x ⊗ d ( x ⊗ d ) ⊤ .

Duality

One can take the dual of the above semidefinite program and obtain the following program:

subject to:

The dimension m ′ is equal to the number of constraints in the semidefinite program. The constraint C − ∑ i ∈ m ′ y i A i ⪰ 0 ensures that the polynomial represented by C − ∑ i ∈ [ m ′ ] y i A i ⪰ 0 is a sum-of-squares of polynomials: by a characterization of PSD matrices, for any PSD matrix Q ∈ R m × m , we can write Q = ∑ i ∈ [ m ] f i f i ⊤ for vectors f i ∈ R m . Thus for any x ∈ R [ n ] ∪ ∅ with x ∅ = 1 ,

where we have identified the vectors f i with the coefficients of a polynomial of degree at most d . This gives a sum-of-squares proof that the value p ( x ) = ⟨ C , x ⊗ d ( x ⊗ d ) ⊤ ⟩ over A ⊂ R n is at least b ⊤ y , since we have that

where the final inequality comes from the constraint a i ( x ) ≥ b i describing the feasible region A ⊂ R n .

Sum-of-squares hierarchy

The sum-of-squares hierarchy (SOS hierarchy), also known as the Lasserre hierarchy, is a hierarchy of convex relaxations of increasing power and increasing computational cost. For each natural number d ∈ N the corresponding convex relaxation is known as the d th level or d th round of the SOS hierarchy. The 1 st round, when d = 1 , corresponds to a basic semidefinite program, or to sum-of-squares optimization over polynomials of degree at most 2 . To augment the basic convex program at the 1 st level of the hierarchy to d th level, additional variables and constraints are added to the program to have the program consider polynomials of degree at most 2 d .

The SOS hierarchy derives its name from the fact that the value of the objective function at the d th level is bounded with a sum-of-squares proof using polynomials of degree at most 2 d via the dual (see "Duality" above). Consequently, any sum-of-squares proof that uses polynomials of degree at most 2 d can be used to bound the objective value, allowing one to prove guarantees on the tightness of the relaxation.

In conjunction with a theorem of Berg, this further implies that given sufficiently many rounds, the relaxation becomes arbitrarily tight on any fixed interval. Berg's result states that every non-negative real polynomial within a bounded interval can be approximated within accuracy ϵ on that interval with a sum-of-squares of real polynomials of sufficiently high degree, and thus if O B J ( x ) is the polynomial objective value as a function of the point x , if the inequality c + ϵ − O B J ( x ) ≥ 0 holds for all x in the region of interest, then there must be a sum-of-squares proof of this fact. Choosing c to be the minimum of the objective function over the feasible region, we have the result.

Computational cost

When optimizing over a function in n variables, the d th level of the hierarchy can be written as a semidefinite program over n O ( d ) variables, and can be solved in time n O ( d ) using the ellipsoid method.

Sum-of-squares background

A polynomial p is a sum of squares (SOS) if there exist polynomials { f i } i = 1 m such that p = ∑ i = 1 m f i 2 . For example,

is a sum of squares since

where

Note that if p is a sum of squares then p ( x ) ≥ 0 for all x ∈ R n . Detailed descriptions of polynomial SOS are available.

Quadratic forms can be expressed as p ( x ) = x T Q x where Q is a symmetric matrix. Similarly, polynomials of degree ≤ 2d can be expressed as

where the vector z contains all monomials of degree ≤ d . This is known as the Gram matrix form. An important fact is that p is SOS if and only if there exists a symmetric and positive-semidefinite matrix Q such that p ( x ) = z ( x ) T Q z ( x ) . This provides a connection between SOS polynomials and positive-semidefinite matrices.

Software tools