Sum of Squares Optimization
and
Its Applications
Amir Ali Ahmadi
Princeton University
Dept. of Operations Research and Financial Engineering (ORFE)
ORF 523
1
Optimization over nonnegative polynomials
nonnegative over a given basic semialgebraic set?
Basic semialgebraic set:
-This problem is fundamental to many areas of applied/computational mathematics.
-It is the problem that “SOS optimization” is designed to solve.
2
Why would you want
to do this?!
▪Let’s start with five application domains…
1. Polynomial optimization
▪Many applications: the optimal power flow problem, low-rank matrix
factorization, dictionary learning, training of deep nets with polynomial
activation function, sparse regression with nonconvex regularizes, etc.
▪Intractable in general (includes your favorite NP-complete problem)
4
2. Optimization under input uncertainty
How to make optimal decisions when input to optimization problem is uncertain/noisy?
Example: The Markowitz portfolio optimization problem
Accounting for uncertainty:
In practice estimated from past
data/ML model. Optimal portfolio
sensitive to this input.
5
3. Statistics and machine learning
Shape-constrained regression; e.g., monotone and/or convex regression
Shape constraints act as regularizer, improve test performance,
make model more interpretable and trustworthy
Example 1: Shape constraints natural in most applications
Example 2: “ML for fast real-time convex optimization”
6
Imposing monotonicity
7
4. Certifying properties of dynamical systems
Example: certifying stability
Ex.
Locally asymptotic stability (LAS) of
equilibrium points
Lyapunov’s theorem (and its converse):
The origin is LAS if and only if there exists a
𝐶 1 function 𝑉: ℝ𝑛 → ℝ that vanishes at the
origin and a scalar 𝛽 > 0 such that
𝑉 𝑥 >0
ሶ
𝑉 𝑥 ≤ 𝛽 ⇒ 𝑉(𝑥) = 𝛻𝑉 𝑥 𝑇 𝑓 𝑥 < 0
5. Automated theorem proving in geometry
Newton Gregory
Discussion/bet in 1694
Newton proved to be
13 spheres impossible iff the following system is infeasible: correct in 1953!
Outline of the rest of the talk…
• Global nonnegativity
– Sum of squares (SOS) and semidefinite programming
– Two applications
– Hilbert’s 17th problem
• Nonnegativity over a region
– Positivstellensatze of Stengle and Putinar
– Three applications
• Recap and further reading
11
How would you prove nonnegativity?
Ex. Decide if the following polynomial is nonnegative:
▪Not so easy! (In fact, NP-hard for degree ≥ 4)
▪But what if I told you:
Natural questions:
•Q1: Is it any easier to test for a sum of squares (SOS) decomposition?
•Q2: Is every nonnegative polynomial SOS?
12
Sum of squares and semidefinite programming
[Lasserre], [Nesterov], [Parrilo]
Q1: Is it any easier to decide SOS?
▪Yes! Can be reduced to a semidefinite program (SDP)
▪Can also efficiently search and optimize over SOS polynomials
▪As we will see, this latter property is very important in
applications…
13
Semidefinite programming (SDP)
• A broad generalization of linear programs
• Can be solved to arbitrary accuracy in polynomial time (e.g., using interior
point algorithms) [Nesterov, Nemirovski], [Alizadeh]
Feasible set called a “spectrahedron”:
14
SOS→SDP
Thm:
(It follows that checking membership or optimizing a linear function over the set of
SOS polynomials is an SDP)
15
Example
16
Let’s revisit two of
our applications!
Optimization over
nonnegative
polynomials
Sum of squares
(SOS)
programming
Semidefinite
programming
(SDP)
1
8
1) Nonconvex unconstrained minimization
19
2) Automated proof of global asymptotic stability
20
Automated proof of global asymptotic stability
21
Hilbert’s 1888 Paper
? Nonnegativity
Q2: SOS
n,d 2 4 ≥6
1 yes yes yes
2 yes yes no
From Logicomix
3 yes no no
≥4 yes no no
Motzkin (1967):
Robinson (1973):
22
The Motzkin polynomial
How to prove it is nonnegative?
How to prove it is not SOS?
23
Hilbert’s 17th Problem (1900)
?
Q. p nonnegative
▪Artin (1927): Yes!
24
Outline of the rest of the talk…
• Global nonnegativity
– Sum of squares (SOS) and semidefinite programming
– Two applications
– Hilbert’s 17th problem
• Nonnegativity over a region
– Positivstellensatze of Stengle and Putinar
– Three applications
• Recap and further reading
25
Positivstellensatz
Artin
Stengle
1927 20th century 1974 1991 1993
Schmudgen Putinar
26
Positivstellensatz: a complete algebraic proof system
▪Let’s motivate it with a toy example:
Consider the task of proving the statement:
Short algebraic proof (certificate):
▪The Positivstellensatz vastly generalizes what happened here:
▪ Algebraic certificates of infeasibility of any system of
polynomial inequalities (or algebraic implications among them)
▪ Automated proof system (via semidefinite programming)
27
Positivstellensatz: a generalization of Farkas lemma
Farkas lemma (1902):
is infeasible
(The S-lemma is also a theorem of this type for quadratics)
28
Stengle’s Positivstellensatz (1974)
29
Putinar’s Positivstellensatz (1993)
easy direction
▪ This is algebraic certificate of positivity
▪ Leads to an SDP hierarchy for polynomial optimization
(the ``Lasserre hierarchy’’)
▪ Degree bounds on SOS multipliers based on the coefficients
(though in special cases, better degree bounds possible)
30
How did I plot this?
31
Let’s end with 3 Optimization over
applications: nonnegative
polynomials
• Finance
Sum of squares
• Control (SOS)
programming
• Learning dynamical
systems Semidefinite
programming
(SDP)
Distributionally robust optimization
What’s the probability that Zoom’s stock goes bust?
▪Three months starting Feb 1, 2020
33
Sum of squares optimization can compute this probability!
34
SOS proofs of local asymptotic stability (LAS)
• Deals with nonlinear systems directly.
• Gives easily-verifiable proofs of stability
in a fully-automated fashion.
35
Local stability – SOS on the Acrobot
Swing-up:
Balance:
(4-state system)
Controller
designed by SOS
(w/ Majumdar and Tedrake)
36
Stabilizing a humanoid robot on one foot
30 states 14 control inputs Cubic dynamics
(w/ Majumdar and Tedrake) 37
Learning dynamical systems with side information
Examples of “side information”:
• Equilibrium points (and their
stability)
• Invariance of certain sets
• Decrease of certain energy functions
• Sign conditions on derivatives of
states
• Having gradient structure
• Monotonicity conditions
• Incremental stability
• (Non)reachability of a set B from a
set A, …
An epidemiology example
A model from the epidemiology
literature for spread of Gonorrhea in
a heterosexual population:
• The dynamics (both its parameters and
its special structure) is unknown to us.
• We only get to observe noisy trajectories
of this dynamical system.
The setup
Least squares solution
f(0)=0 • Good performance on the observed trajectory. Terrible
elsewhere.
Fraction of infected individuals cannot go negative or more than one!
The unit square must be an invariant set!!
• Better, but not perfect. What other side information can you think of?
More infected females should imply higher infection rate for males!
(and vice versa)
Side information: directional monotonicity
• Now we are getting the qualitative behavior correct everywhere!
The SDP that is being solved in the background
Output of SDP solver:
p1=0.2681*x^3 - 0.0361*x^2*y - 0.095*x*y^2 + 0.1409*y^3 - 0.4399*x^2 + 0.0956*x*y - 0.0805*y^2 + 0.1232*x + 0.0201*y
p2=0.1188*x^3 + 0.2606*x^2*y + 0.2070*x*y^2 + 0.0005*y^3 - 0.3037*x^2 - 0.4809*x*y -0.099*y^2+ 0.2794*x+0.01689*y
Recap: “See an inequality? Think SOS!”
Automated SOS-based proofs via SDP!
Many applications!
Optimization Control Learning
Want to learn more?
49
