拉格朗日对偶问题

ゞ浴缸里的玫瑰 2022-11-17 03:22 174阅读 0赞

--------------------

> 在前文了解过拉格朗日乘数法后，进一步介绍拉格朗日对偶。

### 背景信息 ###

> 在约束最优化问题中，常常利用拉格朗日对偶性（Lagrange duality）将原始问题转换为对偶问题，通过解对偶问题而得到原始问题的解。

*  拉格朗日对偶是在[拉格朗日乘数法][Link 1]基础之上，通过变换原始问题的求解形式得到的相对于原始优化问题的另一个优化问题

#### 原始优化问题 ####

> 假设 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.  h i ( x ) ≤ 0 , i = 1 , 2 , … , k g j ( x ) = 0 , j = 1 , 2 , … , l (1) \\begin\{array\}\{c\} \\min \_\{x \\in \\mathbf\{R\}^\{n\}\} f(x) \\\\ \\text \{ s.t. \} \\quad h\_\{i\}(x) \\leq 0, i=1,2, \\ldots, k \\\\ g\_\{j\}(x)=0, j=1,2, \\ldots, l \\end\{array\}\\tag\{1\} minx∈Rnf(x) s.t. hi(x)≤0,i=1,2,…,kgj(x)=0,j=1,2,…,l(1)

*  定义此问题为原始优化问题

#### 广义拉格朗日函数 ####

> 来源见 ：[拉格朗日乘数法][Link 1]

L ( x , α , β ) = f ( x ) + ∑ i = 1 k α i h i ( x ) + ∑ j = 1 l β j g j ( x ) (2) L(x, \\alpha, \\beta)=f(x)+\\sum\_\{i=1\}^\{k\} \\alpha\_\{i\} h\_\{i\}(x)+\\sum\_\{j=1\}^\{l\} \\beta\_\{j\} g\_\{j\}(x)\\tag\{2\} L(x,α,β)=f(x)\+i=1∑kαihi(x)\+j=1∑lβjgj(x)(2)

*  其中  x = ( x 1 , x 2 , … , x n ) T ∈ R n , α i , β j x=\\left(x\_1, x\_2, \\ldots, x\_n\\right)^\{T\} \\in \\mathbf\{R\}^\{n\} , \\alpha\_\{i\}, \\beta\_\{j\} x=(x1,x2,…,xn)T∈Rn,αi,βj是拉格朗日乘子，且 α i ≥ 0 \\alpha\_\{i\} \\geq 0 αi≥0

### 拉格朗日对偶的来源 ###

> 考虑原始优化问题 1 1 1

*  想要求得 f ( x ) f(x) f(x)的最小值，也就是要求 f ( x ) f(x) f(x)的最大下界
 *  对于方程组：

f ( x ) < v h i ( x ) ≤ 0 , i = 1 , 2 , … , k (3) \\begin\{array\}\{l\} f(\\mathbf\{x\})<v \\\\\\\\ h\_\{i\}(\\mathbf\{x\}) \\leq 0, i=1,2, \\ldots, k \\end\{array\} \\tag\{3\} f(x)<vhi(x)≤0,i=1,2,…,k(3)

*  若方程组 3 3 3无解，则 v v v是 f ( x ) f(x) f(x)的一个下界，也就是说如果有渠道可以利用到方程组 3 3 3无解，则可以利用其限制 f ( x ) f(x) f(x)的下界
 *  注意到若方程组 3 3 3有解，可以推出对于任意 λ ≥ 0 \\lambda \\ge 0 λ≥0：

f ( x ) + ∑ i = 1 k λ i h i ( x ) < v (4) f(\\mathbf\{x\})+\\sum\_\{i=1\}^\{k\} \\lambda\_\{i\} h\_\{i\}(\\mathbf\{x\})<v \\tag\{4\} f(x)\+i=1∑kλihi(x)<v(4)

*  方程 4 4 4有解
 *  即命题：***if* 方程组 3 3 3有解 *then* 方程 4 4 4有解** 成立
 *  则其逆否命题 \*\**if* 方程 4 4 4无解 *then* 方程组 3 3 3无解 \*\* 成立
 *  而 **方程 4 4 4无解** 的充要（等价）条件是：

min ⁡ x f ( x ) + ∑ i = 1 k λ i g i ( x ) ≥ v (5) \\min \_\{ \\mathbf\{x\} \} f ( \\mathbf \{x\} ) + \\sum \_ \{ i=1 \} ^ \{k\} \\lambda\_\{i\} g\_\{i\} ( \\mathbf \{x\}) \\geq v \\tag\{5\} xminf(x)\+i=1∑kλigi(x)≥v(5)

