Optimization Week 7: Convex programming and duality

Week 7: Convex programming and duality

• 1 Lagrangian and dual function
• 2 Weak duality
• 3 Strong duality
• 4 Complementary slackness
• 5 Duality and sensitivity

1 Lagrangian and dual function

• Primal

  min ⁡ x f 0 ( x ) s . t . f i ( x ) ≤ 0 , i = 1... m h j ( x ) = 0 , j = 1... n \begin{aligned} \min_x&\quad f_0(x)\\ s.t.&\quad f_i(x)\leq 0, i=1...m\\ &\quad h_j(x)=0,j=1...n \end{aligned} xmin​s.t.​f0​(x)fi​(x)≤0,i=1...mhj​(x)=0,j=1...n​ ⇔ \Leftrightarrow ⇔ min ⁡ x max ⁡ λ ≥ 0 , ν f 0 ( x ) + ∑ i λ i f i ( x ) + ∑ j ν j h j ( x ) \min_x \max_{\lambda\geq0, \nu} f_0(x)+\sum_i \lambda_i f_i(x) +\sum_j \nu_j h_j(x) minx​maxλ≥0,ν​f0​(x)+∑i​λi​fi​(x)+∑j​νj​hj​(x)

  Lagrangian is L ( x , λ , ν ) = f 0 ( x ) + ∑ i λ i f i ( x ) + ∑ j ν j h j ( x ) L(x,\lambda,\nu)=f_0(x)+\sum_i \lambda_i f_i(x) +\sum_j \nu_j h_j(x) L(x,λ,ν)=f0​(x)+∑i​λi​fi​(x)+∑j​νj​hj​(x)

• Dual

  min ⁡ x max ⁡ λ ≥ 0 , ν L ( x , λ , ν ) ≥ max ⁡ λ ≥ 0 , ν min ⁡ x L ( x , λ , ν ) \min_x \max_{\lambda\geq0, \nu}L(x,\lambda,\nu)\geq \max_{\lambda\geq0, \nu}\min_x L(x,\lambda,\nu) minx​maxλ≥0,ν​L(x,λ,ν)≥maxλ≥0,ν​minx​L(x,λ,ν)

  Dual function: g ( λ , ν ) = min ⁡ x L ( x , λ , ν ) g(\lambda,\nu)=\min_x L(x,\lambda,\nu) g(λ,ν)=minx​L(x,λ,ν)

  Dual function is always concave (pointwise minimum of linear functions)

2 Weak duality

Weak duality always holds:

min ⁡ x max ⁡ λ ≥ 0 , ν L ( x , λ , ν ) ≥ max ⁡ λ ≥ 0 , ν min ⁡ x L ( x , λ , ν ) \min_x \max_{\lambda\geq0, \nu}L(x,\lambda,\nu)\geq \max_{\lambda\geq0, \nu}\min_x L(x,\lambda,\nu) xmin​λ≥0,νmax​L(x,λ,ν)≥λ≥0,νmax​xmin​L(x,λ,ν)

3 Strong duality

min ⁡ x f 0 ( x ) s . t . f i ( x ) ≤ 0 , i = 1... m A x = 0 \begin{aligned} \min_x&\quad f_0(x)\\ s.t.&\quad f_i(x)\leq 0, i=1...m\\ &\quad Ax=0 \end{aligned} xmin​s.t.​f0​(x)fi​(x)≤0,i=1...mAx=0​ Convex opt problem +

satisfying slator’s condition

( ∃ \exist ∃ a strictly feasible point, or must exist an interior point)

⇔ \Leftrightarrow ⇔ Strong Duality.

4 Complementary slackness

If

• x ∗ x^* x∗ primal optimal
• λ ∗ , ν ∗ \lambda^*,\nu^* λ∗,ν∗ dual optimal
• Strong duality holds

Then λ i ∗ f i ( x ∗ ) = 0 , ∀ i \lambda_i^* f_i(x^*)=0,\forall i λi∗​fi​(x∗)=0,∀i

5 Duality and sensitivity

min ⁡ x f 0 ( x ) s . t . f i ( x ) ≤ u i , i = 1... m A x = b + v , j = 1... n \begin{aligned} \min_x&\quad f_0(x)\\ s.t.&\quad f_i(x)\leq u_i, i=1...m\\ &\quad Ax=b+v,j=1...n \end{aligned} xmin​s.t.​f0​(x)fi​(x)≤ui​,i=1...mAx=b+v,j=1...n​ min ⁡ x max ⁡ λ ≥ 0 , ν f 0 ( x ) + ∑ i λ i f i ( x ) + ∑ j ν j h j ( x ) \min_x \max_{\lambda\geq0, \nu} f_0(x)+\sum_i \lambda_i f_i(x) +\sum_j \nu_j h_j(x) minx​maxλ≥0,ν​f0​(x)+∑i​λi​fi​(x)+∑j​νj​hj​(x)

Assuming the optmal value of this primal is p ( u , v ) p(u,v) p(u,v). Then:

∂ p ( 0 , 0 ) ∂ u i = − λ i , λ i ≥ 0 ; ∂ p ( 0 , 0 ) ∂ v i = − u i \frac{\partial p(0,0)}{\partial u_i}=-\lambda_i, \lambda_i\geq 0 ; \frac{\partial p(0,0)}{\partial v_i} =-u_i ∂ui​∂p(0,0)​=−λi​,λi​≥0;∂vi​∂p(0,0)​=−ui​