凸优化正戏

港控/mmm° 2021-11-29 08:04 267阅读 0赞

#### 优化问题的基本形式（这里没有凸） ####

m i n i m i z e f 0 ( x ) x ∈ R n \{\\rm minimize\}\\quad f\_0(\\bm x) \\quad \\bm x\\in\\mathbb R^n minimizef0(x)x∈Rn  s u b j e c t   t o f i ( x ) ≤ 0 , i = 1 , ⋯ &ThinSpace; , m h j ( x ) = 0 , j = 1 , ⋯ &ThinSpace; , p \\quad\\quad\\quad\\quad\\quad\\begin\{aligned\}\{\\rm subject\\ to\}\\quad &f\_i(\\bm x)\\leq0,\\quad i=1,\\cdots,m\\\\&h\_j(\\bm x)=0,\\quad j=1,\\cdots,p \\end\{aligned\} subject tofi(x)≤0,i=1,⋯,mhj(x)=0,j=1,⋯,p优化变量： x ∈ R n \\bm x\\in\\mathbb R^n x∈Rn；

*  不等式约束： f i ( x ) ≤ 0 f\_i(\\bm x)\\leq0 fi(x)≤0；
 *  等式约束： h j ( x ) = 0 h\_j(\\bm x)=0 hj(x)=0；
 *  无约束优化： m = p = 0 m=p=0 m=p=0
 *  优化问题的域： D = ⋂ i = 0 m d o m   f i ∩ ⋂ j = 1 p d o m   h j D=\\bigcap^m\_\{i=0\}\{\\rm dom\}\\ f\_i\\cap\\bigcap^p\_\{j=1\}\{\\rm dom\}\\ h\_j D=i=0⋂mdom fi∩j=1⋂pdom hj
 *  可行点（解）(feasible)： x ∈ D \\bm x\\in D x∈D
 *  可行域（可解集）：所有可行点的集合；
 *  最优化值： p ⋆ = i n f \{ f 0 ( x ) ∣ f i ( x ) ≤ 0 , i = 1 , ⋯ &ThinSpace; ; m , h j ( x ) = 0 , j = 1 , ⋯ &ThinSpace; , p \} p^\\star=\{\\rm inf\}\\\{f\_0(\\bm x)|f\_i(\\bm x)\\leq0,i=1,\\cdots;m,h\_j(\\bm x)=0,j=1,\\cdots,p\\\} p⋆=inf\{ f0(x)∣fi(x)≤0,i=1,⋯;m,hj(x)=0,j=1,⋯,p\}其中 i n f \{\\rm inf\} inf表示下确界，即所有其他函数值都大于等于 p ⋆ p^\\star p⋆，是一个最大的兜底函数值。
 *  最优化解： p ⋆ = f 0 ( x ⋆ ) p^\\star=f\_0(\\bm x^\\star) p⋆=f0(x⋆)

最优化问题求解非常困难，原因如下：

*  优化问题的定义域可能弥漫着局部最优解。
 *  可能非常难于求出一个**可行点**。
 *  一般优化算法中使用的停止准则往往在约束优化问题中失效，这个很容易理解，因为我不知道目前优化变量 x \\bm x x走在哪个位置了，到底是不是可行域的点不知道，到底是不是全局最优点不知道。
 *  优化算法的收敛速率很差，因为优化函数的形式很可能是变化非常缓慢的那种。
 *  等等！

而优化问题的上述困难可以借助凸优化技术加以克服。

#### 凸优化问题的基本形式 ####

本质上，凸优化就是**凸集约束下**凸（或凹）目标函数的极小（或极大化）。  
 m i n i m i z e f 0 ( x ) x ∈ R n \{\\rm minimize\}\\quad f\_0(\\bm x) \\quad \\bm x\\in\\mathbb R^n minimizef0(x)x∈Rn  s u b j e c t   t o f i ( x ) ≤ 0 , i = 1 , ⋯ &ThinSpace; , m h j ( x ) = 0 , j = 1 , ⋯ &ThinSpace; , p \\quad\\quad\\quad\\quad\\quad\\begin\{aligned\}\{\\rm subject\\ to\}\\quad &f\_i(\\bm x)\\leq0,\\quad i=1,\\cdots,m\\\\&h\_j(\\bm x)=0,\\quad j=1,\\cdots,p \\end\{aligned\} subject tofi(x)≤0,i=1,⋯,mhj(x)=0,j=1,⋯,p

