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

一、拉格朗日對偶函數

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

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

• 其中 (xin R^n) ，設值域 (D=cap^m_{i=0}dom~f_icap^p_{i=1}dom~h_i) 不為空。
• 最優值記為 (p^*) ，不假設這個問題是凸的。
• 拉格朗日對偶：通過添加限制的權重和來增廣目标函數。

[拉格朗日函數] 定義拉格朗日函數 (L: R^n imes R^m imes R^p

ightarrow 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 imes R^m imes R^p.)
• 拉格朗日乘子：記 (lambda_i) 是第 (i) 個不等式限制 (f_i(x)leq 0) 的拉格朗日乘子； (v_i) 是第 (i) 個等式限制 (h_i(x)=0) 的拉格朗日乘子。
• 乘子向量：向量 (lambda) 和 (v) 稱為對偶變量，或該問題的拉格朗日乘子向量。

[拉格朗日對偶函數] 定義拉格朗日對偶函數（或對偶函數） (g:R^m imes R^p

ightarrow R) 為拉格朗日函數關于 (x) 取得的最小值：對于 (lambdain R^m, vin R^p)

(g(lambda,v)=inf_{xin D} L(x,lambda,v))

注：上面為什麼用 (inf) 這個函數，因為解可能是趨向于一個值，而不是一個具體的值

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

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

二、拉格朗日對偶問題

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

