Semidefinite Relaxations of Products ofNonnegative Forms
Workshop on Real Algebraic Geometry and Algorithms forGeometric Constraint Systems

Chenyang Yuan (joint work with Pablo Parrilo)
June 18, 2021

Introduction

How to exploit product structure in polynomial
optimization problems

1

Introduction

How to exploit product structure in polynomial
optimization problems

Computational tractability

1Introduction

How to exploit product structure in polynomial
optimization problems

Computational tractability+
Provable approximation guarantees

1Introduction

Given A = (A1 , . . . , Ad ) where Ai  0, we study the following polynomial
optimization problem on Kn = Rn or Cn :Opt(A) :=maxx∈Kn , kxk=1dY!1/dhx, Ai xi

i=12Introduction

Given A = (A1 , . . . , Ad ) where Ai  0, we study the following polynomial
optimization problem on Kn = Rn or Cn :Opt(A) :=maxx∈Kn , kxk=1dY!1/dhx, Ai xi

i=1

Properties:• High-degree polynomial optimization problem: degree 2d in nvariables

2Introduction

Given A = (A1 , . . . , Ad ) where Ai  0, we study the following polynomial
optimization problem on Kn = Rn or Cn :Opt(A) :=max

x∈Kn , kxk=1dY!1/dhx, Ai xi

i=1

Properties:• High-degree polynomial optimization problem: degree 2d in nvariables• Compact representation: represented in O(n2 d) space2

Introduction

Given A = (A1 , . . . , Ad ) where Ai  0, we study the following polynomial
optimization problem on Kn = Rn or Cn :Opt(A) :=maxx∈Kn , kxk=1dY!1/dhx, Ai xi

i=1

Properties:• High-degree polynomial optimization problem: degree 2d in nvariables• Compact representation: represented in O(n2 d) space• Polynomial time solution when d is fixed, NP-hard when d = Ω(n)2Applications and Motivation
Opt(A) := maxkxk=1

Qd

1/di=1 hx, Ai xi

3

Applications and Motivation
Opt(A) := maxkxk=1

Qd

1/di=1 hx, Ai xi

Kantorovich’s inequality (A1 = Q, A2 = Q −1 ): Given Q  0,qq
2pλ1 (Q)λn (Q)
maxkxk=1 (x T Qx)(x T Q −1 x) ≤ 14
λn (Q) +λ1 (Q)3Applications and Motivation
Opt(A) := maxkxk=1

Qd

1/di=1 hx, Ai xi

Kantorovich’s inequality (A1 = Q, A2 = Q −1 ): Given Q  0,qq
2pλ1 (Q)λn (Q)
maxkxk=1 (x T Qx)(x T Q −1 x) ≤ 14
λn (Q) +λ1 (Q)Approximating permanents of PSD matrices [YP20] (Ai = vi vi† ): Let
M = V † V , vi columns of V .
Qn
2r (M) := maxkxk=1,x∈Cn i=1 |hx, vi i| , nn!n r (M) ≤ per(M)3Applications and MotivationOpt(A) := maxkxk=1

Qd

1/di=1 hx, Ai xi

Kantorovich’s inequality (A1 = Q, A2 = Q −1 ): Given Q  0,qq2pλ1 (Q)λn (Q)
maxkxk=1 (x T Qx)(x T Q −1 x) ≤ 14
λn (Q) +λ1 (Q)Approximating permanents of PSD matrices [YP20] (Ai = vi vi† ): Let
M = V † V , vi columns of V .
Qn
2r (M) := maxkxk=1,x∈Cn i=1 |hx, vi i| , nn!n r (M) ≤ per(M)Portfolio optimization (Ai = diag(ri )): Given rates of return over a time
period r1 , . . . , rT ∈ Rn+ , maximize expected profit:
Q1/dTmaxy ≥0,Pi yi =1i=1 hy , ri i

3

Applications and Motivation
Opt(A) := maxkxk=1

Qd

1/di=1 hx, Ai xi