*  首先要明白，这里的 x \\bm x x可不是机器学习中的训练数据，而是要优化的参数 w , b \\bm w,b w,b等，不要搞混了。
 *  其中， f i ( x ) f\_i(\\bm x) fi(x)为凸函数， h j ( x ) h\_j(x) hj(x)为仿射函数。可是大家有没有想过，这是为什么？  
    因为我们要**保证可行域是凸集**，这点非常关键，凸优化问题必须在凸集下才能发挥其优良特性。凸函数 f i ( x ) ≤ 0 f\_i(\\bm x)\\leq0 fi(x)≤0的产生的可行域一定是凸集；仿射函数 h j ( x ) = 0 h\_j(\\bm x)=0 hj(x)=0产生的可行域也一定是凸集；而凸集的交集还是凸集，最终保证了凸优化问题的可行域是凸集。
 *  凸优化问题最重要的性质：
    
     *  凸优化问题的可行域是凸集；
     *  凸优化问题的**局部**最优解即为**全局最优解**。

#### 思考： ####

一般的带约束优化问题是怎么解的呢？回顾考研的数学学习，发现通常是将带约束的优化问题转变为拉格朗日函数的无约束优化问题。这也启发我们将上文介绍的优化问题转变成无约束优化问题，那借助什么转变呢？  
还是**拉格朗日乘子法**，但是机器学习中的优化问题会和考研那种题型一样简单吗？当然不会！那能用那种简单粗暴的对各个拉格朗日函数 L ( x , y , z , λ , η ) \\mathcal L(x,y,z,\\lambda,\\eta) L(x,y,z,λ,η)的自变量求偏导、联立解方程、求驻点、比较驻点函数值大小求极值的方法来处理吗？不行！因为我们的限制条件不仅只有**等于号**方程的限制，还有**小于等于号**的限制。那对于小于号不等式方程的限制，我先求全局极值点，然后判断这些极值点是否在限制范围之内进而选取可行的极值点行不行？不行！优化的目标函数和限制条件关系非常紧密，不考虑限制条件直接求优化目标函数之后再反带驻点看是否满足限制条件一则可行性不高（优化目标函数通常无法直接求极值，因为信息量太少，多数信息量都隐藏着在限制条件中）、二则即便勉强能行，解起来也会让人望而却步，头皮发麻，天旋地转。  
总之，考研中的拉格朗日函数解法我们可以理解成启蒙版最优化解法，成不了主戏和正餐，我们只是在这里让考研版拉格朗日函数抛砖引玉。

相信接触过凸优化的同志们都听过**原始问题、对偶问题、原始变量、对偶变量**这些名词，那么他们是怎么来的呢？为此我们接下来要正式引入拉格朗日乘子法。

#### 拉格朗日乘子法 ####

利用拉格朗日乘子法，约束优化问题可以松弛为为无约束优化问题。

*  广义拉格朗日函数（generalized Lagrangian） L ( x , λ , ν ) = f 0 ( x ) + ∑ i = 1 m λ i f i ( x ) + ∑ j = 1 p ν i h j ( x ) L(\\bm x,\\bm \\lambda,\\bm \\nu)=f\_0(\\bm x)+\\sum^m\_\{i=1\}\\lambda\_if\_i(\\bm x)+\\sum^p\_\{j=1\}\\nu\_ih\_j(\\bm x) L(x,λ,ν)=f0(x)\+i=1∑mλifi(x)\+j=1∑pνihj(x)
    
     *   λ i , i = 1 , ⋯ &ThinSpace; , m \\lambda\_i,i=1,\\cdots,m λi,i=1,⋯,m和 ν j , j = 1 , ⋯ &ThinSpace; , q \\nu\_j,j=1,\\cdots,q νj,j=1,⋯,q分别是针对不等式约束 f i ( x ) ≤ 0 f\_i(\\bm x)\\leq 0 fi(x)≤0和等式约束 h j ( x ) = 0 h\_j(\\bm x)=0 hj(x)=0的拉格朗日乘子（Lagrangian multipliers）， λ , ν \\bm \\lambda,\\bm \\nu λ,ν为拉格朗日**乘子**向量，也可以称为**对偶变量**（dual variables）。
     *  向量 x \\bm x x被称为**原始变量**。
     *  这里对Lagrangian乘子 λ i \\lambda\_i λi做一个关键的非负性约束： λ i ≥ 0 , i = 1 , ⋯ &ThinSpace; , m \\lambda\_i\\geq0,i=1,\\cdots,m λi≥0,i=1,⋯,m，如果用分量不等式，则表示为 λ ≻ 0 \\bm \\lambda\\succ\\bm0 λ≻0；而对另一个Lagrangian乘子 ν j , j = 1 , ⋯ &ThinSpace; , p \\nu\_j,j=1,\\cdots,p νj,j=1,⋯,p，不做任何约束。
     *  对于固定的 x \\bm x x，Lagrangian函数 L ( x , λ , ν ) L(\\bm x,\\bm \\lambda,\\bm \\nu) L(x,λ,ν)为关于 λ \\bm\\lambda λ和 ν \\bm \\nu ν的**仿射函数**。

#### 原始问题和对偶问题 ####

