04-拉格朗日對偶問題和KKT條件

一、拉格朗日對偶函式
二、拉格朗日對偶問題
三、強弱對偶的幾何解釋
四、鞍點解釋
- 4.1 鞍點的基礎定義
- 4.2 極大極小不等式和鞍點性質
五、最優性條件與 KKT 條件
- 5.1 KKT 條件
- 5.2 KKT 條件與凸問題
- 5.3 互補松弛性
六、擾動及靈敏度分析
- 6.1 擾動問題
- 6.2 靈敏度分析
七、Reformulation
- 7.1 引入等式約束
- 7.2 顯示約束與隱式約束的相互轉化
- 7.3 轉化目標函式與約束函式

凸優化從入門到放棄完整教程地址：https://www.cnblogs.com/nickchen121/p/14900036.html

一、拉格朗日對偶函式

[題設] 考慮以下標準形式的優化問題：

$\begin{aligned} \text{minimize} \quad & f_0(x) \\ \text{s.t.} \quad & f_i(x)\leq 0, i=1,...,m \\ &h_i(x)=0, i=1,...,p \end{aligned}$

其中 $x\in R^n$ ，設值域 $D=\cap^m_{i=0}dom~f_i\cap^p_{i=1}dom~h_i$ 不為空，
最優值記為 $p^*$ ，不假設這個問題是凸的，
拉格朗日對偶：通過添加約束的加權和來增廣目標函式，

[拉格朗日函式] 定義拉格朗日函式 $L: R^n\times R^m\times R^p\rightarrow R$ 為

注：大概知道拉格朗日函式的構造形式即可，下面在拉個朗日對偶問題中會詳細敘述它的作用

$L(x,\lambda,v)=f_0(x)+\sum^m_{i=1}\lambda_i f_i(x) +\sum^p_{i=1}v_ih_i(x).$

值域： $dom~L=D\times R^m \times R^p.$
拉格朗日乘子：記 $\lambda_i$ 是第 $i$ 個不等式約束 $f_i(x)\leq 0$ 的拉格朗日乘子； $v_i$ 是第 $i$ 個等式約束 $h_i(x)=0$ 的拉格朗日乘子，
乘子向量：向量 $\lambda$ 和 $v$ 稱為對偶變數，或該問題的拉格朗日乘子向量，

[拉格朗日對偶函式] 定義拉格朗日對偶函式（或對偶函式） $g:R^m\times R^p\rightarrow R$ 為拉格朗日函式關于 $x$ 取得的最小值：對于 $\lambda\in R^m, v\in R^p$

$g(\lambda,v)=inf_{x\in D} L(x,\lambda,v)$

注：上面為什么用 $\inf$ 這個函式，因為解可能是趨向于一個值，而不是一個具體的值

如果關于 $x$ 無下界，那么對偶函式取值 $-\infty.$
對偶函式是凹的：因為對偶函式是一組關于 $(\lambda,v)$ 的仿射函式的逐點下確界，所以即使題設是凸的，對偶函式也是凹的

[最優值的下界] 對偶函式給出最優值 $p^*$ 的下界： $g(\lambda,v)\leq p^*$ ， $\forall \lambda\succeq 0, \forall v.$

二、拉格朗日對偶問題

[拉格朗日對偶問題] 拉格朗日函式能給出的最好下界：

$\begin{aligned} \text{maxmize} \quad &g(\lambda,v) \\ \text{s.t.} \quad & \lambda\succeq 0 \end{aligned}$

注：這里解釋下為什么要這樣構造拉格朗日對偶問題，首先明確拉格朗日函式的作用：因為約束條件對定義域有著很大的限制，因此通過拉格朗日函式的形式去除優化問題的約束條件，取消約束限制對定義域的限制，讓優化問題更容易求解，那為什么這樣做有用呢？

我們可以這樣來看拉格朗日函式 $L(x,\lambda,v)=f_0(x)+\sum^m_{i=1}\lambda_i f_i(x) +\sum^p_{i=1}v_ih_i(x).$ ，其中由于約束條件 $h_i(x)=0$ 進而 $\sum^p_{i=1}v_ih_i(x) = 0$，并且如果 $\lambda_i \geq 0$ 且 $f_i(x)\leq 0$ 進而 $\sum^m_{i=1}\lambda_i f_i(x) \leq 0 $，也就是說 $L(x,\lambda,v) \leq f_0(x)$，

