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

2021 年 6 月 20 日
筆記
凸優化從入門到放棄

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

一、拉格朗日對偶函數
二、拉格朗日對偶問題
三、強弱對偶的幾何解釋
四、鞍點解釋
- 4.1 鞍點的基礎定義
- 4.2 極大極小不等式和鞍點性質
五、最優性條件與 KKT 條件
- 5.1 KKT 條件
- 5.2 KKT 條件與凸問題
六、擾動及靈敏度分析
- 6.1 擾動問題
- 6.2 靈敏度分析
七、Reformulation

凸優化從入門到放棄完整教程地址：//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] \\$

六、擾動及靈敏度分析

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

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

Tags: 凸優化從入門到放棄