*  **原始问题**（primal problem）  
    原始问题是广义Lagrangian函数的**极小–极大问题**，为什么呢？首先表示出来 p ⋆ = m i n x m a x λ , ν : λ i ≥ 0 L ( x , λ , ν ) = m i n x θ P ( x ) \\begin\{aligned\}p^\\star&=\\underset\{\\bm x\}\{\\rm min\}\\underset\{\\bm \\lambda,\\bm \\nu:\\lambda\_i\\geq0\}\{\\rm max\}L(\\bm x,\\bm \\lambda,\\bm \\nu)\\\\ &=\\underset\{\\bm x\}\{\\rm min\}\\quad\\theta\_P(\\bm x) \\end\{aligned\} p⋆=xminλ,ν:λi≥0maxL(x,λ,ν)=xminθP(x) 这里的 θ P ( x )   : = m a x λ , ν : λ i ≥ 0 L ( x , λ , ν ) \\theta\_P(\\bm x)\\ :=\\underset\{\\bm \\lambda,\\bm \\nu:\\lambda\_i\\geq0\}\{\\rm max\}L(\\bm x,\\bm \\lambda,\\bm \\nu) θP(x) :=λ,ν:λi≥0maxL(x,λ,ν)，那么为什么计算**极小—极大问题**就等同于计算原始凸优化问题呢？接下来我们研究 θ P ( x ) \\theta\_P(\\bm x) θP(x)，在研究之前，必须保证有这种意识，即在计算 θ P ( x ) \\theta\_P(\\bm x) θP(x)的过程中，其实变动的是对偶变量 λ , ν \\bm \\lambda,\\bm \\nu λ,ν，我们必须将原始变量 x \\bm x x当成**常数**对待，此时，Lagrangian函数 L ( x , λ , ν ) L(\\bm x,\\bm \\lambda,\\bm \\nu) L(x,λ,ν)是关于变量 λ \\bm \\lambda λ和 ν \\bm \\nu ν的**仿射函数**。有了这点作保证，接下来进入 θ P ( x ) \\theta\_P(\\bm x) θP(x)的具体分析：
    
     *  如果 f i ( x ) > 0 ,   i ∈ \{ 1 , ⋯ &ThinSpace; , m \} f\_i(\\bm x)>0,\\ i\\in\\\{1,\\cdots,m\\\} fi(x)>0, i∈\{ 1,⋯,m\}，则 λ i = + ∞ ， 其 余 λ j : j 不 等 于 i = 0 \\lambda\_i=+\\infty，其余\\lambda\_\{j:j不等于i\}=0 λi=\+∞，其余λj:j不等于i=0，从而导致 θ P ( x ) = + ∞ \\theta\_P(\\bm x)=+\\infty θP(x)=\+∞；
     *  如果 h j ( x ) h\_j(\\bm x) hj(x)≠ 0 ,   j ∈ \{ 1 , ⋯ &ThinSpace; , p \} 0,\\ j\\in\\\{1,\\cdots,p\\\} 0, j∈\{ 1,⋯,p\}，则令 ν j = + ∞ \\nu\_j=+\\infty νj=\+∞或 − ∞ -\\infty −∞，从而也会有 θ P ( x ) = + ∞ \\theta\_P(\\bm x)=+\\infty θP(x)=\+∞。
     *  如果 x \\bm x x满足原始全部约束，即 x \\bm x x在可行域内，则 θ P ( x ) = f 0 ( x ) \\theta\_P(\\bm x)=f\_0(\\bm x) θP(x)=f0(x)。
    
    从以上可以看出， θ P ( x ) \\theta\_P(\\bm x) θP(x)保证了原始问题的最小值落在了可行域内，如果 x \\bm x x不在可行域内，由于 θ P ( x ) → + ∞ \\theta\_P(\\bm x)\\to+\\infty θP(x)→\+∞，使得可行域外 θ P ( x ) \\theta\_P(\\bm x) θP(x)没有最小值。
 *  **对偶问题**（dual problem）  
    对偶问题通常要比他对应的原始问题更容易求解。  
    原始问题的对偶问题的最优解我们标记为 d ⋆ d^\\star d⋆，对偶问题是广义Lagrangian函数的**极大—极小问题**，对偶问题的解 d ⋆ d^\\star d⋆，数学描述为： d ⋆ = m a x λ , ν : λ i ≥ 0 m i n x L ( x , λ , ν ) = m a x λ , ν : λ i ≥ 0 θ D ( λ , ν ) \\begin\{aligned\}d^\\star&=\\underset\{\\bm \\lambda,\\bm \\nu:\\lambda\_i\\geq0\}\{\\rm max\}\\underset\{\\bm x\}\{\\rm min\}L(\\bm x,\\bm \\lambda,\\bm \\nu)\\\\ &=\\underset\{\\bm \\lambda,\\bm \\nu:\\lambda\_i\\geq0\}\{\\rm max\}\\theta\_D(\\bm\\lambda,\\bm\\nu) \\end\{aligned\} d⋆=λ,ν:λi≥0maxxminL(x,λ,ν)=λ,ν:λi≥0maxθD(λ,ν) 这里 θ D ( λ , ν ) :   = m i n x L ( x , λ , ν ) \\theta\_D(\\bm\\lambda,\\bm\\nu):\\ =\\underset\{\\bm x\}\{\\rm min\}L(\\bm x,\\bm \\lambda,\\bm \\nu) θD(λ,ν): =xminL(x,λ,ν)是Lagrangian对偶函数，更为细致的描述如下： θ D ( λ , ν ) = i n f x ( f 0 ( x ) + ∑ i = 1 m λ i f i ( x ) + ∑ j = 1 p ν i h j ( x ) ) \\theta\_D(\\bm\\lambda,\\bm\\nu)=\\underset\{\\bm x\}\{\\rm inf\}\\left(f\_0(\\bm x)+\\sum^m\_\{i=1\}\\lambda\_if\_i(\\bm x)+\\sum^p\_\{j=1\}\\nu\_ih\_j(\\bm x)\\right) θD(λ,ν)=xinf(f0(x)\+i=1∑mλifi(x)\+j=1∑pνihj(x)) 接下来我们要说点重要的事情了，是什么呢？  
    Lagrangian对偶函数 θ D ( λ , ν ) \\theta\_D(\\bm\\lambda,\\bm\\nu) θD(λ,ν)一定是**凹函数**，即使目标函数 f 0 ( x ) f\_0(\\bm x) f0(x)不是凸函数；不等式约束函数 f i ( x ) f\_i(\\bm x) fi(x)必须是凸函数，等式约束函数 h j ( x ) h\_j(\\bm x) hj(x)必须是仿射函数，因为我们要保证可行域是凸集。而凹函数任何一个局部极值点都是全局极值点，这也是我们为什么把原函数转换为对偶函数求解的目的之一。现在的困惑是为什么Lagrangian对偶函数是凹函数，怎么证明？  
    其实和上面看待 θ P ( x ) \\theta\_P(\\bm x) θP(x)的角度类似，这里研究Lagrangian对偶函数时，是把对偶变量 λ , ν \\bm \\lambda,\\bm\\nu λ,ν看成一对常量，变动原始变量 x \\bm x x，但是不止于此，我们仍需要做一件事，那就是把变动的 x \\bm x x看成是有无穷多个离散的常量 x 1 , ⋯ &ThinSpace; , x n , n → ∞ \\bm x\_1,\\cdots,\\bm x\_n,n\\to\\infty x1,⋯,xn,n→∞，为什么这样看待呢？因为这样才能恰如其分的发挥**仿射函数既凸又凹**的奇效，用这种角度表示的Lagrangian对偶函数如下： (公式1) θ D ( λ , ν ) = m i n \{ L ( x 1 , λ , ν ) , L ( x 2 , λ , ν ) , ⋯ &ThinSpace; , L ( x n , λ , ν ) \} n → ∞ \\theta\_D(\\bm\\lambda,\\bm\\nu)=\{\\rm min\}\\left\\\{L(\\bm x\_1,\\bm \\lambda,\\bm\\nu),L(\\bm x\_2,\\bm \\lambda,\\bm\\nu),\\cdots,L(\\bm x\_n,\\bm \\lambda,\\bm\\nu)\\right\\\}\\quad n\\to\\infty\\tag\{公式1\} θD(λ,ν)=min\{ L(x1,λ,ν),L(x2,λ,ν),⋯,L(xn,λ,ν)\}n→∞(公式1) 接下来的问题就是，如何证明对偶函数 θ D ( λ , ν ) \\theta\_D(\\bm\\lambda,\\bm\\nu) θD(λ,ν)是凹函数。如果我们能证下式 (公式2) θ D ( η ( λ 1 , ν 1 ) + ( 1 − η ) ( λ 2 , ν 2 ) ) ≥ η θ D ( λ 1 , ν 1 ) + ( 1 − η ) θ D ( λ 2 , ν 2 ) \\theta\_D(\\eta(\\bm\\lambda\_1,\\bm\\nu\_1)+(1-\\eta)(\\bm\\lambda\_2,\\bm\\nu\_2))\\geq\\eta\\theta\_D(\\bm\\lambda\_1,\\bm\\nu\_1)+(1-\\eta)\\theta\_D(\\bm\\lambda\_2,\\bm\\nu\_2)\\tag\{公式2\} θD(η(λ1,ν1)\+(1−η)(λ2,ν2))≥ηθD(λ1,ν1)\+(1−η)θD(λ2,ν2)(公式2)成立，则就证明了对偶函数 θ D ( λ , ν ) \\theta\_D(\\bm\\lambda,\\bm\\nu) θD(λ,ν)是凹函数。  
    证明：由(公式一)可知， θ D ( η ( λ 1 , ν 1 ) + ( 1 − η ) ( λ 2 , ν 2 ) ) = m i n \{ L \[ x 1 , η ( λ 1 , ν 1 ) + ( 1 − η ) ( λ 2 , ν 2 ) \] , L \[ x 2 , η ( λ 1 , ν 1 ) + ( 1 − η ) ( λ 2 , ν 2 ) \] , ⋯ &ThinSpace; , L \[ x n , η ( λ 1 , ν 1 ) + ( 1 − η ) ( λ 2 , ν 2 ) \] \} ≥ m i n \{ η L \[ x 1 , ( λ 1 , ν 1 ) \] + ( 1 − η ) L \[ x 1 , ( λ 2 , ν 2 ) \] , η L \[ x 2 , ( λ 1 , ν 1 ) \] + ( 1 − η ) L \[ x 2 , ( λ 2 , ν 2 ) \] , ⋯ &ThinSpace; , η L \[ x n , ( λ 1 , ν 1 ) \] + ( 1 − η ) L \[ x n , ( λ 2 , ν 2 ) \] \} ≥ η   m i n \{ L ( x 1 , λ 1 , ν 1 ) , L ( x 2 , λ 1 , ν 1 ) , ⋯ &ThinSpace; , L ( x n , λ 1 , ν 1 ) \} + ( 1 − η ) m i n \{ L ( x 1 , λ 2 , ν 2 ) , L ( x 2 , λ 2 , ν 2 ) , ⋯ &ThinSpace; , L ( x n , λ 2 , ν 2 ) \} = η θ D ( λ 1 , ν 1 ) + ( 1 − η ) θ D ( λ 2 , ν 2 ) \\begin\{aligned\} &\\theta\_D(\\eta(\\bm\\lambda\_1,\\bm\\nu\_1)+(1-\\eta)(\\bm\\lambda\_2,\\bm\\nu\_2))\\\\ &=\{\\rm min\}\\left\\\{L\[\\bm x\_1,\\eta(\\bm\\lambda\_1,\\bm\\nu\_1)+(1-\\eta)(\\bm\\lambda\_2,\\bm\\nu\_2)\],L\[\\bm x\_2,\\eta(\\bm\\lambda\_1,\\bm\\nu\_1)+(1-\\eta)(\\bm\\lambda\_2,\\bm\\nu\_2)\],\\cdots,L\[\\bm x\_n,\\eta(\\bm\\lambda\_1,\\bm\\nu\_1)+(1-\\eta)(\\bm\\lambda\_2,\\bm\\nu\_2)\]\\right\\\}\\\\ &\\geq\{\\rm min\}\\left\\\{\\eta L\[\\bm x\_1,(\\bm\\lambda\_1,\\bm\\nu\_1)\]+(1-\\eta)L\[\\bm x\_1,(\\bm\\lambda\_2,\\bm\\nu\_2)\],\\eta L\[\\bm x\_2,(\\bm\\lambda\_1,\\bm\\nu\_1)\]+(1-\\eta)L\[\\bm x\_2,(\\bm\\lambda\_2,\\bm\\nu\_2)\],\\cdots,\\eta L\[\\bm x\_n,(\\bm\\lambda\_1,\\bm\\nu\_1)\]+(1-\\eta)L\[\\bm x\_n,(\\bm\\lambda\_2,\\bm\\nu\_2)\]\\right\\\}\\\\ &\\geq\\eta\\ \{\\rm min\}\\left\\\{L(\\bm x\_1,\\bm \\lambda\_1,\\bm\\nu\_1),L(\\bm x\_2,\\bm \\lambda\_1,\\bm\\nu\_1),\\cdots,L(\\bm x\_n,\\bm \\lambda\_1,\\bm\\nu\_1)\\right\\\}+\\\\ &(1-\\eta)\{\\rm min\}\\left\\\{L(\\bm x\_1,\\bm \\lambda\_2,\\bm\\nu\_2),L(\\bm x\_2,\\bm \\lambda\_2,\\bm\\nu\_2),\\cdots,L(\\bm x\_n,\\bm \\lambda\_2,\\bm\\nu\_2)\\right\\\}\\\\ &=\\eta\\theta\_D(\\bm\\lambda\_1,\\bm\\nu\_1)+(1-\\eta)\\theta\_D(\\bm\\lambda\_2,\\bm\\nu\_2) \\end\{aligned\} θD(η(λ1,ν1)\+(1−η)(λ2,ν2))=min\{ L\[x1,η(λ1,ν1)\+(1−η)(λ2,ν2)\],L\[x2,η(λ1,ν1)\+(1−η)(λ2,ν2)\],⋯,L\[xn,η(λ1,ν1)\+(1−η)(λ2,ν2)\]\}≥min\{ ηL\[x1,(λ1,ν1)\]\+(1−η)L\[x1,(λ2,ν2)\],ηL\[x2,(λ1,ν1)\]\+(1−η)L\[x2,(λ2,ν2)\],⋯,ηL\[xn,(λ1,ν1)\]\+(1−η)L\[xn,(λ2,ν2)\]\}≥η min\{ L(x1,λ1,ν1),L(x2,λ1,ν1),⋯,L(xn,λ1,ν1)\}\+(1−η)min\{ L(x1,λ2,ν2),L(x2,λ2,ν2),⋯,L(xn,λ2,ν2)\}=ηθD(λ1,ν1)\+(1−η)θD(λ2,ν2) 下面对上面证明中的不等式进行说明：
    
     *  第一个 ≥ \\geq ≥成立是因为 L ( x n , ( λ , ν ) ) L(\\bm x\_n,(\\bm \\lambda,\\bm \\nu)) L(xn,(λ,ν))中 x n \\bm x\_n xn的值已固定，所以 f i ( x n ) ,   i = 0 , 1 , ⋯ &ThinSpace; , m f\_i(\\bm x\_n),\\ i=0,1,\\cdots,m fi(xn), i=0,1,⋯,m，和 h j ( x n ) ,   j = 1 , ⋯ &ThinSpace; , p h\_j(\\bm x\_n),\\ j=1,\\cdots,p hj(xn), j=1,⋯,p 都应该看做常数，所以此时的 L ( x n , ( λ , ν ) ) L(\\bm x\_n,(\\bm \\lambda,\\bm \\nu)) L(xn,(λ,ν))是关于 λ \\bm \\lambda λ和 ν \\bm \\nu ν的仿射函数，利用仿射函数的既凸又凹特性，就会有形如 f ( η x + ( 1 − η ) y ) ≥ η f ( x ) + ( 1 − η ) f ( y ) f(\\eta \\bm x+(1-\\eta)\\bm y)\\geq\\eta f(\\bm x)+(1-\\eta)f(\\bm y) f(ηx\+(1−η)y)≥ηf(x)\+(1−η)f(y)的不等式成立，其中 f ( x ) f(\\bm x) f(x)是定义在凸集上的凹函数，故第一个不等式 ≥ \\geq ≥成立。
     *  第二个不等式成立其实很简单，因为单独找内部各自的最小值，然后把各自的最小值加起来所得的最小值一定小于“内部各分量加起来”从整体中找最小值所得的值，数学语言描述为： a = \{ a 1 , a 2 , ⋯ &ThinSpace; , a n \} b =   \{ b 1 , b 2 , ⋯ &ThinSpace; , b n \} m i n \{ a + b \} ≥ m i n \{ a \} + m i n \{ b \} \\begin\{aligned\}&a=\\\{a\_1,a\_2,\\cdots,a\_n\\\}\\\\ &b=\\ \\\{b\_1,b\_2,\\cdots,b\_n\\\}\\\\ & \{\\rm min\}\\\{a+b\\\}\\geq\{\\rm min\}\\\{a\\\}+\{\\rm min\}\\\{b\\\} \\end\{aligned\} a=\{ a1,a2,⋯,an\}b= \{ b1,b2,⋯,bn\}min\{ a\+b\}≥min\{ a\}\+min\{ b\} 故第二个不等式 ≥ \\geq ≥也成立。
     *  当然，在每一个固定点 λ , ν \\bm \\lambda,\\bm \\nu λ,ν处不一定存在下界，我们可以把下界看成是 − ∞ -\\infty −∞。  
        **证毕**。(上面的证明过程参考: [熙来攘往博客][Link 1])
    
    接下来求对偶函数 θ D ( λ , ν ) \\theta\_D(\\bm\\lambda,\\bm\\nu) θD(λ,ν)的最大值后，**就完成了对偶问题的求解过程**。