(egin{aligned} ext{maxmize} quad &g(lambda,v) \

ext{s.t.} quad & lambdasucceq 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）。
• 對偶可行：滿足 (lambdasucceq 0) , (g(lambda,v)>-infty) 稱為對偶可行的。
• 對偶最優解（最優拉格朗日乘子）：記 ((lambda^*,v^*)) 為對偶問題的最優解。
• 拉格朗日對偶問題是凸優化問題：因為目标函數是凹函數，限制集合是凸集。

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

[例子 1]：原問題為

(egin{aligned} ext { minimize } quad& x^Tx\ ext { s.t. } quad& Ax=b end{aligned} \)

那麼可以很容易得到拉格朗日函數為 (L(x,

u)=x^Tx+

u^T(Ax-b))，對偶函數為 (g(

u)=-(1/4)

u^TAA^T

u-b^T

u)，也即

(p^starge g(

u))。

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

(egin{aligned} ext { minimize } quad& c^Tx\ ext { s.t. } quad& Ax=b,quad xsucceq0 end{aligned} \)

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

(egin{aligned} ext { maximize } quad& -b^T

u\ ext { s.t. } quad& A^T

u+csucceq0 end{aligned} \)

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

(egin{aligned} ext { minimize } quad& Vert xVert\ ext { s.t. } quad& Ax=b end{aligned} \)

對偶函數為

(g(

u)=inf_{x} (Vert xVert+

u^T(b-Ax)) =egin{cases}b^T

u & Vert A^T

uVert_* le1 \ -infty & o.w.end{cases} \)

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

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

(egin{aligned} ext { minimize } quad& x^TWx\ ext { s.t. } quad& x_i^2=1,quad i=1,...,n end{aligned} \)

對偶函數為

(egin{aligned} g(

u)=inf_{x}left( x^{T}(W+operatorname{diag}(

u)) x

ight)-mathbf{1}^{T}

u =left{egin{array}{ll} -mathbf{1}^{T}

u & W+operatorname{diag}(

u) succeq 0 \ -infty & ext { otherwise } end{array}

ight. end{aligned} \)

于是可以給出原問題最優解的下界為 (p^starge-mathbf{1}^{T}

u) if (W+operatorname{diag}(

u) succeq 0)。這個下界是不平凡的，比如可以取 (

u=-lambda_{min}(W)mathbf{1})，可以給出 (p^starge nlambda_{min}(W))。

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

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

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

• 最優對偶間隙： (p^{*}-d^{*})

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

• 強對偶性成立的條件：限制準則（constraint qualifications）

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

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

• 這樣的點稱為嚴格可行點。
• Slater定理說明如果Slater 條件成立（且原始問題是凸問題），那麼強對偶性成立。
• 由于存線上性等式限制，是以實際定義域可能不存在内點，可以将這一條件放松為相對内點 (xin ext{relint}mathcal{D})；
• 如果不等式限制中存線上性不等式，那麼他也不必嚴格小于0。也即如果 (f_i(x)=C^Tx+d)，則隻需要滿足 (f_i(x)le0) 即可。

三、強弱對偶的幾何解釋

[弱對偶性] 令集合 (mathcal{G}) 是目标函數和限制函數的值的集合

注：看下面圖檔去了解的時候，需要注意，圖檔的陰影面積是目标函數和限制函數的值的集合，是一個集合，然後通過下面的叙述，就是從集合中找到一個支撐超平面，然後注意一些限制條件，比如(upreceq 0)， 就可以看出(p^*) 為什麼是在那裡了

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

(p^{*}=inf{t| (u,v,t)in mathcal{G},upreceq 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}) 在下方相切）。它是非垂直的。

假設 (lambdasucceq 0) ，如果 (upreceq 0) 且 (v=0) ，那麼 (tgeq (lambda,mathcal{v},1)^T(u,v,t).) 是以，

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

即得到了弱對偶性。

• 如圖1，對于 (mathcal{G}={(f_1(x),f_0(x))|xin 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)，是以展現在這個圖裡面就是 (ule0)，也就是上面左圖當中的紅色區域，而 (p^star=min f_0(x)=min t)。

[弱對偶性的證明]：我們有 (lambdage0)

(egin{aligned} p^star &= inf{t|(u,v,t)inmathcal{G},ule0,v=0} \ &ge inf{t+lambda^Tu+mu^Tv|(u,v,t)inmathcal{G},ule0,v=0} \ &ge inf{t+lambda^Tu+mu^Tv|(u,v,t)inmathcal{G}} \ &= g(lambda,mu) end{aligned} \)

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

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

這實際上定義了 (mathcal{G}) 的一個超平面。特别的有 ((0,0,p^star)in ext{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 要求存在 (xinmathcal{D}) 使得 (f(x)<0)，這也就意味着 (mathcal{G}) 在 (u< 0) 半平面上有點，是以如果支撐超平面存在的話，就一定不是垂直的。

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

(egin{aligned} mathcal{A} &= mathcal{G} + (R^m_+ imes {0} imes R_+) \ &= left{(u,v,t) | exists xinmathcal{D},s.t. f(x)le u,h(x)=v,f_0(x)le t

ight} end{aligned} \)

由于原優化問題為凸的，可以應用定義證明集合 (mathcal{A}) 也是凸的，同時 ((0,0,p^star)in ext{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)inmathcal{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

ightarrow R,quad W subseteq R^n Z subseteq R^m)，有

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

]

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

[underset{zin Z}{sup}\,underset{win W}{inf}\,f(w,z) = underset{win W}{inf} \, underset{zin 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) 處取得最小值（關于變量 (win W)），(f(hat w, z)) 在 (hat z) 處取得最大值（關于變量 (z in Z)）:

[f(hat w, hat z) = inf_{win 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 條件

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

(egin{aligned} ext { minimize } quad& f_{0}(x)\ ext { 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,

u)=f_0(x)+lambda^Tf(x)+

u^Th(x) \)

首先，我們看對偶函數

(g(lambda,

u)=inf_{xinmathcal{D}}left(f_0(x)+lambda^Tf(x)+

u^Th(x)

ight) \)

對偶問題實際上就是

(d^star = sup_{lambda,

u}g(lambda,

u)=sup_{lambda,

u}inf_x L(x,lambda,

u) \)

然後我們再看原問題，由于 (lambdasucceq0,f(x)preceq0)，我們有

(f_0(x)=sup_{lambda,

u}L(x,lambda,

u) \)

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

(p^star=inf_x f_0(x)= inf_x sup_{lambda,

u}L(x,lambda,

u) \)

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

(inf_x sup_{lambda,

u}L(x,lambda,

u) ge sup_{lambda,

u}inf_x L(x,lambda,

u) \)

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

(inf_x sup_{lambda,

u}L(x,lambda,

u) = sup_{lambda,

u}inf_x L(x,lambda,

u) = L({x}^star,{lambda}^star,{

u}^star) \)

注：實際上 ({x}^star,{lambda}^star,{

u}^star) 就是拉格朗日函數的鞍點！！！（數學家們真實太聰明了！！！妙啊！！！）那麼也就是說強對偶性成立等價于拉格朗日函數存在鞍點(在定義域内)。

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

(egin{aligned} f_0({x}^star) = g(lambda^star,

u^star) &= inf_x left( f_0(x)+lambda^{star T}f(x)+

u^{star T}h(x)

ight) \ & le f_0(x^star)+lambda^{star T}f(x^star)+

u^{star T}h(x^star) \ & le f_0(x^star) end{aligned} \)

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

(

abla_x left( f_0(x)+lambda^{star T}f(x)+

u^{star T}h(x)

ight) =0 \)

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

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

同時，由于 ({x}^star,{lambda}^star,{

u}^star) 還必須位于定義域内，需要滿足限制條件，是以上面的幾個條件共同構成了 KKT 條件。

KKT 條件

1. 原始限制 (f_i(x)le0,i=1,...,m, quad h_i(x)=0,i=1,...,p)
2. 對偶限制 (lambdasucceq0)
3. 互補性條件(complementary slackness) (lambda_i f_i(x)=0,i=1,...,m)
4. 梯度條件

(

abla f_{0}(x)+sum_{i=1}^{m} lambda_{i}

abla f_{i}(x)+sum_{i=1}^{p}

u_{i}

abla h_{i}(x)=0 \)

5.2 KKT 條件與凸問題

Remarks(重要結論)

1. 前面推導沒有任何凸函數的假設，是以不論是否為凸問題，如果滿足強對偶性，那麼最優解一定滿足 KKT 條件。

2. 但是反過來不一定成立，也即 KKT 條件的解不一定是最優解，因為如果 (L(x,lambda^star,

   u^star)) 不是凸的，那麼 (

   abla_x L=0) 并不能保證 (g(lambda^star,

   u^star)=inf_x L(x,lambda^star,

   u^star)

   e L(x^star,lambda^star,

   u^star))，也即不能保證 ({x}^star,{lambda}^star,{

   u}^star) 就是鞍點。

但是如果我們假設原問題為凸問題的話，那麼 (L(x,lambda^star,

u^star)) 就是一個凸函數，由梯度條件 (

abla_x L=0) 我們就能得到 (g(lambda^star,

u^star)=L(x^star,lambda^star,

u^star)=inf_x L(x,lambda^star,

u^star))，另一方面根據互補性條件我們有此時 (f_0(x^star)=L(x^star,lambda^star,

u^star))，是以我們可以得到一個結論

Remarks(重要結論)：

1. 考慮原問題為凸的，那麼若 KKT 條件有解 ( ilde{x}, ilde{lambda}, ilde{

   u})，則原問題一定滿足強對偶性，且他們就對應原問題和對偶問題的最優解。

2. 但是需要注意的是，KKT 條件可能無解！此時就意味着原問題不滿足強對偶性！

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

Remarks(重要結論)：

如果 SCQ 滿足，那麼 (x) 為最優解當且僅當存在 (lambda,

u) 滿足 KKT 條件！

[例子 1]：等式限制的二次優化問題 (Pin S_+^n)

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

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

(left[egin{array}{cc} P & A^{T} \ A & 0 end{array}

ight]left[egin{array}{l} x^{star} \

u^{star} end{array}

ight]=left[egin{array}{c} -q \ b end{array}

ight] \)

5.3 互補松弛性

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

u^*)) 是對偶問題的最優解。這表明，

(egin{align} f_0(x^*) &= g(lambda^*,

u^*) \ & = inf_{x} Big(f_0(x) + sum_{i=1}^m lambda_i^* f_i(x) + sum_{i=1}^p

u_i^* h_i(x)Big) \ &leq f_0(x^*) + sum_{i=1}^m lambda_i^* f_i(x^*) + sum_{i=1}^p

u_i^* h_i(x^*)\ &leq f_0(x^*) end{align} ag{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 擾動問題

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

現在我們再回到原始問題

(egin{aligned} ext { minimize } quad& f_{0}(x)\ ext { 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,

u))，那這兩個參數 (lambda,

u) 有什麼含義嗎？假如我們把原問題放松一下

(egin{aligned} ext { minimize } quad& f_{0}(x)\ ext { 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))，現在對偶問題變成了

(egin{aligned} max quad& g(lambda,

u)-u^Tlambda -v^T

u\ ext{s.t.} quad& lambdasucceq0 end{aligned} \)

假如說原始對偶問題的最優解為 (lambda^star,

u^star)，松弛後的對偶問題最優解為 ( ilde{lambda}, ilde{

u})，那麼根據弱對偶性原理，有

(egin{aligned} p^star(u,v) &ge g( ildelambda, ilde

u)-u^T ildelambda -v^T ilde

u \ &ge g(lambda^star,

u^star)-u^{T}lambda^star -v^{T}

u^star \ &= p^star(0,0) - u^{T}lambda^star -v^{T}

u^star end{aligned} \)

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

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

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

6.2 靈敏度分析

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

1. 如果(lambda_i^*)比較大，加強第i個限制，即(u_i< 0)，則最優值(P^*(u,l))會大幅增加。
2. 如果(lambda_i^*)比較小，放松第i個限制，即(u_i> 0)，則最優值(P^*(u,l))不會減小太多。
3. 如果(v_i^*)比較大且大于0，(l_i< 0])，或者如果(v_i^*)比較大且小于0，(l_i> 0)，則最優值(P^*(u,l))會大幅增加。
4. 如果(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))，他的對偶問題跟原問題是一樣的。如果我們引入等式限制，原問題和對偶問題變為

(egin{aligned} ext{minimize} quad& f_{0}(y) quad \ ext{s.t.} quad& A x+b-y=0 end{aligned} quadqquad egin{aligned} ext{minimize} quad& b^{T}

u-f_{0}^{*}(

u) \ ext{s.t.} quad& A^{T}

u=0 end{aligned} \)

[例子 2]：考慮無限制優化 (min Vert Ax-bVert)，類似的引入等式限制後，對偶問題變為

(egin{aligned} ext{minimize} quad& b^{T}

u \ ext{s.t.} quad& A^{T}

u=0,quad Vert

uVert_*le1 end{aligned} \)

7.2 顯示限制與隐式限制的互相轉化

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

(egin{aligned} ext{minimize} quad& c^{T} x \ ext{s.t.} quad& A x=b \ quad& -1 preceq x preceq 1 end{aligned} egin{aligned} ext{maximize} quad& -b^{T}

u-mathbf{1}^{T} lambda_{1}-mathbf{1}^{T} lambda_{2} \ ext{s.t.} quad& c+A^{T}

u+lambda_{1}-lambda_{2}=0 \ quad& lambda_{1} succeq 0, quad lambda_{2} succeq 0 end{aligned} \)

如果我們原問題的不等式限制條件轉化為隐式限制，則有

(egin{aligned} ext{minimize} quad& f_{0}(x)=left{egin{array}{ll}c^{T} x & Vert xVert_infty preceq 1 \ infty & ext { otherwise }end{array}

ight. \ ext{s.t.} quad& A x=b end{aligned} \)

然後對偶問題就可以轉化為無限制優化問題

( ext{maximize} -b^T

u-Vert A^T

u +cVert_1 \)

7.3 轉化目标函數與限制函數

[例子 4]：還考慮上面提到的無限制優化問題 (min Vert Ax-bVert)，我們可以把目标函數平方一下，得到

(egin{aligned} ext{minimize} quad& (1/2)Vert yVert^2 \ ext{s.t.} quad& Ax-b=y end{aligned} \)

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

(egin{aligned} ext{minimize} quad& (1/2)Vert

uVert_*^2+ b^T

u \ ext{s.t.} quad& A^T

u=0 end{aligned} \)

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

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