A Wishlist for Optimization Algorithms

• Nonlinear, non-convex objectives
• Powerful enough to tackle hard problems in a systematic way, and meanwhile is still practical
• Becoming more accurate as we’re paying more
• A generic framework that can be applied obviously to various problems.
• Methods
  • sum-of-squares (SoS) SDP
  • Lasserre hierarchy
  • Lovász-Schrijver hierarchy

Quadratic programming

$$min\frac{1}{2}{x}^{T}Qx+c^{T}x$$

Semidefinite Program

• $A\succcurlyeq 0$: symmetric matrix $A\in {\mathbb{R}}^{n\times n}$ is positive semidefinite ($\mathrm{\forall }x\in {\mathbb{R}}^n,x^{T}Ax\ge 0$)
• $A\succcurlyeq 0⟺\mathrm{\forall }\lambda (A)\ge 0⟺\mathrm{\exists }B\in {\mathbb{R}}^{n\times n},A=B^{T}B$
• Semidefinite Programing(SDP): $C,A_1,\cdots ,A_k\in {\mathbb{R}}^{n\times n},b_1,b_2,\cdots ,b_k\in \mathbb{R}$

$$\begin{array}{rl}max& \text{tr}(C^{T}Y)=\sum _{i=1}^n\sum _{i=1}^n{c}_{ij}{y}_{ij}\\ \text{s.t. }& \text{tr}(A_r^{T}Y)\le b_r& \mathrm{\forall }1\le r\le k\\ & Y\succcurlyeq 0\\ & Y=Y^T\in {\mathbb{R}}^{n\times n}\end{array}$$

• SDP (vector program form, LP for inner products)

$$\begin{array}{rl}max& \sum _{i=1}^n\sum _{i=1}^n{c}_{ij}⟨v_i,v_j⟩\\ \text{s.t.}& \sum _{i=1}^n\sum _{j=1}^n{a}_{ij}^{(r)}⟨v_i,v_j⟩\le b_r& \mathrm{\forall }1\le r\le k\\ & v_1,\cdots ,v_n\in {\mathbb{R}}^n\end{array}$$

• LP $\subset$ SDP $\subset$ convex programs
• ellipsoid method: find $\text{OPT}\pm ϵ$ in time $\text{poly}(n,\frac{1}{ϵ})$
• SDP-Relaxation
  • Present the original quadratic program
  • SDP relaxation: $x_u{x}_v\to ⟨{\mathbf{x}}_v,{\mathbf{x}}_u⟩$
  • Solve SDP relaxtion
  • Round optimal solution $x_v^{\ast }$ to ${\hat{x}}_v$

Max-Cut

• Some Algorithm
  • Greedy: $\frac{1}{2}$-approximate
  • Random: $\frac{1}{2}$-approximate
  • Local Search: $\frac{1}{2}$-approximate
• LP for Max-Cut

$$\begin{array}{rl}max& \sum _{uv\in E}{y}_{uv}\\ \text{s.t. }& y_{uv}\le |x_u-x_v|& \mathrm{\forall }uv\in E\\ & x_v\in 0,1& \mathrm{\forall }v\in V\end{array}$$

• Linearization: Integrality gap $>2$

$$\begin{array}{rl}max& \sum _{uv\in E}{y}_{uv}\\ \text{s.t. }& y_{uv}\le y_{uw}+y_{wv}& \mathrm{\forall }u,v,w\in V\\ & y_{uv}+y_{uw}+y_{wv}\le 2& \mathrm{\forall }u,v,w\in V\\ & y_{uv}\in 0,1,\mathrm{\forall }u,v\in V\end{array}$$

• Quadratic Program

$$\begin{array}{rl}max& \sum _{uv\in E}{y}_{uv}\\ \text{s.t. }& y_{uv}\le \frac{1}{2}(1-x_u{x}_v)& \mathrm{\forall }uv\in E\\ & x_v\in -1,1& \mathrm{\forall }v\in V\end{array}$$

• Strictly Quadratic Program (nonlinear,non-convex)

$$\begin{array}{rl}max& \sum _{uv\in E}\frac{1}{2}(1-x_u{x}_v)\\ \text{s.t. }& x_v^2=1& \mathrm{\forall }v\in V\end{array}$$

• Relax to vector program

$$\begin{array}{rl}max& \sum _{uv\in E}\frac{1}{2}(1-⟨x_u,x_v⟩)\\ \text{s.t. }& |x_v{|}^2=1& \mathrm{\forall }v\in V\\ & x_v\in {\mathbb{R}}^{|V|}\end{array}$$

• Rounding: ${\hat{x}}_v=\text{sgn}(⟨x_v^{\ast },u⟩),u\in {\mathbb{R}}^n,|u{|}_2=1$ is uniform random unit vector
  • Generate $u$: $u=\frac{r}{|r{|}_2},r=(r_1,\cdots ,r_n)\in {\mathbb{R}}^n,r_i\sim N(0,1)$ i.i.d
  • $E(\text{cut})=\sum_{uv\in E}{\frac{\theta_{uv}}{\pi}}=\sum_{uv\in E}\frac{\arccos\langle x_u^,x_v^\rangle}{\pi}\geq\alpha\sum_{uv\in E}\frac{1}{2}(1-\langle x_u^,x_v^\rangle),\geq\alpha\text{OPT}_{\text{IP}}\geq\alpha\text{OPT}$
  • Assuming the unique games conjecture: no poly-time algorithm with approx. ratio $<\alpha =\underset{x\in [-1,1]}{inf}\frac{2\arccos (x)}{\pi (1-x)}=0.87856\cdots$

SoS

• Given a $n$-variate polynomial $f$, determine whether $f(x)\ge 0$ for all $x\in {0,1}^n$
  • NP-hard
• multilinear: $f(x)=\sum _{d=(d_1,\cdots ,d_n)\in {0,1}^n}{x}_1^{d_1}\cdots x_n^{d_n}$
• Given a $n$-variate polynomial $f$, find
  • either an $x\in {0,1}^n$ such that $f(x)<0$
  • or a “proof” of $f(x)\ge 0$ over all $x\in {0,1}^n$
    • SoS proof: $f(x)=\sum _{i=1}^r{g}_1(x{)}^2$
    • For nonnegatvie polynomial
      • $f:{0,1}^n\to \mathbb{R}$, degree-$2n$ SoS proof always exists
      • degree-$d$ SoS proof needs at most $r=n^{O(d)}$ length
      • if $f$ has degree=$d$ SoS proff, then it can be found in $n^{O(d)}$ time (by SDP)