原問題是去尋找 $f_0(x)$ 的最小值，那么通過上述的分析，我們是不是可以找到 $L(x,\lambda,v)$ 的最小值去作為 $f_0(x)$ 的最小值呢？可以的，只不過稍微有點誤差而已，但是我們卻輕松地解決了帶約束問題的優化問題，

為此，為了減小這個誤差，我們進而又想找到 $L(x,\lambda,v)$ 的最小值中的最大值，也就有了 $g(\lambda,v)$，最重要的還是，無論原問題是否為凸問題，$g(\lambda,v)$ 都是一個凹函式，

上述稱為拉格朗日對偶問題，也稱原問題（primal problem），
對偶可行：滿足 $\lambda\succeq 0$ , $g(\lambda,v)>-\infty$ 稱為對偶可行的，
對偶最優解（最優拉格朗日乘子）：記 $(\lambda^*,v^*)$ 為對偶問題的最優解，
拉格朗日對偶問題是凸優化問題：因為目標函式是凹函式，約束集合是凸集，

另一方面，由于不論原函式是否為凸優化問題，新的問題都是凸的，因此可以方便求解，下面舉幾個例子，

[例子 1]：原問題為

$\begin{aligned} \text { minimize } \quad& x^Tx\\ \text { s.t. } \quad& Ax=b \end{aligned} \\$

那么可以很容易得到拉格朗日函式為 $L(x,\nu)=x^Tx+\nu^T(Ax-b)$，對偶函式為 $g(\nu)=-(1/4)\nu^TAA^T\nu-b^T\nu$，也即

$p^\star\ge g(\nu)$，

[例子 2]：標準形式的線性規劃(LP)

$\begin{aligned} \text { minimize } \quad& c^Tx\\ \text { s.t. } \quad& Ax=b,\quad x\succeq0 \end{aligned} \\$

按照定義容易得到對偶問題為

$\begin{aligned} \text { maximize } \quad& -b^T\nu\\ \text { s.t. } \quad& A^T\nu+c\succeq0 \end{aligned} \\$

[例子 3]：原問題為最小化范數

$\begin{aligned} \text { minimize } \quad& \Vert x\Vert\\ \text { s.t. } \quad& Ax=b \end{aligned} \\$

對偶函式為

$g(\nu)=\inf_{x} (\Vert x\Vert+\nu^T(b-Ax)) =\begin{cases}b^T\nu & \Vert A^T\nu\Vert_* \le1 \\ -\infty & o.w.\end{cases} \\$

這個推導程序中用到了共軛函式的知識，實際上上面三個例子都是線性等式約束，這種情況下，我們應用定義推導程序中可以很容易聯想到共軛函式，（實際上加上線性不等式約束也可以）

[例子 4]：(原問題非凸)考慮 Two-way partitioning (不知道怎么翻譯了...)

$\begin{aligned} \text { minimize } \quad& x^TWx\\ \text { s.t. } \quad& x_i^2=1,\quad i=1,...,n \end{aligned} \\$

對偶函式為