Kantorovich’s inequality (A1 = Q, A2 = Q −1 ): Given Q  0,qq
2pλ1 (Q)λn (Q)
maxkxk=1 (x T Qx)(x T Q −1 x) ≤ 14
λn (Q) +λ1 (Q)Approximating permanents of PSD matrices [YP20] (Ai = vi vi† ): Let
M = V † V , vi columns of V .
Qn2r (M) := maxkxk=1,x∈Cn i=1 |hx, vi i| , nn!n r (M) ≤ per(M)Portfolio optimization (Ai = diag(ri )): Given rates of return over a time
period r1 , . . . , rT ∈ Rn+ , maximize expected profit:Q
1/dT
maxy ≥0,Pi yi =1i=1 hy , ri i
And more! (Solving systems of quadratic equations, linear polarization
constants, Nash social welfare . . . )3

Our Contributions
Using semidefinite programming (SDP) based approximation algorithms
for general polynomial optimization (Sum-of-Squares):Compute: SDP with O( n+dApprox: Ω( n1 )d ) vars/consts

4

Our Contributions
Using semidefinite programming (SDP) based approximation algorithms
for general polynomial optimization (Sum-of-Squares):Compute: SDP with O( n+dApprox: Ω( n1 )d ) vars/consts
Our relaxation and approximation algorithm that exploits compact
representation:
Compute: SDP with O(n2 d) vars/consts
Approx: Ω(1)4Our Contributions
Using semidefinite programming (SDP) based approximation algorithmsfor general polynomial optimization (Sum-of-Squares):Compute: SDP with O( n+dApprox: Ω( n1 )d ) vars/consts
Our relaxation and approximation algorithm that exploits compact
representation:
Compute: SDP with O(n2 d) vars/consts
Approx: Ω(1)We also:• Prove that when d = Ω(n), NP-hard to approximate

4

Our Contributions
Using semidefinite programming (SDP) based approximation algorithms
for general polynomial optimization (Sum-of-Squares):Compute: SDP with O( n+dApprox: Ω( n1 )d ) vars/consts
Our relaxation and approximation algorithm that exploits compact
representation:
Compute: SDP with O(n2 d) vars/consts
Approx: Ω(1)We also:• Prove that when d = Ω(n), NP-hard to approximate• Introduce higher-degree relaxations that trade off computation withapproximation quality

4

Our Contributions
Using semidefinite programming (SDP) based approximation algorithms
for general polynomial optimization (Sum-of-Squares):Compute: SDP with O( n+dApprox: Ω( n1 )d ) vars/consts
Our relaxation and approximation algorithm that exploits compact
representation:
Compute: SDP with O(n2 d) vars/consts
Approx: Ω(1)We also:• Prove that when d = Ω(n), NP-hard to approximate• Introduce higher-degree relaxations that trade off computation withapproximation quality• Exhibit integrality gap instances that show our analysis of our SDP
based relaxation is tight4

Semidefinite Relaxation
max

kxk=1

1/di=1 hx, Ai xi

Qduse AM-GM

rank-1 relaxmaxX

1/di=1 hX , Ai i

Qds.t. Tr(X ) = 1, X  0(Opt)min λdualλ,αPds.t. d1 i=1 αi Ai  λI (OptSDP)
Qi αi ≥ 1, αi > 05

Semidefinite Relaxation
max

kxk=1

1/di=1 hx, Ai xi

Qduse AM-GMrank-1 relaxmaxX

1/di=1 hX , Ai i

Qds.t. Tr(X ) = 1, X  0(Opt)

min λ
dual

λ,αPd
s.t. d1 i=1 αi Ai  λI (OptSDP)
Qi αi ≥ 1, αi > 0Theorem
Let r = rank(X ∗ ) ≤ n, γ be Euler’s constant, φ be digamma function
cr (K) OptSDP ≤ Opt ≤ OptSDP

5

Semidefinite Relaxation
max

kxk=1

1/di=1 hx, Ai xi