#### 弱对偶性（weak duality） ####

即对偶问题的值 d ⋆ d^\\star d⋆**小于等于**原始问题的值 p ⋆ p^\\star p⋆，即 θ D ( λ , ν ) ≤ d ⋆ ≤ p ⋆ ≤ θ P ( x ) \\theta\_D(\\bm\\lambda,\\bm\\nu)\\leq d^\\star\\leq p^\\star\\leq\\theta\_P(\\bm x) θD(λ,ν)≤d⋆≤p⋆≤θP(x)这就是通常优化问题的**弱对偶性**。问题是为什么呢？  
下面证明不等式  m a x x   m i n y f ( x , y ) ≤ m i n y   x m a x f ( x , y ) \\underset\{\\bm x\}\{\\rm max\}\\ \\underset\{\\bm y\}\{\\rm min\}f(\\bm x,\\bm y)\\leq\\underset\{\\bm y\}\{\\rm min\}\\underset\{\\bm x\}\\ \{\\rm max\}f(\\bm x,\\bm y) xmax yminf(x,y)≤yminx maxf(x,y)  
证明：对于任意的 ( x , y ) ∈ d o m f (\\bm x,\\bm y)\\in\{\\rm dom\}f (x,y)∈domf  f ( x , y ) ≤ m a x x f ( x , y ) ⇒ m i n y f ( x , y ) ≤ m i n y m a x x f ( x , y ) ⇒ m a x x   m i n y f ( x , y ) ≤ m i n y   x m a x f ( x , y ) \\begin\{aligned\}&f(\\bm x,\\bm y)\\leq\\underset\{\\bm x\}\{\\rm max\}f(\\bm x,\\bm y)\\\\ &\\Rightarrow\\underset\{\\bm y\}\{\\rm min\}f(\\bm x,\\bm y)\\leq\\underset\{\\bm y\}\{\\rm min\}\\underset\{\\bm x\}\{\\rm max\}f(\\bm x,\\bm y)\\\\ &\\Rightarrow\\underset\{\\bm x\}\{\\rm max\}\\ \\underset\{\\bm y\}\{\\rm min\}f(\\bm x,\\bm y)\\leq\\underset\{\\bm y\}\{\\rm min\}\\underset\{\\bm x\}\\ \{\\rm max\}f(\\bm x,\\bm y) \\end\{aligned\} f(x,y)≤xmaxf(x,y)⇒yminf(x,y)≤yminxmaxf(x,y)⇒xmax yminf(x,y)≤yminx maxf(x,y)这里面蕴藏着一个道理，求其上着得其中，求其中者得起下，求其下者无所得。《论语》也说过，取乎其上，得乎其中；取乎其中，得乎其下；取乎其下，则无所得矣。做事起初的眼界和格局就很大程度上决定了我们能到达的高度，心里若只有三尺土地，又怎能鹏程万里、遍历无限山河？不过做事时一定要脚踏实地、稳步开来，有没有糊弄、将就每一个细小节目，自己心里最清楚。