$\begin{aligned} g(\nu)=\inf_{x}\left( x^{T}(W+\operatorname{diag}(\nu)) x \right)-\mathbf{1}^{T} \nu =\left\{\begin{array}{ll} -\mathbf{1}^{T} \nu & W+\operatorname{diag}(\nu) \succeq 0 \\ -\infty & \text { otherwise } \end{array}\right. \end{aligned} \\$

于是可以給出原問題最優解的下界為 $p^\star\ge-\mathbf{1}^{T} \nu$ if $W+\operatorname{diag}(\nu) \succeq 0$，這個下界是不平凡的，比如可以取 $\nu=-\lambda_{\min}(W)\mathbf{1}$，可以給出 $p^\star\ge n\lambda_{\min}(W)$，

注：弱強對偶的區別，簡單點說，就是我們從對偶函式 $g(\lambda,v)$ 找到的最大值是否為原函式 $f_0(x)$ 的最優解，也就是通過對偶問題求解之后，對偶問題的解和真實問題的解有沒有誤差

[弱對偶性] 對偶問題的最優值記為 $d^{*}$ , 是從對偶函式中得到的 $p^{*}$ 的最優下界，因此不等式

$d^{*}\leq p^{*}$ 成立即使最初問題不是凸的，這個性質稱為弱對偶性，

最優對偶間隙： $p^{*}-d^{*}$

[強對偶性] 如果等式 $d^{*}=p^{*}$ 成立，即最優對偶間隙為零，那么強對偶性成立，注：如果原問題為凸優化問題，一般情況下都成立，

強對偶性成立的條件：約束準則（constraint qualifications）

[Slater's constraint qualifications(SCQ)條件] 存在 $x\in relint~D$ （relint指相對內部）使得 $f_i(x)<0, i=1,...,m$ ， $Ax=b.$

注：Slater 條件，如果簡單說，就是看 $f_i(x) \lt 0$ 是否嚴格滿足

這樣的點稱為嚴格可行點，
Slater定理說明如果Slater 條件成立（且原始問題是凸問題），那么強對偶性成立，
由于存在線性等式約束，因此實際定義域可能不存在內點，可以將這一條件放松為相對內點 $x\in\text{relint}\mathcal{D}$；
如果不等式約束中存在線性不等式，那么他也不必嚴格小于0，也即如果 $f_i(x)=C^Tx+d$，則只需要滿足 $f_i(x)\le0$ 即可，

三、強弱對偶的幾何解釋

[弱對偶性] 令集合 $\mathcal{G}$ 是目標函式和約束函式的值的集合

注：看下面圖片去理解的時候，需要注意，圖片的陰影面積是目標函式和約束函式的值的集合，是一個集合，然后通過下面的敘述，就是從集合中找到一個支撐超平面，然后注意一些限制條件，比如$u\preceq 0$，就可以看出$p^*$ 為什么是在那里了

$\mathcal{G}=\{(f_1(x),...,f_m(x),h_1(x),...,h_p(x),f_0(x) )\in R^m\times R^p\times R| x\in D\}$

$p^{*}=inf\{t| (u,v,t)\in \mathcal{G},u\preceq 0, v=0 \}$

為了得到關于 $(\lambda,\mathcal{v})$ 的對偶函式，我們最小化仿射函式： $(u,v,t)\in \mathcal{G},$

$(\lambda,\mathcal{v},1)^T(u,v,t)=\sum^m_{i=1}\lambda_i u_i +\sum^p_{i=1}\mathcal{v}_iv_i+t$

即對偶函式為：

$g(\lambda,\mathcal{v})=inf\{(\lambda,\mathcal{v},1)^T(u,v,t)|(u,v,t)\in \mathcal{G}\}$

如果下確界是有限的，那么

$(\lambda,\mathcal{v},1)^T(u,v,t)\geq g(\lambda,\mathcal{v})$

這定義了一個 $\mathcal{G}$ 的支撐超平面（以 $(\lambda,\mathcal{v},1)$ 為法向量且與 $\mathcal{G}$ 在下方相切），它是非垂直的，

假設 $\lambda\succeq 0$ ，如果 $u\preceq 0$ 且 $v=0$ ，那么 $t\geq (\lambda,\mathcal{v},1)^T(u,v,t).$ 因此，

$p^*\geq g(\lambda,\mathcal{v}).$

即得到了弱對偶性，

如圖1，對于 $\mathcal{G}=\{(f_1(x),f_0(x))|x\in D\}$ ，給定一個 $\lambda$ ，然后在 $\mathcal{G}$ 范圍內最小化 $(\lambda,1)^T(u,t)$ ，得到一個斜率為 $-\lambda$ 的支撐超平面 $t=-\lambda u+g(\lambda)$ ， $g(\lambda)$ 位于 $p^{*}$ 的下方，注：由于 $g(\lambda) = t + \lambda u$，可以得知 $g(\lambda)$ 就是 $t$ 軸的交點，也就相當于截距，
為了最大化 $g(\lambda)$ ，給 $\lambda$ 取不同的值, 如圖2，即使是最優的 $\lambda^{*}$ ，給出的 $d^{*}$ 也在 $p^{*}$ 的下方，所以不滿足強對偶性，只有弱對偶性，注：可以把這看成是一個迭代的程序

注：再次講講 $p^*$ 的來源，那么 $p^\star$ 體現在哪個點呢？由于對于原優化問題，我們有 $f_1(x)\le0$，因此體現在這個圖里面就是 $u\le0$，也就是上面左圖當中的紅色區域，而 $p^\star=\min f_0(x)=\min t$，

[弱對偶性的證明]：我們有 $\lambda\ge0$

$\begin{aligned} p^\star &= \inf\{t|(u,v,t)\in\mathcal{G},u\le0,v=0\} \\ &\ge \inf\{t+\lambda^Tu+\mu^Tv|(u,v,t)\in\mathcal{G},u\le0,v=0\} \\ &\ge \inf\{t+\lambda^Tu+\mu^Tv|(u,v,t)\in\mathcal{G}\} \\ &= g(\lambda,\mu) \end{aligned} \\$

[強對偶性條件 Slater’s constraint quali?cation(SCQ) 的證明]：由 $g(\lambda,\mu)=\inf_{(u,v,t)\in\mathcal{G}}(t+\lambda^T u+\mu^Tv)$ 可以得到

$(\lambda,\mu,1)^T(u,v,t)\ge g(\lambda,\mu),\quad \forall (u,v,t)\in\mathcal{G} \\$

這實際上定義了 $\mathcal{G}$ 的一個超平面，特別的有 $(0,0,p^\star)\in\text{bd}\mathcal{G}$，因此也有

$(\lambda,\mu,1)^T(0,0,p^\star)\ge g(\lambda,\mu) \\$

這個不等式可以自然地匯出弱對偶性，當“=”成立時則可以匯出強對偶性，那么什么時候取等號呢？點 $(0,0,p^\star)$ 為支撐點的時候！也就是說

如果在邊界點 $(0,0,p^\star)$ 處存在一個非豎直的支撐超平面，那么我們就可以找到 $\lambda,\mu$ 使得上面的等號成立，也就是得到了強對偶性，

注意前面的分析中我們并沒有提到 SCQ，那么 SCQ 是如何保證強對偶性的呢？注意 SCQ 要求存在 $x\in\mathcal{D}$ 使得 $f(x)<0$，這也就意味著 $\mathcal{G}$ 在 $u< 0$ 半平面上有點，因此如果支撐超平面存在的話，就一定不是垂直的，

但這又引出另一個問題，那就是支撐超平面一定存在嗎？答案是一定存在，這是由原問題的凸性質決定的，為了證明這一點，我們可以引入一個類似于 epigraph 的概念：

$\begin{aligned} \mathcal{A} &= \mathcal{G} + (R^m_+\times \{0\}\times R_+) \\ &= \left\{(u,v,t) |\ \exists x\in\mathcal{D},s.t. f(x)\le u,h(x)=v,f_0(x)\le t\right\} \end{aligned} \\$

由于原優化問題為凸的，可以應用定義證明集合 $\mathcal{A}$ 也是凸的，同時 $(0,0,p^\star)\in\text{bd}\mathcal{A}$，那么集合 $\mathcal{A}$ 在 $(0,0,p^\star)$ 點就一定存在一個支撐超平面，又由 SCQ 可知這個支撐超平面一定不是豎直的，因此就可以得到強對偶性了，

注：$(\lambda,\mu,1)^T(u,v,t)\ge g(\lambda,\mu),\quad \forall (u,v,t)\in\mathcal{A}$ 也成立，

注：說實話，這里我也有點半知半解，數學公式看的太亂了，反正要注意，$u$ 相當于 $f_i(x)$，$v$ 相當于 $h_i(x)$，我只能說說我淺顯的理解，就是從圖中看，確保坐標軸 $u$ 的負半軸有一個支撐超平面，且這個支撐超平面不是垂直的，那么 $p^* \geq d^*$ 就被保證了，

四、鞍點解釋

4.1 鞍點的基礎定義

[鞍點定義]：一個不是區域最小值的駐點（一階導數為0的點）稱為鞍點，注：鞍點的數學含義是——目標函式在此點上的梯度（一階導數）值為 0，但從該點出發的一個方向是函式的極大值點，而在另一個方向是函式的極小值點，

[判斷鞍點的一個充分條件]：函式在一階導數為零處（駐點）的黑塞矩陣為不定矩陣（特征值有正有負的矩陣為不定矩陣），

下面對函式 $z=x^2-y^2$ 的駐點 $(0,0)$ 判斷是否為鞍點，函式影像如下（紅點為影像的鞍點)：

我們根據定義來判斷 $(0,0)$ 點的 Hessian 矩陣：

我們容易求得二元函式 $z=x^2?y^2$ 在駐點 $ (0,0) $ 處的 Hessian 矩陣形式為：

容易解出特征值一個為 $2$，一個為 $-2$（有正有負），顯然是不定矩陣，所以該點是鞍點，

注：函式在一階導數為零處（駐點）的 Hessian 矩陣為不定矩陣只是判斷該點是否為鞍點的充分條件，也就是說函式在一階導數為零處（駐點）的 Hessian 矩陣不滿足不定矩陣的定義，也不一定能夠說明它不是鞍點，比如在 $z=x^4?y^4$ 點 $ (0,0)$ 處的 Hessian 矩陣是一個 0 矩陣,并不滿足是不定矩陣，但是它是一個鞍點，

4.2 極大極小不等式和鞍點性質

[極大極小不等式]：對任意 $f$ ：$R^n × R^m \rightarrow R,\quad W \subseteq R^n Z \subseteq R^m$，有

\[\underset{z\in Z}{sup}\,\underset{w\in W}{inf}\,f(w,z) \leq \underset{w\in W}{inf} \, \underset{z\in Z}{sup}\,f(w,z) \]

對于上述這個不等式一般稱為極大極小不等式，如果等式成立，即

\[\underset{z\in Z}{sup}\,\underset{w\in W}{inf}\,f(w,z) = \underset{w\in W}{inf} \, \underset{z\in Z}{sup}\,f(w,z) \]

則稱 $f$（以及 $W$ 和 $Z$）滿足強極大極小性質或者鞍點性質，

[鞍點性質]：注：這個解釋更多的是為了下面講述 KKT 條件，其實就是注意下這個強極大極小性質就是鞍點性質

我們稱一對 $\hat w \in W, \hat z \in Z$ 是函式 $f$ （以及 $W$ 和 $Z$）的鞍點，如果對任意的 $w \in W$ 和 $z \in Z$ 下式成立：

\[f(\hat w,z) \leq f(\hat w \hat z) \leq f(w, \hat z) \]

也就是說，$f(x,\hat z)$ 在 $\hat w$ 處取得最小值（關于變數 $w\in W$），$f(\hat w, z)$ 在 $\hat z$ 處取得最大值（關于變數 $z \in Z$）:

\[f(\hat w, \hat z) = \inf_{w\in W} f(w, \hat z), \quad f(\hat w, \hat z) = \sup_{z \in Z} f(\hat w, z) \]

該式滿足強極大極小性質，且共同值為 $f(\hat w, \hat z)$，也就是上述說的，$\hat w$ 和 $\hat z$ 為 $f$ 的鞍點，

五、最優性條件與 KKT 條件

5.1 KKT 條件

我們首先回顧一下拉格朗日函式，考慮下面的優化問題

$\begin{aligned} \text { minimize } \quad& f_{0}(x)\\ \text { s.t. } \quad& f_{i}(x) \leq 0, \quad i=1, \ldots, m\\ &h_{i}(x)=0, \quad i=1, \ldots, p \end{aligned} \\$

那么他的拉格朗日函式就是

$L(x,\lambda,\nu)=f_0(x)+\lambda^Tf(x)+\nu^Th(x) \\$

首先，我們看對偶函式

$g(\lambda,\nu)=\inf_{x\in\mathcal{D}}\left(f_0(x)+\lambda^Tf(x)+\nu^Th(x)\right) \\$

對偶問題實際上就是

$d^\star = \sup_{\lambda,\nu}g(\lambda,\nu)=\sup_{\lambda,\nu}\inf_x L(x,\lambda,\nu) \\$

然后我們再看原問題，由于 $\lambda\succeq0,f(x)\preceq0$，我們有

$f_0(x)=\sup_{\lambda,\nu}L(x,\lambda,\nu) \\$

原問題的最優解實際上就是

$p^\star=\inf_x f_0(x)= \inf_x \sup_{\lambda,\nu}L(x,\lambda,\nu) \\$

弱對偶性 $p^\star \ge d^\star$ 實際上說的是什么呢？就是 max-min 不等式

$\inf_x \sup_{\lambda,\nu}L(x,\lambda,\nu) \ge \sup_{\lambda,\nu}\inf_x L(x,\lambda,\nu) \\$

強對偶性說的又是什么呢？就是上面能夠取等號

$\inf_x \sup_{\lambda,\nu}L(x,\lambda,\nu) = \sup_{\lambda,\nu}\inf_x L(x,\lambda,\nu) = L({x}^\star,{\lambda}^\star,{\nu}^\star) \\$

注：實際上 ${x}^\star,{\lambda}^\star,{\nu}^\star$ 就是拉格朗日函式的鞍點！！！（數學家們真實太聰明了！！！妙啊！！！）那么也就是說強對偶性成立等價于拉格朗日函式存在鞍點(在定義域內)，

好，如果存在鞍點（一階導為 0）的話，我們怎么求解呢？還是看上面取等的式子

$\begin{aligned} f_0({x}^\star) = g(\lambda^\star,\nu^\star) &= \inf_x \left( f_0(x)+\lambda^{\star T}f(x)+\nu^{\star T}h(x) \right) \\ & \le f_0(x^\star)+\lambda^{\star T}f(x^\star)+\nu^{\star T}h(x^\star) \\ & \le f_0(x^\star) \end{aligned} \\$

這兩個不等號必須要取到等號，而第一個不等號取等條件應為（鞍點一階導為 0）

$\nabla_x \left( f_0(x)+\lambda^{\star T}f(x)+\nu^{\star T}h(x) \right) =0 \\$

第二個不等號取等條件為（這個條件成立，等號才能取到）

$\lambda^\star_i f_i(x^\star)=0,\forall i \\$

同時，由于 ${x}^\star,{\lambda}^\star,{\nu}^\star$ 還必須位于定義域內，需要滿足約束條件，因此上面的幾個條件共同構成了 KKT 條件，

KKT 條件

原始約束 $f_i(x)\le0,i=1,...,m, \quad h_i(x)=0,i=1,...,p$
對偶約束 $\lambda\succeq0$
互補性條件(complementary slackness) $\lambda_i f_i(x)=0,i=1,...,m$
梯度條件

$\nabla f_{0}(x)+\sum_{i=1}^{m} \lambda_{i} \nabla f_{i}(x)+\sum_{i=1}^{p} \nu_{i} \nabla h_{i}(x)=0 \\$

5.2 KKT 條件與凸問題

Remarks(重要結論)

前面推導沒有任何凸函式的假設，因此不論是否為凸問題，如果滿足強對偶性，那么最優解一定滿足 KKT 條件，
但是反過來不一定成立，也即 KKT 條件的解不一定是最優解，因為如果 $L(x,\lambda^\star,\nu^\star)$ 不是凸的，那么 $\nabla_x L=0$ 并不能保證 $g(\lambda^\star,\nu^\star)=\inf_x L(x,\lambda^\star,\nu^\star)\ne L(x^\star,\lambda^\star,\nu^\star)$，也即不能保證 ${x}^\star,{\lambda}^\star,{\nu}^\star$ 就是鞍點，

但是如果我們假設原問題為凸問題的話，那么 $L(x,\lambda^\star,\nu^\star)$ 就是一個凸函式，由梯度條件 $\nabla_x L=0$ 我們就能得到 $g(\lambda^\star,\nu^\star)=L(x^\star,\lambda^\star,\nu^\star)=\inf_x L(x,\lambda^\star,\nu^\star)$，另一方面根據互補性條件我們有此時 $f_0(x^\star)=L(x^\star,\lambda^\star,\nu^\star)$，因此我們可以得到一個結論

Remarks(重要結論)：

考慮原問題為凸的，那么若 KKT 條件有解 $\tilde{x},\tilde{\lambda},\tilde{\nu}$，則原問題一定滿足強對偶性，且他們就對應原問題和對偶問題的最優解，
但是需要注意的是，KKT 條件可能無解！此時就意味著原問題不滿足強對偶性！

假如我們考慮上一節提到的 SCQ 條件，如果凸優化問題滿足 SCQ 條件，則意味著強對偶性成立，則此時有結論

Remarks(重要結論)：
如果 SCQ 滿足，那么 $x$ 為最優解當且僅當存在 $\lambda,\nu$ 滿足 KKT 條件！

[例子 1]：等式約束的二次優化問題 $P\in S_+^n$

$\begin{aligned} \text { minimize } \quad& (1/2)x^TPx+q^Tx+r \\ \text { s.t. } \quad& Ax=b \end{aligned} \\$

那么經過簡單計算就可以得到 KKT 條件為

$\left[\begin{array}{cc} P & A^{T} \\ A & 0 \end{array}\right]\left[\begin{array}{l} x^{\star} \\ \nu^{\star} \end{array}\right]=\left[\begin{array}{c} -q \\ b \end{array}\right] \\$

5.3 互補松弛性

假設原問題和對偶問題的最優值都可以達到且相等，令 $x^*$ 是原問題的最優解， $(\lambda^*, \nu^*)$ 是對偶問題的最優解，這表明，

$\begin{align} f_0(x^*) &= g(\lambda^*, \nu^*) \\ & = \inf_{x} \Big(f_0(x) + \sum_{i=1}^m \lambda_i^* f_i(x) + \sum_{i=1}^p \nu_i^* h_i(x)\Big) \\ &\leq f_0(x^*) + \sum_{i=1}^m \lambda_i^* f_i(x^*) + \sum_{i=1}^p \nu_i^* h_i(x^*)\\ &\leq f_0(x^*) \end{align} \tag{8}$

其中第一個等式是因為強對偶的定義，第二個等式是Lagrange函式的定義，第三個不等式是根據Lagrange函式關于 $x$ 求下確界小于等于其在 $x^*$ 處的值(請確保你理解這個不等式)，最后一個不等式是因為 $\lambda_i^* \ge0, f_i(x^*) \leq 0, i = 1, \cdots, m$ 以及 $h_i(x^*) = 0, i =1, \cdots, p$ ，因此，在上面的式子鏈中，兩個不等式取等號，

由于第三個不等式可以取等式，這里有一個重要的結論：

$\sum_{i=1}^m \lambda_i^* f_i(x^*) = 0 \\$

事實上，求和的每一項都非正，因此有：

$\lambda_i^* f(x_i^*) = 0 \quad i = 1, \cdots, m \\$

所以，

$\lambda_i^* > 0 \Rightarrow f_i(x^*) = 0 \\ f_i(x_i^*) < 0 \Rightarrow \lambda_i^* = 0$

注：這表明在最優點處，原問題的不等式起作用時，對于的Lagrange問題的對應的不等式不起作用，反之亦然，

六、擾動及靈敏度分析

6.1 擾動問題

注：擾動其實就是約束條件多了點限制

現在我們再回到原始問題

$\begin{aligned} \text { minimize } \quad& f_{0}(x)\\ \text { s.t. } \quad& f_{i}(x) \leq 0, \quad i=1, \ldots, m\\ &h_{i}(x)=0, \quad i=1, \ldots, p \end{aligned} \\$

我們引入了對偶函式 $g(\lambda,\nu)$，那這兩個引數 $\lambda,\nu$ 有什么含義嗎？假如我們把原問題放松一下

$\begin{aligned} \text { minimize } \quad& f_{0}(x)\\ \text { s.t. } \quad& f_{i}(x) \leq u_i, \quad i=1, \ldots, m\\ &h_{i}(x)=v_i, \quad i=1, \ldots, p \end{aligned} \\$

記最優解為 $p^\star(u,v)=\min f_0(x)$，現在對偶問題變成了

$\begin{aligned} \max \quad& g(\lambda,\nu)-u^T\lambda -v^T\nu\\ \text{s.t.} \quad& \lambda\succeq0 \end{aligned} \\$

假如說原始對偶問題的最優解為 $\lambda^\star,\nu^\star$，松弛后的對偶問題最優解為 $\tilde{\lambda},\tilde{\nu}$，那么根據弱對偶性原理，有

$\begin{aligned} p^\star(u,v) &\ge g(\tilde\lambda,\tilde\nu)-u^T\tilde\lambda -v^T\tilde\nu \\ &\ge g(\lambda^\star,\nu^\star)-u^{T}\lambda^\star -v^{T}\nu^\star \\ &= p^\star(0,0) - u^{T}\lambda^\star -v^{T}\nu^\star \end{aligned} \\$

這像不像關于 $u,v$ 的一階近似？太像了！實際上，我們有

$\lambda_{i}^{\star}=-\frac{\partial p^{\star}(0,0)}{\partial u_{i}}, \quad \nu_{i}^{\star}=-\frac{\partial p^{\star}(0,0)}{\partial v_{i}} \\$

6.2 靈敏度分析

注：細節我也沒認真看，其實看看下述給出的靈敏度解釋，也就是大概知道擾動會對結果造成什么影響就行了

如果$\lambda_i^*$比較大，加強第i個約束，即$u_i< 0$，則最優值$P^*(u,l)$會大幅增加，
如果$\lambda_i^*$比較小，放松第i個約束，即$u_i> 0$，則最優值$P^*(u,l)$不會減小太多，
如果$v_i^*$比較大且大于0，$l_i< 0]$，或者如果$v_i^*$比較大且小于0，$l_i> 0$，則最優值$P^*(u,l)$會大幅增加，
如果$v_i^*$比較小且大于0，$l_i> 0$，或者如果$v_i^*$比較大且小于0，$l_i< 0$，則最優值$P^*(u,l)$不會減少太多，

