Conic Optimization, SDP, and Interior-Point¶

Job: develop the conic optimization (LP/SOCP/SDP), the SDP (Schur, Lovász theta, Goemans–Williamson), the interior-point (Nesterov–Nemirovski, self-concordant), and the strong duality / complementarity — with the Lovász theta / Goemans–Williamson MAX-CUT as the worked example.

Core¶

The conic optimization¶

The $\min\langle c,x\rangle$ s.t. $Ax=b, x\in K$ (the cone $K$).

Conic / LP / SOCP / SDP	Description
Conic	$\min\langle c,x\rangle$ s.t. $Ax=b, x\in K$ (the cone $K$)
LP	$K=\mathbb{R}^n_+$ (the polyhedral, the simplex)
SOCP	$K=\{x:\\|x_{2:n}\\|\le x_1\}$ (the Lorentz cone)
SDP	$K=S^n_+$ (the PSD cone, $X\succeq0$)

The SDP and the Schur / the Lovász theta¶

SDP / Schur / Lovász / Goemans–Williamson	Description
SDP	$\min\langle C,X\rangle$ s.t. $X\succeq0, \mathcal{A}(X)=b$ (the PSD, the Schur complement)
Lovász $\vartheta(G)$	$\max\langle J,X\rangle$ s.t. $X\succeq0, X_{ij}=0\,\forall ij\in E, \mathrm{Tr}X=1$ (the $\alpha\le\vartheta\le\chi(\bar G)$)
Goemans–Williamson	MAX-CUT the SDP relaxation + hyperplane rounding the 0.878 approximation (the discrete math)

The interior-point (Nesterov–Nemirovski)¶

Interior-point / self-concordant / path-following	Description
Self-concordant barrier	$
Path-following	the central path $x(t)=\arg\min tc+J_K\nabla F$, the $t\uparrow$ (the Newton)
Polynomial complexity	$O(\sqrt{\nu}\log(1/\varepsilon))$ (the $\nu$ the barrier parameter, the NN)

The strong duality and the complementarity¶

Strong duality / Slater / complementarity	Description
Strong duality	the Slater $K^\circ\ne\emptyset$ $\Rightarrow$ the $p^=d^$ (the conic)
Complementarity	$X S=0$ (the $X,S\succeq0$ the PSD the complementarity, the conic KKT)

See it¶

Lovász $\vartheta(G)$ via SDP and the Goemans–Williamson MAX-CUT. The Lovász: $\vartheta(G)=\max\langle J,X\rangle$ s.t. $X\succeq0, X_{ij}=0\,\forall ij\in E, \mathrm{Tr}X=1$ (the SDP, the $\vartheta$ the upper bound $\alpha(G)\le\vartheta(G)\le\chi(\bar G)$). The Goemans–Williamson: MAX-CUT $\max\sum w_{ij}\frac{1-x_ix_j}{2}$ the SDP relaxation ($x_i\in S^{n-1}$ the unit, the hyperplane rounding), the 0.878 the approximation (the GW, the discrete math). The key point: the SDP the Lovász theta / the Goemans–Williamson MAX-CUT — the conic optimization the combinatorial.

Check¶

Show that the SDP relaxation of MAX-CUT gives the 0.878 Goemans–Williamson approximation.

The MAX-CUT: $\max\sum_{ij}w_{ij}\frac{1-x_ix_j}{2}$ with $x_i\in\{-1,+1\}$. The SDP relaxation: $x_i\in S^{n-1}$ (the unit vectors, $X\succeq0$ the Gram), the $\max\sum w_{ij}\frac{1-\langle x_i,x_j\rangle}{2}$. The rounding: the random hyperplane $r$, the $x_i$ assigned by $\mathrm{sign}(\langle r,x_i\rangle)$, the $\mathbb{E}[\frac{1-x_ix_j}{2}]=\frac{\arccos\langle x_i,x_j\rangle}{\pi}\ge0.878\frac{1-\langle x_i,x_j\rangle}{2}$ (the GW). So the SDP the 0.878.

Explain the self-concordant barrier and the $O(\sqrt{\nu}\log(1/\varepsilon))$ complexity.

The self-concordant: $|\nabla^3 F[h,h,h]|\le 2\|\nabla^2 F[h,h]\|^{3/2}$ (the barrier $F$, the Nesterov–Nemirovski). The central path: $x(t)=\arg\min tc+\nabla F_K$ (the $t\uparrow$, the Newton the step). The $O(\sqrt{\nu}\log(1/\varepsilon)$: the $\nu$ the barrier parameter ($\nu=n$ for the LP, $\nu=n$ for the SDP), the $\sqrt{\nu}$ the iterations, the $\log(1/\varepsilon)$ the accuracy. The NN: the self-concordant the polynomial, the interior-point the efficient.

Pitfalls¶

The SDP the PSD (the $X\succeq0$, the Schur, the linear algebra) — the SDP the PSD, the LP the polyhedral.
The Lovász $\vartheta$ the sandwich ($\alpha\le\vartheta\le\chi(\bar G)$) — the $\vartheta$ the upper / the lower, the Lovász.
The Goemans–Williamson 0.878 (the SDP the relaxation, the hyperplane the rounding) — the 0.878 the approximation, the MAX-CUT.
The self-concordant the NN (the barrier, the $O(\sqrt{\nu}\log(1/\varepsilon)$) — the self-concordant the polynomial, the interior-point.
The strong duality the Slater ($K^\circ\ne\emptyset$) — the Slater the strong, the conic the KKT.

Refs¶

Nesterov–Nemirovski, Interior-Point Polynomial Algorithms in Convex Programming (1994)
Lovász, "On the Shannon capacity of a graph" (IEEE 1979); Goemans–Williamson, "Improved approximation algorithms for MAX-CUT" (1995)
Vandenberghe–Boyd, "Semidefinite programming" (SIAM Review 1996); Wolkowicz et al., Handbook of SDP

Next¶

Opt index · Foundations · Nonconvex & Landscape · Variational & Monotone · Online & Stochastic · Discrete math · Linear algebra