#### 强对偶性 ####

若要求对偶函数的最大值等于原始问题的最小值，则需满足： f 0 ( x ⋆ ) = θ D ( λ ⋆ , ν ⋆ ) = i n f x ( f 0 ( x ) + ∑ i = 1 m λ i ⋆ f i ( x ) + ∑ j = 1 p ν i ⋆ h j ( x ) ) ≤ f 0 ( x ⋆ ) + ∑ i = 1 m λ i ⋆ f i ( x ⋆ ) + ∑ j = 1 p ν i ⋆ h j ( x ⋆ ) ≤ f 0 ( x ⋆ ) \\begin\{aligned\} f\_0(\\bm x^\\star)&=\\theta\_D(\\bm\\lambda^\\star,\\bm\\nu^\\star)\\\\ &=\\underset\{\\bm x\}\{\\rm inf\}\\left(f\_0(\\bm x)+\\sum^m\_\{i=1\}\\lambda^\\star\_if\_i(\\bm x)+\\sum^p\_\{j=1\}\\nu^\\star\_ih\_j(\\bm x)\\right)\\\\ &\\leq f\_0(\\bm x^\\star)+\\sum^m\_\{i=1\}\\lambda^\\star\_if\_i(\\bm x^\\star)+\\sum^p\_\{j=1\}\\nu^\\star\_ih\_j(\\bm x^\\star)\\\\ &\\leq f\_0(\\bm x^\\star) \\end\{aligned\} f0(x⋆)=θD(λ⋆,ν⋆)=xinf(f0(x)\+i=1∑mλi⋆fi(x)\+j=1∑pνi⋆hj(x))≤f0(x⋆)\+i=1∑mλi⋆fi(x⋆)\+j=1∑pνi⋆hj(x⋆)≤f0(x⋆) 由此也顺利引出了满足强对偶性的KKT条件。