七、Reformulation

前面將凸優化問題的時候，我們提到了Reformulation的幾個方法來簡化原始問題，比如消去等式約束，添加等式約束，添加松弛變數，epigraph等等，現在當我們學習了對偶問題，再來重新看一下這些方法，

7.1 引入等式約束

[例子 1】：考慮無約束優化問題 $\min f(Ax+b)$，他的對偶問題跟原問題是一樣的，如果我們引入等式約束，原問題和對偶問題變為

$\begin{aligned} \text{minimize} \quad& f_{0}(y) \quad \\ \text{s.t.} \quad& A x+b-y=0 \end{aligned} \quad\qquad \begin{aligned} \text{minimize} \quad& b^{T} \nu-f_{0}^{*}(\nu) \\ \text{s.t.} \quad& A^{T} \nu=0 \end{aligned} \\$

[例子 2]：考慮無約束優化 $\min \Vert Ax-b\Vert$，類似的引入等式約束后，對偶問題變為

$\begin{aligned} \text{minimize} \quad& b^{T} \nu \\ \text{s.t.} \quad& A^{T} \nu=0,\quad \Vert\nu\Vert_*\le1 \end{aligned} \\$

7.2 顯示約束與隱式約束的相互轉化

[例子 3]：考慮原問題如下，可以看出來對偶問題非常復雜

$\begin{aligned} \text{minimize} \quad& c^{T} x \\ \text{s.t.} \quad& A x=b \\ \quad& -1 \preceq x \preceq 1 \end{aligned} \begin{aligned} \text{maximize} \quad& -b^{T} \nu-\mathbf{1}^{T} \lambda_{1}-\mathbf{1}^{T} \lambda_{2} \\ \text{s.t.} \quad& c+A^{T} \nu+\lambda_{1}-\lambda_{2}=0 \\ \quad& \lambda_{1} \succeq 0, \quad \lambda_{2} \succeq 0 \end{aligned} \\$

如果我們原問題的不等式約束條件轉化為隱式約束，則有

$\begin{aligned} \text{minimize} \quad& f_{0}(x)=\left\{\begin{array}{ll}c^{T} x & \Vert x\Vert_\infty \preceq 1 \\ \infty & \text { otherwise }\end{array}\right. \\ \text{s.t.} \quad& A x=b \end{aligned} \\$

然后對偶問題就可以轉化為無約束優化問題

$\text{maximize} -b^T\nu-\Vert A^T\nu +c\Vert_1 \\$

7.3 轉化目標函式與約束函式

[例子 4]：還考慮上面提到的無約束優化問題 $\min \Vert Ax-b\Vert$，我們可以把目標函式平方一下，得到

$\begin{aligned} \text{minimize} \quad& (1/2)\Vert y\Vert^2 \\ \text{s.t.} \quad& Ax-b=y \end{aligned} \\$

然后對偶問題就可以轉化為

$\begin{aligned} \text{minimize} \quad& (1/2)\Vert \nu\Vert_*^2+ b^T\nu \\ \text{s.t.} \quad& A^T\nu=0 \end{aligned} \\$

參考文獻：Stephen Boyd, Lieven Vandenberghe: Convex Optimization

參考資料：https://www.zhihu.com/column/c_1174389256402771968

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/288208.html

標籤：其他

上一篇：你不可不會的幾種移動零的方法

下一篇：什么是人工智能？你需要知道的關于人工智能的一切