Prime Promblem and Dual Problem
recommend textbook:
Convex Optimization Stepthen Boyd
Nonlinear Programming
Prime Problem
{ m i n i m i z e f ( ω ) s . t . { g i ( ω ) ≤ 0 ( i = 1 ∼ K ) h i ( ω ) = 0 ( i = 1 ∼ N ) \left\{\begin{array}{l} minimize\ f(\boldsymbol\omega)\\ s.t.\left\{\begin{array}{l} g_i(\boldsymbol\omega)\leq0(i=1\sim K)\\ h_i(\boldsymbol\omega) = 0 (i=1\sim N) \end{array}\right. \end{array}\right.⎩⎨⎧minimize f(ω)s.t.{gi(ω)≤0(i=1∼K)hi(ω)=0(i=1∼N)
Dual Problem
{ Θ ( α , β ) = min a l l ω { L ( ω , α , β ) } s . t . α i ≥ 0 L ( ω , α , β ) = f ( ω ) + ∑ i = 1 K α i g i ( ω ) + ∑ i = 1 M β i h i ( ω ) L ( ω , α , β ) = f ( ω ) + α T g ( ω ) + β T h ( ω ) ( v e c t o r i z e ) \left\{\begin{array}{l} \Theta(\boldsymbol\alpha, \boldsymbol\beta) = \min\limits_{all \ ω}\{L(\boldsymbol\omega, \boldsymbol\alpha, \boldsymbol\beta)\}\\ s.t. \ \boldsymbol\alpha_i \geq0 \end{array}\right.\\ L(\boldsymbol\omega,\boldsymbol\alpha, \boldsymbol\beta) = f(\boldsymbol\omega)+\sum\limits_{i=1}^{K}\boldsymbol\alpha_ig_i(\boldsymbol\omega)+\sum\limits_{i=1}^{M}\boldsymbol\beta_ih_i(\boldsymbol\omega)\\ L(\boldsymbol\omega,\boldsymbol\alpha, \boldsymbol\beta) = f(\boldsymbol\omega)+\boldsymbol\alpha^Tg(\boldsymbol\omega)+\boldsymbol\beta^Th(\boldsymbol\omega) \ (vectorize){Θ(α,β)=all ωmin{L(ω,α,β)}s.t. αi≥0L(ω,α,β)=f(ω)+i=1∑Kαigi(ω)+i=1∑Mβihi(ω)L(ω,α,β)=f(ω)+αTg(ω)+βTh(ω) (vectorize)
Theorme: if ω ∗ \boldsymbol\omega^*ω∗ is the solution of the prime problem and α ∗ , β ∗ \boldsymbol\alpha^*, \boldsymbol\beta^*α∗,β∗ is the solution of the dual problem. Then: f ( ω ∗ ) ≥ Θ ( α ∗ , β ∗ ) f(\boldsymbol\omega^*) \geq \Theta(\boldsymbol\alpha^*, \boldsymbol\beta^*)f(ω∗)≥Θ(α∗,β∗)
Prove:
∵ ω ∗ \boldsymbol\omega^*ω∗ satisfies prime problem and α ∗ , β ∗ \boldsymbol\alpha^*,\boldsymbol\beta^*α∗,β∗ satisfy dual problem
L ( ω ∗ , α ∗ , β ∗ ) = f ( ω ∗ ) + ∑ i = 1 K α i ∗ ≥ 0 g ( ω ∗ ) ≤ 0 + ∑ i = 1 N β i h ( ω ) = 0 L(\boldsymbol\omega^*,\boldsymbol\alpha^*, \boldsymbol\beta^*) = f(\boldsymbol\omega^*)+\sum\limits_{i=1}^K\mathop{\boldsymbol\alpha_i^*}\limits_{\geq0}\mathop{g(\boldsymbol\omega^*)}\limits_{\leq0} +\sum\limits_{i=1}^N\boldsymbol\beta_i\mathop{h(\boldsymbol\omega)}\limits_{=0}L(ω∗,α∗,β∗)=f(ω∗)+i=1∑K≥0αi∗≤0g(ω∗)+i=1∑Nβi=0h(ω)
∴ L ( ω ∗ , α ∗ , β ∗ ) ≤ f ( ω ∗ ) L(\boldsymbol\omega^*,\boldsymbol\alpha^*, \boldsymbol\beta^*) \leq f(\boldsymbol\omega^*)L(ω∗,α∗,β∗)≤f(ω∗)
it is easy to prove that:
Θ ( α ∗ , β ∗ ) ≤ L ( ω ∗ , α ∗ , β ∗ ) \Theta(\boldsymbol\alpha^*, \boldsymbol\beta^*)\leq L(\boldsymbol\omega^*,\boldsymbol\alpha^*, \boldsymbol\beta^*)Θ(α∗,β∗)≤L(ω∗,α∗,β∗)
∴ f ( ω ∗ ) ≥ Θ ( α ∗ , β ∗ ) f(\boldsymbol\omega^*) \geq \Theta(\boldsymbol\alpha^*, \boldsymbol\beta^*)f(ω∗)≥Θ(α∗,β∗)
Define the distance between prime problem and dual problem Duality Gap G = f ( ω ∗ ) − Θ ( α ∗ , β ∗ ) ≥ 0 G = f(\boldsymbol\omega^*) - \Theta(\boldsymbol\alpha^*, \boldsymbol\beta^*) \geq0G=f(ω∗)−Θ(α∗,β∗)≥0. In certain conditions, G = 0.
Strong Duality Therome(I won’t prove it here)
If f(ω) is a convex function and g ( ω ) = A ω + b , h ( ω ) = C ω + d g(\omega)=A\omega+b, h(\omega) = C\omega+dg(ω)=Aω+b,h(ω)=Cω+d, then G = 0.
Suppose we have already proved strong duality therome, then f ( ω ∗ ) = Θ ( α ∗ , β ∗ ) f(\boldsymbol\omega^*)=\Theta(\boldsymbol\alpha^*, \boldsymbol\beta^*)f(ω∗)=Θ(α∗,β∗):
①ω ∗ = ω , Θ ( α ∗ , β ∗ ) = L ( ω ∗ , α ∗ , β ∗ ) \omega^* = \omega,\ \Theta(\boldsymbol\alpha^*, \boldsymbol\beta^*)=L(\boldsymbol\omega^*,\boldsymbol\alpha^*, \boldsymbol\beta^*)ω∗=ω, Θ(α∗,β∗)=L(ω∗,α∗,β∗)
②∑ i = 1 K α i ∗ g i ( ω ∗ ) = 0 , ∀ i = 1 ∼ K , α i ∗ = 0 o r g i ∗ ( ω ∗ ) = 0 \sum\limits_{i=1}^{K}\alpha_i^*g_i(\omega^*) = 0, \ \forall i=1\sim K, \ \alpha_i^*=0 \ or \ g_i^*(\omega^*) = 0i=1∑Kαi∗gi(ω∗)=0, ∀i=1∼K, αi∗=0 or gi∗(ω∗)=0
② is very important, it is also called KKT condition