Semidefinite Relaxations of Product of PSD
Forms
LIDS Student Conference 2021

Chenyang Yuan (joint work with Pablo Parrilo)
February 3, 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 K = R or C:
Opt(A) :=maxx∈K, kxk=1dY!1/dhx, Ai xi

i=12Introduction

Given A = (A1 , . . . , Ad ) where Ai  0, we study the following polynomial
optimization problem on K = R or C:
Opt(A) :=maxx∈K, 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 K = R or C:
Opt(A) :=maxx∈K, kxk=1

dY!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 K = R or C:
Opt(A) :=maxx∈K, kxk=1

dY!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 2qp
λ1λnmaxkxk=1 (x T Ax)(x T A−1 x) ≤ 41
λn +λ13

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 2qp
λ1λnmaxkxk=1 (x T Ax)(x T A−1 x) ≤ 41
λn +λ1Approximating 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 Motivation
Opt(A) := maxkxk=1

Qd

1/di=1 hx, Ai xi

Kantorovich’s inequality (A1 = Q, A2 = Q −1 ): Given Q  0,q 2qp
λ1
λnmaxkxk=1 (x T Ax)(x T A−1 x) ≤ 41
λn +λ1
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 MotivationOpt(A) := maxkxk=1Qd

1/di=1 hx, Ai xi

Kantorovich’s inequality (A1 = Q, A2 = Q −1 ): Given Q  0,q 2qp
λ1λnmaxkxk=1 (x T Ax)(x T A−1 x) ≤ 41
λn +λ1Approximating 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 =1
i=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):Approx: Ω( n1 )Compute: SDP with nO(d) vars/consts

4

Our Contributions
Using semidefinite programming (SDP) based approximation algorithms
for general polynomial optimization (Sum-of-Squares):Approx: Ω( n1 )Compute: SDP with nO(d) vars/consts
Our relaxation and approximation algorithm that exploits compact
representation:
Compute: SDP with n2 d vars/consts
Approx: Ω(1)4Our Contributions
Using semidefinite programming (SDP) based approximation algorithms
for general polynomial optimization (Sum-of-Squares):Approx: Ω( n1 )Compute: SDP with nO(d) vars/consts
Our relaxation and approximation algorithm that exploits compact
representation:
Compute: SDP with 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):Approx: Ω( n1 )Compute: SDP with nO(d) vars/consts
Our relaxation and approximation algorithm that exploits compact
representation:
Compute: SDP with 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 ContributionsUsing semidefinite programming (SDP) based approximation algorithms
for general polynomial optimization (Sum-of-Squares):Approx: Ω( n1 )Compute: SDP with nO(d) vars/consts
Our relaxation and approximation algorithm that exploits compact
representation:
Compute: SDP with 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

Qd

use AM-GM

rank-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 > 05

Semidefinite Relaxation
max

kxk=1

1/di=1 hx, Ai xi

Qd

use AM-GM

rank-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 > 0

Theorem
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

Qd

use AM-GM

rank-1 relaxmaxX

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  0

Theorem
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 = R
if K = C
5

Higher-order Relaxations
OptSDP constructed using AM/GM inequality. Ifd
Y
i=11/dhx, Ai xi

≤ xT

1dd
X

Qi αi = 1,!
αi Ai

xi=1

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

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

1/dhx, Ai xi≤ xT1ddX

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 ) =kYxiI ⊆[d],|I |=k i∈I

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

1/dhx, Ai xi

≤ xT

i=1

1ddX

Qi αi = 1,!
αi Aixi=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/d

1/d= Ed

1/(d−1)≤ Ed−1

1/2≤ · · · ≤ E2

≤ E1 =

y1 + · · · + ydd6

Higher-order Relaxations
OptSDP constructed using AM/GM inequality. Ifd
Y

1/dhx, Ai xi≤ xTi=11ddX

Qi αi = 1,!
αi Ai

xi=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

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

1/d= Ed

1/(d−1)≤ Ed−1

1/2≤ · · · ≤ E2

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

6

Example: Icosahedral formLet ψ 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)]7

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!

7

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
7

Distribution sampled from rounding algorithmk = 2, lower: 0.28197, upper: 1.59397

1.000.75/2)

0.50
0.25

sin(0.000.25
0.50
0.75
1.00

32

101238

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

1012

39

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

32

10

12

310

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

1.000.75/2)

0.50
0.25

sin(0.000.25
0.50
0.75
1.00

321012311

Distribution sampled from rounding algorithm

k = 6, lower: 0.79445, upper: 1.00000

1.000.75/2)

0.50
0.25

sin(0.00
0.25
0.50
0.75
1.00

32

1012312

Distribution sampled from rounding algorithm

Distribution concentrates towards optima as k increases
13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

14

Conclusion

Takeaways:• Product of PSD forms has nice structure and generalizes manyproblems• 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?

14