拉格朗日對偶性Duality and the Lagrangian

利用拉格朗日對偶性（Lagrange duality）将原始問題轉換為對偶問題，通過解對偶問題而得到原始問題的解。

原始問題

考慮原始問題：

假設 f ( x ) f(x) f(x)、 c i ( x ) c_i(x) ci​(x)、 h j ( x ) h_j(x) hj​(x)是定義在 R n \mathbf{R}^n Rn上的連續可微函數，考慮限制最優化問題

min ⁡ x ∈ R n f ( x ) s . t . c i ( x ) ≤ 0 , i = 1 , 2 , ⋯   , k h j ( x ) = 0 , j = 1 , 2 , ⋯   , l \begin{aligned}\min_{x\in \mathbf{R}^n}\quad &f(x)\\ s.t. \quad & c_i(x)\leq 0,\quad i=1,2,\cdots,k\\ & h_j(x)=0, \quad j=1,2,\cdots,l \end{aligned} x∈Rnmin​s.t.​f(x)ci​(x)≤0,i=1,2,⋯,khj​(x)=0,j=1,2,⋯,l​

首先，我們引入廣義拉格朗日函數(generalized Lagrange function)

L ( x , α , β ) = f ( x ) + ∑ i = 1 k α i c i ( x ) + ∑ j = 1 l β j h j ( x ) L(x,\alpha,\beta)=f(x)+\sum_{i=1}^k \alpha_ic_i(x)+\sum_{j=1}^l \beta_jh_j(x) L(x,α,β)=f(x)+i=1∑k​αi​ci​(x)+j=1∑l​βj​hj​(x)

其中 x = ( x ( 1 ) , x ( 2 ) , ⋯   , x ( n ) ) T ∈ R n x=(x^{(1)},x^{(2)},\cdots, x^{(n)})^T \in \mathbf{R}^n x=(x(1),x(2),⋯,x(n))T∈Rn， α i ≥ 0 , β j \alpha_i\geq 0,\beta_j αi​≥0,βj​是拉格朗日乘子。考慮 x x x的函數：

θ P ( x ) = max ⁡ α , β ; α i ≥ 0 L ( x , α , β ) \theta_P(x)=\max_{\alpha,\beta;\alpha_i\geq 0}L(x,\alpha,\beta) θP​(x)=α,β;αi​≥0max​L(x,α,β)

下标P表示原始問題。

假設給定某個 x x x，如果 x x x違反原始問題的限制條件，即存在某個 i i i使得 c i ( w ) > 0 c_i(w)>0 ci​(w)>0或者存在某個 j j j使得 h j ( w ) ≠ 0 h_j(w)\neq 0 hj​(w)​=0，則有

θ P ( x ) = max ⁡ α , β ; α i ≥ 0 [ f ( x ) + ∑ i = 1 k α i c i ( x ) + ∑ j = 1 l β j h j ( x ) ] = + ∞ \theta_P(x)=\max_{\alpha,\beta;\alpha_i\geq 0}\left[f(x)+\sum_{i=1}^k \alpha_ic_i(x)+\sum_{j=1}^l \beta_jh_j(x)\right]=+\infty θP​(x)=α,β;αi​≥0max​[f(x)+i=1∑k​αi​ci​(x)+j=1∑l​βj​hj​(x)]=+∞

因為某個 i i i使得限制 c i ( x ) > 0 c_i(x)>0 ci​(x)>0，故我令 α i → + ∞ \alpha_i\rightarrow +\infty αi​→+∞，則可得到上式；同理，若某個 j j j使得限制 h j ( x ) ≠ 0 h_j(x)\neq 0 hj​(x)​=0，則令 β j h j ( x ) → + ∞ \beta_jh_j(x)\rightarrow +\infty βj​hj​(x)→+∞，也可得到上式。

相反地，如果限制條件均滿足，則 θ P ( x ) = f ( x ) \theta_P(x)=f(x) θP​(x)=f(x)，是以

