First-order methods for
Sum of Squares Optimization
Presented by Chenyang Yuan
Joint work with Benoît Legat and Pablo ParriloIntroduction
Semideﬁnite programming (SDP) is a very powerful and expressive
convex optimization method
Positive semideﬁnite variable X≽0 + linear constraints
Applications: Optimal control, convex relaxations of combinatorial
optimization, rank minimization and nuclear norm, ...

Typically solved with expensive interior point methods (n∼103)
Deep Learning uses gradient-based solvers on large scale problems
Very successful on various classiﬁcation and inference tasks
Solved with highly parallelized ﬁrst-order methods (n > 108)

Can we apply these techniques to solving SDPs?

Introduction
Burer-Monteiro methods factor PSD constraint X = UUT, then perform local
optimization on resulting non-convex unconstrained problem

Feasible

Optimum = 0

May get stuck in local optimum (explicit counterexamples where second-order
critical point ≠ global minimum)
When is non-convexity benign?

Related work
For general SDP feasibility with m linear constraints, with the factorization X = UUT,
where U is a nхr matrix.
Second-order critical point ⇒ Global minimum (non-convexity benign) when:●●r > n [Burer and Monteiro]r = Ω(√m), but with smoothed analysis [Cifuentes and Moitra], genericconstraints [Bhojanapalli, Boumal, Jain, Netrapalli], or determinant
regularization [Burer and Monteiro], (necessary because of counterexamples)
Can we do better if the SDP has special structure?

Samuel Burer and Renato Monteiro. (2005) Local Minima and Convergence in Low-Rank Semideﬁnite Programming, Mathematical Programming.
Diego Cifuentes and Ankur Moitra. (2019) Polynomial time guarantees for the Burer-Monteiro method, arXiv:1912.01745.
Srinadh Bhojanapalli, Nicolas Boumal, Prateek Jain, Praneeth Netrapalli (2018) Smoothed analysis for low-rank solutions to semideﬁnite programs in quadratic penalty form, Conference on Learning Theory.

Sum of Squares Optimization
Given p(x), can we write it as a sum of squares?
Certiﬁes that p(x) ≥ 0, and can be formulated as SDP
Focus on univariate trigonometric polynomials in this talk (methods can begeneralized to multivariate case)Applications in signal processing, ﬁlter design andcontrol
Image credit: Tae Roh and Lieven Vandenberghe. (2006) Discrete transforms, semideﬁnite programming and sum-of-squares representations of nonnegative polynomials. SIAM J. on Optimization.

Contributions
Find sum of squares decomposition of p(x) by solving

For any norm on polynomials, if f(u) = 0, sum of squares
decomposition agrees with p(x)Theorem: when r ≥ 2 (vs r = Ω(√m)) ﬁrst-order methods ﬁnd
sum of squares decomposition for univariate polynomials(non-convexity benign)If we choose right norm, ∇f(u) can be computed inO(n log n) time using fast fourier transforms (FFTs)
Image credit: Chi Yuejie, Lu Yue, Chen Yuxin. (2019) Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview. IEEE Transactions on Signal Processing.

Proof Sketch
Assume that p(x) is a univariate polynomial and r = 2

Given u such that ∇f(u)(v) = 0 and ∇2f(u)(v,v) ≥ 0 for all v, show that f(u) = 0
We have inner product <p(x),q(x)> on polynomials with associated norm ||.||:

Proof Sketch{ p | ∇fp(u) = 0 }Geometrically, we want to show that theonly intersection between set with zero
gradient and PSD Hessian is when f(u) = 0.
For ﬁxed u, these sets are convex!

p=u12 + u22{ p | ∇2fp(u) ≥ 0}

Our proof can be interpreted as ﬁnding a certiﬁcate of this condition
for every u and p.

Proof Sketch

Suppose u1 , u2 coprime (true generically)
Bézout's lemma + gradient condition ⇒ exist v1 , v2 s.t.

Suppose u1 = u2 , choose v1 = v and v2 = -v in Hessian condition so for all v,However,(gradient condition), soInterpolate between these two cases with the Positivstellensatz

Sampled basis
Which inner product <p(x),q(x)> on polynomials to choose?
Given p(x), q(x) degree d, choose d+1 points xk

Valid inner product: when xk are distinct points, if ||p(x)||2 = 0 then p(x) = 0.
Sum of squares using a sampled/interpolation basis studied by [Löfberg and Parrilo]and [Cifuentes and Parrilo]
How should we choose xk?
Diego Cifuentes and Pablo Parrilo. (2017) Sampling algebraic varieties for sum of squares programs, SIAM J. Optimization.
Johan Lofberg and Pablo Parrilo. (2004) From coeﬃcients to samples: a new approach to SOS optimization, 43rd IEEE Conference on Decision and Control.

Numerical Implementation
Compute sum of squares decomposition ofdegree 4n trigonometric polynomial

Using basis vectors evaluated at 4n + 1 points

Matrix-vector products in ∇f(U) can be computed by FFT

Image credit: Christos Papadimitriou, Sanjoy Dasgupta, and Umesh Vazirani. (2006) Algorithms

Numerical Implementation
TrigPolys.jl: a new package for fast manipulation of trigonometric polynomials

evaluate, evaluateT and interpolate uses FFTW.jl, enables fast computation of f(U):AutoGrad.jl enables automatic computation of ∇f(U)Pass f(U), ∇f(U) to NLopt.jl to minimize f(U) with ﬁrst-order optimization algorithms

Results
Sum of squares decomposition for
random trigonometric polynomial
Convergence rate for LBFGS withrandom initialization:
Running times (stop at 10-7 relative error in U):
Degree of p(x)

1000

5000

10,00050,000100,000

Time (s)151145112

Conclusion
When does it make sense to solve non-convex formulations of convex problems?
In our setting we can prove non-convexity does not hurt us
Also enables fast implementation in Julia