*  KKT条件说：
    
     *   f i ( x ⋆ ) ≤ 0 ,   i = 1 , ⋯ &ThinSpace; , m f\_i(\\bm x^\\star)\\leq0,\\ i=1,\\cdots,m fi(x⋆)≤0, i=1,⋯,m，原始不等式约束；
     *   h j ( x ⋆ ) = 0 ,   j = 1 , ⋯ &ThinSpace; , p h\_j(\\bm x^\\star)=0,\\ j=1,\\cdots,p hj(x⋆)=0, j=1,⋯,p，原始等式约束；
     *   λ i ⋆ ≥ 0 ,   i = 1 , ⋯ &ThinSpace; , m \\lambda\_i^\\star\\geq0,\\ \\quad \\quad i=1,\\cdots,m λi⋆≥0, i=1,⋯,m，非负性；
     *   λ i ⋆ f i ( x ⋆ ) = 0 , i = 1 , ⋯ &ThinSpace; , m \\lambda\_i^\\star f\_i(\\bm x^\\star)=0,i=1,\\cdots,m λi⋆fi(x⋆)=0,i=1,⋯,m，这是**互补松弛性**，非常重要；
     *  由于 x ⋆ \\bm x^\\star x⋆使Lagrangian函数 L ( x , λ ⋆ , ν ⋆ ) L(\\bm x,\\bm\\lambda^\\star,\\bm\\nu^\\star) L(x,λ⋆,ν⋆)在所有原始可行点 x \\bm x x中最小化，所以Lagrangian函数在 x ⋆ \\bm x^\\star x⋆的**梯度向量**必然等于零向量，即 ∇ x f 0 ( x ⋆ ) + ∑ i = 1 m λ i ⋆ ∇ x f i ( x ⋆ ) + ∑ j = 1 q ν j ⋆ ∇ x h j ( x ⋆ ) = 0 \\nabla\_\{\\bm x\}f\_0(\\bm x^\\star)+\\sum^m\_\{i=1\}\\lambda\_i^\\star\\nabla\_\{\\bm x\}f\_i(\\bm x^\\star)+\\sum^q\_\{j=1\}\\nu\_j^\\star\\nabla\_\{\\bm x\}h\_j(\\bm x^\\star)=0 ∇xf0(x⋆)\+i=1∑mλi⋆∇xfi(x⋆)\+j=1∑qνj⋆∇xhj(x⋆)=0