*  方程 5 5 5的自变量为 λ i \\lambda\_i λi，我们的目标是要找到其上界 v m a x v\_\{max\} vmax，因此有：

v m a x = max ⁡ λ ≥ 0 min ⁡ x f ( x ) + ∑ i = 1 k λ i g i ( x ) (6) v\_\{max\}=\\max \_\{\\boldsymbol\{\\lambda\} \\geq \\mathbf\{0\}\} \\min \_\{\\mathbf\{x\}\} f(\\mathbf\{x\})+\\sum\_\{i=1\}^\{k\} \\lambda\_\{i\} g\_\{i\}(\\mathbf\{x\}) \\tag\{6\} vmax=λ≥0maxxminf(x)\+i=1∑kλigi(x)(6)

*  方程 6 6 6即为拉格朗日对偶问题的核心，延续原始问题的标记，记为：

max ⁡ α ⋅ β ; α i ≥ 0 D ( α , β ) = max ⁡ α ⋅ β ; α i ≥ 0 min ⁡ x L ( x , α , β ) (7) \\mathop \{\\max \}\\limits\_\{\\alpha \\cdot \\beta ;\{\\alpha \_i\} \\ge 0\}D(\\alpha ,\\beta ) = \\mathop \{\\max \}\\limits\_\{\\alpha \\cdot \\beta ;\{\\alpha \_i\} \\ge 0\} \\mathop \{\\min \}\\limits\_x L(x,\\alpha ,\\beta )\\tag\{7\} α⋅β;αi≥0maxD(α,β)=α⋅β;αi≥0maxxminL(x,α,β)(7)

> 可以说对偶问题就是从另一个方向逼近 f ( x ) f(x) f(x)最小值的问题

![380fa7e283fb29a3045dcc6427e28be0.gif][]

### 对偶问题的性质 ###

> 之所以引入另一个优化问题是因为对偶问题之间有着良好的性质

*  对偶问题的对偶是原问题；
 *  无论原始问题是否是凸的，对偶问题都是凸优化问题；
 *  对偶问题可以给出原始问题一个下界；
 *  当满足一定条件时，原始问题与对偶问题的解是完全等价的；

### 拉格朗日对偶问题的凹函数性质证明 ###

#### 按照定义 ####

> 对偶问题有一个很好的性质是对偶函数为凹函数，证明如下

*  命题 **拉格朗日对偶函数一定是凹函数，且其凹性与最优化函数和约束函数无关。**
 *  考虑对偶问题 7 7 7，按照凹函数定义，往证：

D ( θ α 1 + ( 1 − θ ) α 2 , θ β 1 + ( 1 − θ ) β 2 ) ≥ θ D ( α 1 , β 1 ) + ( 1 − θ ) D ( α 2 , β 2 ) (8) D(\\theta \{\\alpha \_1\} + (1 - \\theta )\{\\alpha \_2\},\\theta \{\\beta \_1\} + (1 - \\theta )\{\\beta \_2\}) \\ge \\theta D(\{\\alpha \_1\},\{\\beta \_1\}) + (1 - \\theta )D(\{\\alpha \_2\},\{\\beta \_2\}) \\tag\{8\} D(θα1\+(1−θ)α2,θβ1\+(1−θ)β2)≥θD(α1,β1)\+(1−θ)D(α2,β2)(8)

*  有：

