Lagrange dual problem
Lagrangian
\[\min{}f_0(x),s.t.f_i(x)\leq0,h_i(x)=0\] variable \(x\in{}R^n\), domain \(\mathcal{D}\), optimal value \(p^\star\) \[L:R^n\times{}R^m\times{}R^p\rightarrow{}R,dom~L=\mathcal{D}\times{}R^m\times{}R^p\] \[L(x,\lambda,\nu)=f_0(x)+\sum_{i=1}^m\lambda_if_i(x)+\sum_{i=1}^p\nu_ih_i(x)\]
Lagrange dual function
\[g:R^m\times{}R^p\rightarrow{}R\] \[g(\lambda,\nu)=\inf_{x\in{}D}L(x,\lambda,\nu)=\inf_{x\in{}D}(f_0(x)+\sum_{i=1}^m\lambda_if_i(x)+\sum_{i=1}^p\nu_ih_i(x))\] lower bound property: if \(\lambda\geq0\), then \(g(\lambda,\nu)\leq{}p^\star\)
Lagrange dual problem
\[\max{}g(\lambda,\nu),s.t.\lambda\succeq0\] optimal value \(d^\star\)
Weak and strong duality
- weak duality: \(d^\star\leq{}p^\star\)
- always holds (for convex and nonconvex problems)
- strong duality: \(d^\star=p^\star\)
- (usually) holds for convex problems
Slater's constraint qualification
\[\text{minimize }f_0(x)\] \[\text{subject to }f_i(x)\leq0,Ax=b\] strong duality holds if it is strictly feasible, i.e., \[\exists{}x\in{}\text{relint }D:~f_i(x)<0,Ax=b\]
- there exist many other types of constraint qualifications
Geometric interpretation
Omit
Complementary slackness
Assume strong duality holds, \(x^\star\) is primal optimal, \((\lambda^\star,\nu^\star)\) is dual optimal - \(x^\star\) minimizes \(L(x,\lambda^\star,\nu^\star)\) - \(\lambda_i^\star{}f_i(x^\star)=0\) for \(i=1,\dots,m\)
KKT conditions
- primal constraints: \(f_i(x)\leq0,i=1,\dots,m,h_i(x)=0,i=1,\dots,p\)
- dual constraints: \(\lambda\succeq0\)
- complementary slackness: \(\lambda_if_i(x)=0\)
- gradient of Lagrangian with respect to \(x\) vanishes: \[\nabla{}f_0(x)+\sum_{i=1}^m\lambda_i\nabla{}f_i(x)+\sum_{i=1}^p\nu_i\nabla{}h_i(x)=0\]
KKT conditions for convex problem
If \(\tilde{x},\tilde{\lambda},\tilde{\nu}\) satisfy KKT for a convex problem, then they are optimal. If Slater’s condition is satisfied, then \(x\) is optimal if and only if there exist \(\lambda, \nu\) that satisfy KKT conditions.
Perturbation and sensitivity analysis
\[f_i(x)\leq0\Rightarrow{}f_i(x)\leq{}u_i\] \[h_i(x)=0\Rightarrow{}h_i(x)=v_i\] \[g(\lambda,\nu)\Rightarrow{}g(\lambda,\nu)-u^T\lambda-v^T\nu\]
\[p^\star(u,v)\geq{}g(\lambda^\star,\nu^\star)-u^T\lambda^\star-v^T\nu^\star=p^\star(0,0)-\lambda^\star-\nu^\star\]
Local sensitivity
If \(p^\star(u,v)\) is differentiable at \((0,0)\), then \[\lambda_i^\star=-\frac{\partial{}p^\star(0,0)}{\partial{}u_i},\nu_i^\star=-\frac{\partial{}p^\star(0,0)}{\partial{}v_i}\]
Duality and problem reformulations
Introducing new variables and equality constraints
\[\text{minimize }f_0(Ax+b)\]
- dual function is constant
- we have strong duality, but dual is quite useless
\[\Rightarrow\text{minimize }f_0(y)\text{, subject to }Ax+b-y=0\]
Implicit constraints
\[\text{minimize }c^Tx\text{, subject to }Ax=b,-1\preceq{}x\preceq{}1\] \[\Rightarrow\text{minimize }f_0(x)=c^Tx(-1\preceq{}x\preceq{}1),\infty(\text{otherwise})\text{, subject to }Ax=b\]
Problems with generalized inequalities
\[\text{minimize }f_0(x)\text{, subject to }f_i(x)\preceq{}_{K_i}0,h_i(x)=0\]
Semidefinite program
\[\text{minimize }c^Tx,\text{, subject to }x_1F_1+\dots+x_nF_n\preceq{}G\]
- Lagrange multiplier is matrix \(Z\in{}S^k\)
- Lagranigian \[L(x,Z)=c^Tx+tr(Z(x_1F_1+\dots+x_nF_n-G))\]
- dual function \[g(Z)=\inf_xL(x,Z)=-tr(GZ)(\text{for }tr(F_iZ)+c_i=0),-\infty(\text{otherwise})\]