Qduse AM-GM

rank-1 relaxmax
X

1/di=1 hX , Ai i

Qd(Opt)min λλ,αPds.t. d1 i=1 αi Ai  λI (OptSDP)
Qi αi ≥ 1, αi > 0dual

s.t. Tr(X ) = 1, X  0Theorem
Let r = rank(X ∗ ) ≤ n, γ be Euler’s constant, φ be digamma function
cr (K) OptSDP ≤ Opt ≤ OptSDP(cr (K) =exp(−γ − log 2 − φr2

+ logr2) > 0.2807

exp(−γ − φ(r ) + log(r )) > 0.5614

if K = Rif K = C
5Proof Sketch
Rounding algorithm: Given optimum X ∗ , produce unit vector x̂ by:6

Proof Sketch
Rounding algorithm: Given optimum X ∗ , produce unit vector x̂ by:• Sample x ∼ N(0, X ∗ )• Normalize x̂ = x/ kxk

6

Proof Sketch
Rounding algorithm: Given optimum X ∗ , produce unit vector x̂ by:• Sample x ∼ N(0, X ∗ )• Normalize x̂ = x/ kxk
Lower bound expected value of objective:" d#Y1/dOpt ≥ Ehx̂, Ai x̂ii=1!#d1X
log hx̂, Ai x̂i= E exp
di=1!
d1X
≥ exp
E[log hx̂, Ai x̂i]d"i=1≥ cr (K)OptSDP
6

Application: convex hull of image of quadratic map
Let ϕ(x) : Kn → Kd be a quadratic map: x 7→ (hx, A1 xi , . . . , hx, Ad xi)

7Application: convex hull of image of quadratic map
Let ϕ(x) : Kn → Kd be a quadratic map: x 7→ (hx, A1 xi , . . . , hx, Ad xi)
When is ϕ(Kn ) convex? (always true for d = 2, not in general)7Application: convex hull of image of quadratic map
Let ϕ(x) : Kn → Kd be a quadratic map: x 7→ (hx, A1 xi , . . . , hx, Ad xi)
When is ϕ(Kn ) convex? (always true for d = 2, not in general)
How far is ϕ(Kn ) from conv(ϕ(Kn ))? Measure relative entropy distance
between intersection of these cones and the simplex ∆d7

Application: convex hull of image of quadratic map
Let ϕ(x) : Kn → Kd be a quadratic map: x 7→ (hx, A1 xi , . . . , hx, Ad xi)
When is ϕ(Kn ) convex? (always true for d = 2, not in general)
How far is ϕ(Kn ) from conv(ϕ(Kn ))? Measure relative entropy distance
between intersection of these cones and the simplex ∆dTheorem
Let a ∈ conv(ϕ(Kn )) ∩ ∆d . Then there exists a point b ∈ ϕ(Kn ) ∩ ∆dsuch thatD(a k b) =dX
i=1

ai lnaibi≤ log(cr (K))

Proved by Barvinok (2014) for a larger constant, our analysis gives
asymptotically optimal constant7

Higher-order Relaxations
OptSDP constructed using AM/GM inequality. IfdY
i=11/dhx, Ai xi≤ xT1dd
X

Qi αi = 1,!
αi Ai

x

i=1

Can we get a better bound with a higher-degree polynomial on the RHS?

8Higher-order Relaxations
OptSDP constructed using AM/GM inequality. IfdY
i=1

1/dhx, Ai xi

≤ xT

1dd
X

Qi αi = 1,!
αi Ai

x

i=1

Can we get a better bound with a higher-degree polynomial on the RHS?
Let Ek be elementary symmetric polynomials:
 −1 XdEk (y1 , . . . , yd ) =kYxiI ⊆[d],|I |=k i∈I

8Higher-order Relaxations
OptSDP constructed using AM/GM inequality. IfdY

1/dhx, Ai xi≤ xTi=11ddX

Qi αi = 1,!
αi Ai

xi=1Can we get a better bound with a higher-degree polynomial on the RHS?
Let Ek be elementary symmetric polynomials:
 −1 XdEk (y1 , . . . , yd ) =kYxiI ⊆[d],|I |=k i∈I

Maclaurin’s inequality:(y1 · · · yd )1/d1/d= Ed

1/(d−1)≤ Ed−1

1/2≤ · · · ≤ E2

≤ E1 =y1 + · · · + ydd8

Higher-order Relaxations
OptSDP constructed using AM/GM inequality. IfdY1/dhx, Ai xi≤ xTi=11ddX

Qi αi = 1,!
αi Aixi=1

Can we get a better bound with a higher-degree polynomial on the RHS?
Let Ek be elementary symmetric polynomials:
 −1 XdEk (y1 , . . . , yd ) =kYxi

I ⊆[d],|I |=k i∈I

Maclaurin’s inequality:
y1 + · · · + ydd
Use Sum-of-Squares to construct relaxations OptSoSk for 1 ≤ k ≤ d(y1 · · · yd )1/d

1/d= Ed1/(d−1)≤ Ed−1

1/2≤ · · · ≤ E2

≤ E1 =Opt ≤ OptSDP = OptSoS1 ≤ OptSoSd
Trades off computation for accuracy

8

Example: Icosahedral form
Let ψ be golden ratio, C chosen so thatmax

x 2 +y 2 +z 2 =1p(x, y , z) = 1.
2p(x, y , z) = C [(x + ψy )(x − ψy )(y + ψz)(y − ψz)(z + ψx)(z − ψx)]9

Example: Icosahedral form
Let ψ be golden ratio, C chosen so thatmax

x 2 +y 2 +z 2 =1p(x, y , z) = 1.
2p(x, y , z) = C [(x + ψy )(x − ψy )(y + ψz)(y − ψz)(z + ψx)(z − ψx)]

Hard instance because of high degree of symmetry!

9Example: Icosahedral form
Let ψ be golden ratio, C chosen so thatmax

x 2 +y 2 +z 2 =1p(x, y , z) = 1.
2p(x, y , z) = C [(x + ψy )(x − ψy )(y + ψz)(y − ψz)(z + ψx)(z − ψx)]

Hard instance because of high degree of symmetry!
We implement a randomized rounding algorithm to obtain feasible
solution from relaxations OptSoSk
9Distribution sampled from rounding algorithmk = 2, lower: 0.28197, upper: 1.59397

1.000.75/2)