说明，**KKT条件不是**Lagrangian函数对偶无约束优化问题的最优解**等于**原始约束优化问题的最优解的**充分条件**，只是**必要条件**；**如果**再加上一条原始约束优化问题为**凸优化问题**，即可成为**充分条件**。

换一种说法，凸优化问题可以利用**满足KKT条件**实现**强对偶性**，这是其中一种方法。  
还有一种方法就是Slater条件。

##### Slater条件（强对偶性的判断） #####

自己google吧。

#### 原始约束问题与Lagrangian对偶无约束凸优化的最优解之间的关系 ####

1.  只有当**不等式约束**函数 f i ( x ) ,   i = 1 , ⋯ &ThinSpace; , m f\_i(\\bm x),\\ i=1,\\cdots,m fi(x), i=1,⋯,m 均为**凸函数**，且**等式约束**函数 h j ( x ) ,   j = 1 , ⋯ &ThinSpace; , p h\_j(\\bm x),\\ j=1,\\cdots,p hj(x), j=1,⋯,p 均为**仿射函数**时，一个原始约束优化问题才能借助Lagrangian乘子法，转换成一个**凹函数**的对偶无约束极大化问题。
2.  若原始约束优化问题的目标函数  f 0 ( x ) f\_0(\\bm x) f0(x)不是凸函数，但**不等式约束**函数 f i ( x ) ,   i = 1 , ⋯ &ThinSpace; , m f\_i(\\bm x),\\ i=1,\\cdots,m fi(x), i=1,⋯,m 均为**凸函数**，且**等式约束**函数 h j ( x ) ,   j = 1 , ⋯ &ThinSpace; , p h\_j(\\bm x),\\ j=1,\\cdots,p hj(x), j=1,⋯,p 均为**仿射函数**，则Lagrangian目标函数满足 K K T \{\\rm KKT\} KKT条件的点 x ⋆ \\bm x^\\star x⋆和 ( λ ⋆ , ν ⋆ ) (\\bm \\lambda^\\star,\\bm\\nu^\\star) (λ⋆,ν⋆)一般不会分别是原始最优点和对偶最优点，即Lagrangian函数对偶无约束优化问题的最优解不是原始约束优化问题的最优解，而是 ϵ \\epsilon ϵ\-次最优解，其中 ϵ = f 0 ( x ⋆ ) − θ D ( λ ⋆ , ν ⋆ ) \\epsilon=f\_0(\\bm x^\\star)-\\theta\_D(\\bm \\lambda^\\star,\\bm \\nu^\\star) ϵ=f0(x⋆)−θD(λ⋆,ν⋆)。
3.  若 f 0 ( x ) f\_0(\\bm x) f0(x)和 f i ( x ) f\_i(\\bm x) fi(x)均为凸函数，并且等式约束函数 h j ( x ) h\_j(\\bm x) hj(x)均为仿射函数，即原始约束优化问题为**凸优化问题**，则Lagrangian目标函数满足 K K T \{\\rm KKT\} KKT条件的点  x ~ \\bm \{\\tilde x\} x~ 和 ( λ ~ , ν ~ ) (\\bm\{\\tilde \\lambda\},\\bm\{\\tilde \\nu\}) (λ~,ν~) 分别是具有零对偶间隙的原始最优点和对偶最优点。换言之，Lagrangian函数对偶无约束优化问题的最优解 d ⋆ d^\\star d⋆就是原始约束优化问题的最优解 p ⋆ p^\\star p⋆。

[Link 1]: https://blog.csdn.net/u014540876/article/details/79153913