拉格朗日对偶性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。