Linear Programming
\[\text{(P) }\min_xc^Tx,s.t.Ax=b,x\geq0\] \[\text{(D) }\min_yb^Ty,s.t.A^Ty+s=c,s\geq0\]
Strong duality
\[c^Tx=b^T\Leftrightarrow{}x^Ts=0\Leftrightarrow{}x_is_i=0\]
KKT system in LP
- Primal feasibility
\[Ax=b\land{}x\geq0\]
- Dual feasibility
\[A^Ty+s=c\land{}s\geq0\]
- Complementarity
\[x_is_i=0\]
Algebraic Characterization
- Define \(x\circ{}s=(x_1s_1,\dots,x_ns_n)^\top\) and
\[L_x:y\mapsto(x_1y_1,\dots,x_ny_n)^\top,\text{ i.e. }L_x={\rm Diag}(x)\]
Semidefinite programming (SDP)
\[\text{(P) }\min\langle{}C_1,X_1\rangle{}+\dots+\langle{}C_n,X_n\rangle{}\] \[s.t.~\langle{}A_{i1},X_1\rangle{}+\dots+\langle{}A_{in},X_n\rangle{}=b_i,X_i\succeq0\] \[\text{(D) }\max{}b^\top{}y\] \[s.t.~A_{1i}b_1+\dots+A_{ni}b_n+S_i=C_i,S_i\succeq0\]
Strong duality
\[\langle{}X,S\rangle{}=0\Leftrightarrow{}X\succeq0\land{}S\succeq0\land\frac{XS+SX}{2}=0\]
Second order cone programming (SOCP)
\[\text{(P) }\min{}c^\top{}x,s.t.Ax=b,x\succeq_{\mathcal{Q}}0\] \[\text{(Q) }\min{}b^\top{}y,s.t.A^\top{}y+s=c,s\succeq_{\mathcal{Q}}0\]
Example
\[x\in{}S,\lambda_1\geq\lambda_2\geq\dots\geq\lambda_n\] \[(\lambda_1+\dots+\lambda_K)(X)\] \[\Leftrightarrow\] \[\min_{Y,t}Tr(Y)+Kt,~s.t.tI+Y\succeq{}X,Y\succeq0\]
SDP Relaxation
Consider QCQP \[\min~x^TA_0x+2b_0^Tx+c_0\text{ assume }A_i\in{}S^n\] \[\text{s.t. }x^TA_ix+2b_i^Tx+c_i\leq0,i=1,\dots,m\]
Max Cut
For graph \((V,E)\) and weights
\(w_{ij}=w_{ji}\geq0\), the maxcut
problem is: \[(Q)~\max_x\frac{1}{2}\sum_{i<j}w_{ij}(1-x_ix_j),~\text{
s.t. }x_i\in\{-1,1\}\] where \(x_i=-1\) means \(x\) in set \(X_1\) and \(x_i=1\) means \(x\) in set \(X_2\). And its relaxation is: \[(P)~\max_{v_i\in{}R^n}\frac{1}{2}\sum_{i<j}w_{ij}(1-v_iv_j),~\text{
s.t. }||v_i||_2=1\] The equivalent SDP of \((P)\) is : \[(SDP)~\max_{X\in{}S^n}\frac{1}{2}\sum_{i<j}w_{ij}(1-X_{ij}),~\text{
s.t. }X_{ii}=1,X\succeq0\] where \(X=V^TV=(v_1,\dots,v_n)^T(v_1,\dots,v_n)\).
Add \(rank(X)=1\), then \(X=xx^T\Rightarrow{}x_i^2=1\), which means
that it is equivalent to the original problem.
Greedy Way
Every time we pick most distant one, then \[Z^*\geq\frac{1}{2}Z_{opt}\]
Rounding Procedure
- Generate a vector \(r\) uniformly distributed on the unit sphere, i.e. \(||r||_2=1\)
- Set \(x_i=1(v_i^Tr\geq0),-1(\text{otherwise})\)
Theoretical Result
- Let \(W\) be the objective function value of \(x\) and \(E(W)\) be the expected value. Then
\[E(W)=\frac{1}{\pi}\sum_{i<j}w_{ij}\arccos(v_i^Tv_j)\]
- Goemans and Williamson showed:
\[E(W)\geq\alpha\frac{1}{2}\sum_{i<j}w_{ij}(1-v_i^Tv_j),\alpha=\min_{0\leq\theta\leq\pi}\frac{2}{\pi}\frac{\theta}{1-\cos\theta}>0.878\]
SDP Representablity
A set \(X\subseteq{}R^n\) is SDP-representable (or SDP-Rep for short) if it can be expressed linearly as the feasible region of an SDP: \[X=\{x|(\exists{}u\in{}R^k)(\exists{}A_i,B_j,C\in{}R^{m\times{}m})\sum_ix_iA_i+\sum_ju_jB_j+C\succeq0\}\] A function \(f(x)\) is SDP-Rep if its epigraph is SDP-representable: \[\text{epi}(f)=\{(x_0,x)|f(x)\leq{}x_0\}\]
- If \(X\) is SDP-Rep, then \(\min_{x\in{}X}c^Tx\) is an SDP
- If \(f(x)\) is SDP-Rep, then \(\min_xf(x)\) is an SDP
'Calculus' of SDP-Rep Sets
If \(X\) and \(Y\) are SDP-Rep then so are
- Minkowski sum \(X+Y\)
- Intersection \(X\cap{}Y\)
- Affine pre-image \(A^{-1}(X)\) if \(A\) is affine
- Affine map \(A(X)\) if \(A\) is affine
- Cartesian Product \(X\times{}Y=\{(x,y)|x\in{}X,y\in{}Y\}\)
Proof of Affine map
\[Y=\{Fx+f|F\in{}R^{m\times{}n},x\in{}X\}\] \[m\geq{}n,rank(F)=n\] \[y=Fx+f\Rightarrow{}x=(F^TF)^{-1}F^T(y-f)=F^+(y-f)\] \[A(F^+(y-f))+B(u)+C\geq0\Rightarrow{}A(F^+y)+B(u)+C-A(F^+f)\geq0\]
\[m\leq{}n,rank(F)=m\] \[y=Fx\Rightarrow{}y=[F_1,F_2][x_1,x_2]^T\Rightarrow{}x_1=F^{-1}(y-F_2x_2)\]
'Calculus' of SDP-Rep Functions
If functions \(f_i,i=1,\dots,m\) and \(g\) are SDP-Rep. Then the following are SDP-Rep:
- nonnegative sum \(\sum\alpha_if_i\) for \(\alpha_i\geq0\)
- maximum \(\max_if_i\)
- composition \(g(f_1(x),\dots,f_m(x))\)
- Legendre transform \(f^*(y)=\max_xy^Tx-f(x)\)
Positive Polynomials
The set of nonnegative polynomials of a given degree forms a proper cone \[P_n=\{(p_0,\dots,p_n)|(\forall{}t\in{}I)p_o+p_1t+\dots+p_nt^n>0\}\]
- The cone of positive polynomials is SDP-Rep
