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^TQx+c^Tx$$

Semidefinite Program

• $A≽0$: symmetric matrix $A\in\mathbb{R}^{n\times n}$ is positive semidefinite ($\forall x\in\mathbb{R}^n,x^TAx\geq0$)
• $A≽0\iff\forall\lambda(A)\geq 0\iff\exists B\in\mathbb{R}^{n\times n},A=B^TB$
• 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{aligned} \max\ & \text{tr}(C^TY)=\sum_{i=1}^n\sum_{i=1}^nc_{ij}y_{ij}\newline \text{s.t. } & \text{tr}(A^T_rY)\leq b_r & \forall 1\leq r\leq k\newline &Y≽0\newline &Y=Y^T\in\mathbb{R}^{n\times n} \end{aligned} $$

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

$$ \begin{aligned} \max & \sum_{i=1}^n\sum_{i=1}^nc_{ij}\langle v_i,v_j\rangle\newline \text{s.t.} & \sum_{i=1}^n\sum_{j=1}^na_{ij}^{(r)}\langle v_i,v_j\rangle\leq b_r & \forall 1\leq r\leq k\newline &v_1,\cdots,v_n\in\mathbb{R}^n \end{aligned} $$

• LP $\subset$ SDP $\subset$ convex programs
• ellipsoid method: find $\text{OPT}\pm\epsilon$ in time $\text{poly}(n,\frac{1}{\epsilon})$
• SDP-Relaxation
  • Present the original quadratic program
  • SDP relaxation: $x_ux_v\rightarrow\langle \mathbf{x}_v,\mathbf{x}_u\rangle$
  • Solve SDP relaxtion
  • Round optimal solution $x^*_v$ 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{aligned} \max & \sum_{uv\in E}y_{uv}\newline \text{s.t. } & y_{uv}\leq |x_u-x_v| &\forall uv\in E\newline & x_v\in{0,1} & \forall v\in V \end{aligned} $$

• Linearization: Integrality gap $>2$

$$ \begin{aligned} \max & \sum_{uv\in E}y_{uv}\newline \text{s.t. } & y_{uv}\leq y_{uw}+y_{wv} &\forall u,v,w\in V\newline & y_{uv}+y_{uw}+y_{wv}\leq 2 &\forall u,v,w\in V\newline & y_{uv}\in{0,1},\forall u,v\in V \end{aligned} $$

• Quadratic Program

$$ \begin{aligned} \max & \sum_{uv\in E}y_{uv}\newline \text{s.t. } & y_{uv}\leq \frac{1}{2}(1-x_ux_v) &\forall uv\in E\newline & x_v\in{-1,1} &\forall v\in V \end{aligned} $$

• Strictly Quadratic Program (nonlinear,non-convex)

$$ \begin{aligned} \max & \sum_{uv\in E}\frac{1}{2}(1-x_ux_v)\newline \text{s.t. } & x_v^2=1 &\forall v\in V \end{aligned} $$

• Relax to vector program

$$ \begin{aligned} \max & \sum_{uv\in E}\frac{1}{2}(1-\langle x_u,x_v\rangle)\newline \text{s.t. } & |x_v|^2=1 &\forall v\in V\newline & x_v\in\mathbb{R}^{|V|} \end{aligned} $$

• Rounding: $\hat x_v=\text{sgn}(\langle x_v^*,u\rangle),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=\inf_{x\in[-1,1]}\frac{2\arccos(x)}{\pi(1-x)}=0.87856\cdots$

SoS

• Given a $n$-variate polynomial $f$, determine whether $f(x)\geq 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)\geq 0$ over all $x\in{0,1}^n$
    • SoS proof: $f(x)=\sum_{i=1}^rg_1(x)^2$
    • For nonnegatvie polynomial
      • $f:{0,1}^n\rightarrow\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)