θ P ( x ) = { f ( x ) , x 滿 足 原 始 問 題 約 束 + ∞ , 其 他 \theta_P(x)=\begin{cases}f(x ), & x 滿足原始問題限制\\+\infty, & 其他\end{cases} θP​(x)={f(x),+∞,​x滿足原始問題限制其他​

是以考慮極小化問題

min ⁡ x θ P ( x ) = min ⁡ x max ⁡ α , β ; α i ≥ 0 L ( x , α , β ) \min_x \theta_P(x)=\min_x\max_{\alpha,\beta; \alpha_i\geq 0}L(x,\alpha,\beta) xmin​θP​(x)=xmin​α,β;αi​≥0max​L(x,α,β)

它與原始問題是等價的，即具有相同的解，我們把問題 min ⁡ x max ⁡ α , β ; α i ≥ 0 L ( x , α , β ) \min\limits_x\max\limits_{\alpha,\beta; \alpha_i\geq 0}L(x,\alpha,\beta) xmin​α,β;αi​≥0max​L(x,α,β)稱為廣義拉格朗日函數的極小極大問題，這樣以來就将原始問題轉化為廣義拉格朗日函數的極小極大問題。

對偶問題

定義

θ D ( α , β ) = min ⁡ x L ( x , α , β ) \theta_D(\alpha,\beta)=\min_x L(x,\alpha,\beta) θD​(α,β)=xmin​L(x,α,β)

再考慮極大化 θ D ( α , β ) \theta_D(\alpha,\beta) θD​(α,β)

max ⁡ α , β ; α i ≥ 0 θ D ( α , β ) = max ⁡ α , β ; α i ≥ 0 min ⁡ x L ( x , α , β ) \max_{\alpha,\beta;\alpha_i\geq0}\theta_D(\alpha,\beta)=\max_{\alpha,\beta;\alpha_i\geq0}\min_x L(x,\alpha,\beta) α,β;αi​≥0max​θD​(α,β)=α,β;αi​≥0max​xmin​L(x,α,β)

該問題稱為廣義拉格朗日問題的極大極小問題。

可以将廣義拉格朗日的極大極小問題表示為限制最優化問題：

max ⁡ α , β θ D ( α , β ) = max ⁡ α , β min ⁡ x L ( x , α , β ) s . t . α i ≥ 0 , i = 1 , 2 , ⋯   , k \begin{aligned}\max_{\alpha,\beta}\theta_D(\alpha,\beta)=&\max_{\alpha,\beta}\min_x L(x,\alpha,\beta)\\ s.t. \quad &\alpha_i\geq 0,i=1,2,\cdots, k\end{aligned} α,βmax​θD​(α,β)=s.t.​α,βmax​xmin​L(x,α,β)αi​≥0,i=1,2,⋯,k​

稱為原始問題的對偶問題。

原始問題與對偶問題的關系

Theorem1. 若原始問題和對偶問題都有最優值，則

d ∗ = max ⁡ α , β ; α i ≥ 0 min ⁡ x L ( x , α , β ) ≤ min ⁡ x max ⁡ α , β ; α i ≥ 0 L ( x , α , β ) = p ∗ d^*=\max_{\alpha,\beta;\alpha_i\geq0}\min_x L(x,\alpha,\beta)\leq \min_x\max_{\alpha,\beta;\alpha_i\geq 0} L(x,\alpha,\beta)=p^* d∗=α,β;αi​≥0max​xmin​L(x,α,β)≤xmin​α,β;αi​≥0max​L(x,α,β)=p∗

Proof.

θ D ( α , β ) = min ⁡ x L ( x , α , β ) ≤ L ( x , α , β ) ≤ max ⁡ α , β ; α i ≥ 0 L ( x , α , β ) = θ P ( x ) \theta_D (\alpha,\beta)=\min_x L(x,\alpha,\beta)\leq L(x,\alpha,\beta)\leq \max_{\alpha,\beta;\alpha_i\geq 0} L(x,\alpha,\beta)=\theta_P(x) θD​(α,β)=xmin​L(x,α,β)≤L(x,α,β)≤α,β;αi​≥0max​L(x,α,β)=θP​(x)

則

θ D ( α , β ) ≤ θ P ( x ) \theta_D(\alpha,\beta)\leq \theta_P(x) θD​(α,β)≤θP​(x)

由于原始問題和對偶問題均有最優值，則

max ⁡ α , β ; α i ≥ 0 θ D ( α , β ) ≤ min ⁡ x θ P ( x ) \max_{\alpha,\beta;\alpha_i\geq 0} \theta_D(\alpha,\beta)\leq \min_x \theta_P(x) α,β;αi​≥0max​θD​(α,β)≤xmin​θP​(x)

故 d ∗ ≤ p ∗ d^*\leq p^* d∗≤p∗

換句話說，對偶問題的最優值小于等于原問題的最優值。

Corollary 1. 設 x ∗ x^* x∗ 和 α ∗ \alpha^* α∗ ， β ∗ \beta^* β∗分别表示原始問題和對偶問題的可行解，并且 d ∗ = p ∗ d^*=p^* d∗=p∗，則 x ∗ x^* x∗ 和 α ∗ \alpha^* α∗ ， β ∗ \beta^* β∗分别是原始問題和對偶問題的最優解。

在這種條件下，原始問題和對偶問題的最優值相等，這時可以用解對偶問題代替解原始問題。

Theorem 2. 考慮原始問題和對偶問題。假設函數 f ( x ) f(x) f(x) 和 c i ( x ) c_i(x) ci​(x)是凸函數， h j ( x ) h_j(x) hj​(x)是仿射函數；假設不等式限制 c i ( x ) c_i(x) ci​(x) 是嚴格可行的，即存在 x x x，對所有的 i i i有 c i ( x ) < 0 c_i(x)<0 ci​(x)<0，則存在 x ∗ , α ∗ , β ∗ x^*,\alpha^*,\beta^* x∗,α∗,β∗，使得 x ∗ x^* x∗是原始問題的解， α ∗ , β ∗ \alpha^*,\beta^* α∗,β∗是對偶問題的解，并且

p ∗ = d ∗ = L ( x ∗ , α ∗ , β ∗ ) p^*=d^*=L(x^*,\alpha^*,\beta^*) p∗=d∗=L(x∗,α∗,β∗)

Theorem 3. 對原始問題和對偶問題，假設函數 f ( x ) f(x) f(x) 和 c i ( x ) c_i(x) ci​(x)是凸函數， h j ( x ) h_j(x) hj​(x)是仿射函數，并且不等式限制 c i ( x ) c_i(x) ci​(x) 是嚴格可行的，則 x ∗ x^* x∗和 α ∗ , β ∗ \alpha^*,\beta^* α∗,β∗分别是原始問題和對偶問題的解的充分必要條件是 x ∗ , α ∗ , β ∗ x^*,\alpha^*,\beta^* x∗,α∗,β∗滿足Karush-kuhn-Tucker(KKT)條件：

∇ x L ( x ∗ , α ∗ , β ∗ ) = 0 ∇ α L ( x ∗ , α ∗ , β ∗ ) = 0 ∇ β L ( x ∗ , α ∗ , β ∗ ) = 0 α i ∗ c i ( x ∗ ) = 0 , i = 1 , 2 , ⋯   , k c i ( x ∗ ) ≤ 0 , i = 1 , 2 , ⋯   , k α i ∗ ≥ 0 , i = 1 , 2 , ⋯   , k h i ( x ∗ ) = 0 \begin{aligned}\nabla_x L(x^*,\alpha^*,\beta^*)=0\\ \nabla_\alpha L(x^*,\alpha^*,\beta^*)=0\\ \nabla_\beta L(x^*,\alpha^*,\beta^*)=0\\ \alpha^*_ic_i(x^*)=0, i=1,2,\cdots, k\\ c_i(x^*)\leq 0, i=1,2,\cdots, k\\ \alpha_i^*\geq 0,i=1,2,\cdots,k\\ h_i(x^*)=0 \end{aligned} ∇x​L(x∗,α∗,β∗)=0∇α​L(x∗,α∗,β∗)=0∇β​L(x∗,α∗,β∗)=0αi∗​ci​(x∗)=0,i=1,2,⋯,kci​(x∗)≤0,i=1,2,⋯,kαi∗​≥0,i=1,2,⋯,khi​(x∗)=0​

特别指出， α i ∗ c i ( x ∗ ) = 0 \alpha^*_ic_i(x^*)=0 αi∗​ci​(x∗)=0稱為KKT的對偶互補條件，此條件可知: 若 α ∗ > 0 \alpha^*>0 α∗>0，則 c i ( x ∗ ) = 0 c_i(x^*)=0 ci​(x∗)=0。