D ( θ α 1 + ( 1 − θ ) α 2 , θ β 1 + ( 1 − θ ) β 2 ) = min ⁡ x L ( x , θ α 1 + ( 1 − θ ) α 2 , θ β 1 + ( 1 − θ ) β 2 ) = min ⁡ x ( f ( x ) + ∑ i = 1 k ( θ α 1 , i + ( 1 − θ ) α 2 , i ) h i ( x ) + ∑ j = 1 l ( θ β 1 , j + ( 1 − θ ) β 2 , j ) g j ( x ) = min ⁡ x ( θ ( f ( x ) + ∑ i = 1 k α 1 , i h i ( x ) + ∑ j = 1 l β 1 , j g j ( x ) ) + ( 1 − θ ) ( f ( x ) + ∑ i = 1 k α 2 , i h i ( x ) + ∑ j = 1 l β 2 , j g j ( x ) ) ) ≥ θ min ⁡ x ( f ( x ) + ∑ i = 1 k α 1 , i h i ( x ) + ∑ j = 1 l β 1 , j g j ( x ) ) + ( 1 − θ ) min ⁡ x ( f ( x ) + ∑ i = 1 k α 2 , i h i ( x ) + ∑ j = 1 l β 2 , j g j ( x ) ) = θ D ( α 1 , β 1 ) + ( 1 − θ ) D ( α 2 , β 2 ) (9) \\begin\{array\}\{l\} &D(\\theta \{\\alpha \_1\} + (1 - \\theta )\{\\alpha \_2\},\\theta \{\\beta \_1\} + (1 - \\theta )\{\\beta \_2\}) \\\\ &= \\mathop \{\\min \}\\limits\_x L(x,\\theta \{\\alpha \_1\} + (1 - \\theta )\{\\alpha \_2\},\\theta \{\\beta \_1\} + (1 - \\theta )\{\\beta \_2\})\\\\ &= \\mathop \{\\min \}\\limits\_x (f(x) + \\sum\\limits\_\{i = 1\}^k \{(\\theta \{\\alpha \_\{1,i\}\} + (1 - \\theta )\{\\alpha \_\{2,i\}\})\} \{h\_i\}(x) + \\sum\\limits\_\{j = 1\}^l \{(\\theta \{\\beta \_\{1,j\}\} + (1 - \\theta )\{\\beta \_\{2,j\}\})\} \{g\_j\}(x)\\\\ &= \\mathop \{\\min \}\\limits\_x (\\theta (f(x) + \\sum\\limits\_\{i = 1\}^k \{ \{\\alpha \_\{1,i\}\}\} \{h\_i\}(x) + \\sum\\limits\_\{j = 1\}^l \{ \{\\beta \_\{1,j\}\}\} \{g\_j\}(x)) + (1 - \\theta )(f(x) + \\sum\\limits\_\{i = 1\}^k \{ \{\\alpha \_\{2,i\}\}\} \{h\_i\}(x) + \\sum\\limits\_\{j = 1\}^l \{ \{\\beta \_\{2,j\}\}\} \{g\_j\}(x)))\\\\ &\\ge \\theta \\mathop \{\\min \}\\limits\_x (f(x) + \\sum\\limits\_\{i = 1\}^k \{ \{\\alpha \_\{1,i\}\}\} \{h\_i\}(x) + \\sum\\limits\_\{j = 1\}^l \{ \{\\beta \_\{1,j\}\}\} \{g\_j\}(x)) + (1 - \\theta )\\mathop \{\\min \}\\limits\_x (f(x) + \\sum\\limits\_\{i = 1\}^k \{ \{\\alpha \_\{2,i\}\}\} \{h\_i\}(x) + \\sum\\limits\_\{j = 1\}^l \{ \{\\beta \_\{2,j\}\}\} \{g\_j\}(x))\\\\ &= \\theta D(\{\\alpha \_1\},\{\\beta \_1\}) + (1 - \\theta )D(\{\\alpha \_2\},\{\\beta \_2\}) \\end\{array\} \\tag\{9\} D(θα1\+(1−θ)α2,θβ1\+(1−θ)β2)=xminL(x,θα1\+(1−θ)α2,θβ1\+(1−θ)β2)=xmin(f(x)\+i=1∑k(θα1,i\+(1−θ)α2,i)hi(x)\+j=1∑l(θβ1,j\+(1−θ)β2,j)gj(x)=xmin(θ(f(x)\+i=1∑kα1,ihi(x)\+j=1∑lβ1,jgj(x))\+(1−θ)(f(x)\+i=1∑kα2,ihi(x)\+j=1∑lβ2,jgj(x)))≥θxmin(f(x)\+i=1∑kα1,ihi(x)\+j=1∑lβ1,jgj(x))\+(1−θ)xmin(f(x)\+i=1∑kα2,ihi(x)\+j=1∑lβ2,jgj(x))=θD(α1,β1)\+(1−θ)D(α2,β2)(9)

*  其中 9 9 9的不等式来源于：
    
     *  对于实数集合 a , b \\bf\{a\},\\bf\{b\} a,b：
    
     a = \{ a 1 , a 2 , ⋯   , a n \} b = \{ b 1 , b 2 , ⋯   , b n \} (10) \\begin\{array\}\{l\} a=\\left\\\{a\_\{1\}, a\_\{2\}, \\cdots, a\_\{n\}\\right\\\} \\\\ b=\\left\\\{b\_\{1\}, b\_\{2\}, \\cdots, b\_\{n\}\\right\\\} \\end\{array\} \\tag\{10\} a=\{ a1,a2,⋯,an\}b=\{ b1,b2,⋯,bn\}(10)
    
     *  对于任意 i i i，有：
    
     min ⁡ i \{ a i + b i \} ≥ min ⁡ \{ a \} + min ⁡ \{ b \} , i ∈ N + (11) \\mathop \{\\min \}\\limits\_i \\left\\\{ \{ \{a\_i\} + \{b\_i\}\} \\right\\\} \\ge \\min \\\{ \{\\bf\{a\}\}\\\} + \\min \\\{ \{\\bf\{b\}\}\\\} ,\\quad i \\in \{N^ + \} \\tag\{11\} imin\{ ai\+bi\}≥min\{ a\}\+min\{ b\},i∈N\+(11)
 *  原命题得证。

#### 仿射函数 ####

> 另一种思路是讨论式 2 2 2的后两项内容

*  因为对偶问题中 x x x视作常数， α , β \\alpha,\\beta α,β为自变量，可以视作：

D ( α , β ∣ x ) = f ( x ) + ∑ i = 1 k α i h i ( x ) + ∑ j = 1 l β j g j ( x ) = A + ∑ i = 1 k α i B i + ∑ j = 1 l β j C j (12) \\begin\{array\}\{l\} D(\\alpha ,\\beta \{\\rm\{|x\}\}) &= f(x) + \\sum\\limits\_\{i = 1\}^k \{ \{\\alpha \_i\}\} \{h\_i\}(x) + \\sum\\limits\_\{j = 1\}^l \{ \{\\beta \_j\}\} \{g\_j\}(x)\\\\ &= A + \\sum\\limits\_\{i = 1\}^k \{ \{\\alpha \_i\}\} \{B\_i\} + \\sum\\limits\_\{j = 1\}^l \{ \{\\beta \_j\}\} \{C\_j\} \\end\{array\} \\tag\{12\} D(α,β∣x)=f(x)\+i=1∑kαihi(x)\+j=1∑lβjgj(x)=A\+i=1∑kαiBi\+j=1∑lβjCj(12)

*  因此 D ( α , β ) D(\\alpha, \\beta) D(α,β)是调整常数 A , B , C A,B,C A,B,C的仿射函数，仿射函数**既凸且凹**，因此拉格朗日对偶问题具有凹函数性质

### 拉格朗日对偶 ###

#### 原始问题 ####

*  考虑 x x x的函数：

P ( x ) = max ⁡ α , β ; α i ≥ 0 L ( x , α , β ) (13) P(x)=\\max \_\{\\alpha, \\beta ; \\alpha\_\{i\} \\geq 0\} L(x, \\alpha, \\beta) \\tag\{13\} P(x)=α,β;αi≥0maxL(x,α,β)(13)

> 这里， P P P表示原始问题。将上式看做 x x x 的函数。
> 
> 等式右边可以看做固定 x x x 的情况下，求关于 α , β \\alpha, \\beta α,β的函数 $L $的最大值的问题。

*  可以推出：

P ( x ) = \{ f ( x ) , x  满足原始问题约束  + ∞ ,  otherwise  (14) P(x)=\\left\\\{\\begin\{array\}\{l\} f(x), x \\text \{ 满足原始问题约束 \} \\\\ +\\infty, \\text \{ otherwise \} \\end\{array\}\\right. \\tag\{14\} P(x)=\{ f(x),x 满足原始问题约束 \+∞, otherwise (14)

*  考虑极小化问题：

min ⁡ x P ( x ) = min ⁡ x max ⁡ α , β ; α ≥ 0 L ( x , α , β ) (15) \\min \_\{x\} P(x)=\\min \_\{x\} \\max \_\{\\alpha, \\beta ; \\alpha \\geq 0\} L(x, \\alpha, \\beta) \\tag\{15\} xminP(x)=xminα,β;α≥0maxL(x,α,β)(15)

*  式 15 15 15与 7 7 7等价，因为固定 x x x时剩余两项在约束范围内最大值为0，相当于在约束范围内求解 f ( x ) f(x) f(x)的最小值。
 *  定义原始问题的值为：

p ∗ = min ⁡ x P ( x ) (16) p^\{\*\}=\\min \_\{x\} P(x) \\tag\{16\} p∗=xminP(x)(16)

#### 对偶问题 ####

*  延续上文的对偶问题 7 7 7
 *  可以看到事实上对偶问题与原问题为极大极小的求解顺序问题
 *  定义对偶问题的值：

d ∗ = max ⁡ α , β ; α i ≥ 0 D ( α , β ) (17) d^\{\*\}=\\max \_\{\\alpha, \\beta ; \\alpha\_\{i\} \\geq 0\} D(\\alpha, \\beta) \\tag\{17\} d∗=α,β;αi≥0maxD(α,β)(17)

#### 原始问题与对偶问题的关系 ####

*  对偶问题的解不大于原始问题的解：
 *  证明：

D ( a , β ) = min ⁡ x L ( x , a , β ) ⩽ L ( x , a , β ) ⩽ max ⁡ σ , β : a i ⩾ 0 L ( x , a , β ) = P ( x ) D ( a , β ) ⩽ P ( x ) d ∗ = max ⁡ a , B : a i ⩾ 0 min ⁡ x L ( x , a , β ) ⩽ min ⁡ x max ⁡ a , β : a i ⩾ 0 L ( x , a , β ) = p ∗ d ∗ ≤ p ∗ (18) \\begin\{array\}\{c\}\\\\ D(a, \\beta)=\\min \_\{x\} L(x, a, \\beta) \\leqslant L(x, a, \\beta) \\leqslant \\max \_\{\\sigma, \\beta: a\_\{i\} \\geqslant 0\} L(x, a, \\beta)=P(x)\\\\ D(\\mathrm\{a\}, \\beta) \\leqslant P(x)\\\\ \\mathrm\{d\}^\{\*\}=\\max \_\{\\mathrm\{a\}, \\mathrm\{B\}: \\mathrm\{a\}\_\{i\} \\geqslant 0\} \\min \_\{\\mathrm\{x\}\} L(x, \\mathrm\{a\}, \\beta) \\leqslant \\min \_\{\\mathrm\{x\}\} \\max \_\{\\mathrm\{a\}, \\mathrm\{\\beta\}: \\mathrm\{a\}\_\{i\} \\geqslant 0\} L(x, \\mathrm\{a\}, \\beta)=\\mathrm\{p\}^\{\*\}\\\\ d ^ \{ \* \} \\le p ^ \{ \* \} \\end\{array\}\\tag\{18\} D(a,β)=minxL(x,a,β)⩽L(x,a,β)⩽maxσ,β:ai⩾0L(x,a,β)=P(x)D(a,β)⩽P(x)d∗=maxa,B:ai⩾0minxL(x,a,β)⩽minxmaxa,β:ai⩾0L(x,a,β)=p∗d∗≤p∗(18)

*  该性质为弱对偶性（weak duality），该性质在任何情况下都成立
 *  也因为弱对偶的存在，使得 **对偶问题可以给出原始问题的下界**
 *  与弱对偶性相对应的是强对偶性（strong duality），即：

d ∗ = p ∗ (19) d^\{\* \} = p^\{\* \} \\tag\{19\} d∗=p∗(19)

*  若强对偶性成立，即原始问题与对偶问题的最优值相等，则可以通过求解对偶问题来得到原始问题的解

### 强对偶成立条件 ###

> 强对偶的性质太过于美妙，如果我们的问题满足强对偶条件，直接求对偶问题就好了
> 
> 这里列出两个常见的条件

#### Convex + Slater ####

*  原问题是凸优化
    
     *   f ( x ) f(x) f(x)和 h ( x ) h(x) h(x)是凸函数
     *   g ( x ) g(x) g(x)是放射函数
 *  存在 x x x使得不等式约束严格成立（严格成立不等号）

#### KKT 条件 ####

> 原问题是否为凸函数的两种情况下，KKT的用法不同

##### 原问题非凸 #####

> 当原问题并非凸优化(或者不清楚、不关心是不是凸优化)时，KKT 条件是一种用来**描述强对偶情况下最优解性质**的条件  
> 换而言之，若强对偶性质成立，那么满足最优解的**点**一定满足 KKT 条件；KKT 条件是强对偶一个**必要条件**，但无法作为充分条件来使用

##### 原问题为凸函数 #####

> 当原问题为凸优化时，KKT 条件在非凸的基础上有多了找到最优点的功能  
> 在这种情况下，那么满足 KKT 条件的点一定是原问题和对偶问题的最优解；KKT 条件成了强对偶和最优解的充要条件

### 参考资料 ###

*  https://blog.csdn.net/qq\_32742009/article/details/81413068
 *  https://blog.csdn.net/u014540876/article/details/79153913
 *  https://zhuanlan.zhihu.com/p/45431511
 *  https://www.zhihu.com/question/58584814
 *  https://blog.csdn.net/frostime/article/details/90291392

[Link 1]: https://www.zywvvd.com/2021/03/13/machine_learning/lagrange-multiplier/lagrange-multiplier/
[380fa7e283fb29a3045dcc6427e28be0.gif]: /images/20221022/ec796daf678f4ac0bca3ff8d421d69f6.png