0.50
0.25

sin(0.00
0.25
0.50
0.75
1.00

32

1012

310

Distribution sampled from rounding algorithmk = 3, lower: 0.52128, upper: 1.34164

1.000.75/2)

0.50
0.25

sin(0.00
0.25
0.50
0.75
1.00

32

10

12311

Distribution sampled from rounding algorithmk = 4, lower: 0.65640, upper: 1.18500

1.000.75/2)

0.50
0.25

sin(0.00
0.25
0.50
0.75
1.00

321012312

Distribution sampled from rounding algorithmk = 5, lower: 0.74235, upper: 1.07797

1.000.75/2)

0.50
0.25

sin(0.00
0.25
0.500.75
1.00

32

10

12313

Distribution sampled from rounding algorithm

k = 6, lower: 0.79445, upper: 1.00000

1.000.75/2)

0.50
0.25

sin(0.000.25
0.500.75
1.00

32

10

12

314

Distribution sampled from rounding algorithm

Distribution concentrates towards optima as k increases
15

Conclusion

Takeaways:• Product of PSD forms has nice structure and generalizes many
problems• Exploiting product structure allows us to write a computationallyefficient relaxation with good approximation guarantees

16Conclusion

Takeaways:• Product of PSD forms has nice structure and generalizes many
problems• Exploiting product structure allows us to write a computationallyefficient relaxation with good approximation guarantees
Future work:• Low-rank guarantees of solution from symmetry• How to generate intermediate Sum-of-Squares relaxations for otherhigh degree polynomial optimization problems?

16