UA SIE545 優(yōu)化理論基礎(chǔ)4 對偶理論簡介3 強對偶

上一講介紹了弱對偶，弱對偶滿足
$$\inf \{f(x):x\in X,g(x)\le 0,h(x)=0\}\ge \sup \{\theta (u,v):u\ge 0\}$$

如果這個式子取等，那就是強對偶，原問題與對偶問題的最優(yōu)值相等。相比弱對偶，我們肯定是更希望有強對偶的，這一講我們討論什么樣的優(yōu)化問題，它的Lagrange對偶是強對偶。

---

Strong Duality Theorem
假設(shè)$X$是非空凸集，$f,g$是凸函數(shù)，$h(x)$是仿射函數(shù)(或者可以寫成$h(x)=Ax?b$的形式)，使得下面的條件成立：
$$?\hat{x}\in X,g(\hat{x})<0,h(\hat{x})=0,0\in inth(X)$$則下面的結(jié)論成立
$$\inf \{f(x):x\in X,g(x)\le 0,h(x)=0\}=\sup \{\theta (u,v):u\ge 0\}$$

另外，如果$\inf \{f(x):x\in X,g(x)\le 0,h(x)=0\}<\infty$，并且$\bar{x}$和$\bar{u},\bar{v}$分別為原問題與對偶問題的最優(yōu)解，則
$${\bar{u}}^{T}g(\bar{x})=0$$

這一講我們先完成這個定理的證明，之后再討論強對偶的實際應(yīng)用。

---

在正式證明這個定理之前，我們先介紹一個非常重要的Farkas定理類型的引理，這個引理將提供強對偶定理的證明框架。

引理 假設(shè)$X$是一個非空凸集，$\alpha ,g$是兩個凸函數(shù)，$h$是一個仿射函數(shù)，如果System 1無解，則System 2有解。

System 1：$\alpha (x)<0,g(x)\le 0,h(x)=0,?x\in X$
System 2: $u_0\alpha (x)+u^{T}g(x)+v^{T}h(x)\ge 0,?x\in X,(u_0,u)\ge 0,(u_0,u,v)=0$

證明
這是比較典型的Farkas定理類型的結(jié)論，所以證明方法是比較標(biāo)準(zhǔn)的，主要思路仍然是分離定理，參考UA SIE545 優(yōu)化理論基礎(chǔ)1 例題2 Farkas定理與相關(guān)結(jié)論。

定義集合，
$$A=\{(p,q,r):p>\alpha (x),q\ge g(x),r=h(x),?x\in X\}$$

假設(shè)System 1無解，則$(0,0,0)\in /A$。因為$\alpha ,g$是凸函數(shù)，$h$是仿射函數(shù)，而$X$也是凸集，不難驗證$A$也是凸集。根據(jù)凸集與點的分離，$?(u_0,u,v)$,
$$u_{0}p+u^{T}p+v^{T}r\ge 0,?(p,q,r)\in \bar{A}$$

我們先固定一個使$(p,q,r)\in A$的$x$，接下來我們觀察集合$A$的構(gòu)造，很明顯$p,q$可以任意大，因此$u_0,u$必須非負(fù)才能保證上面這個不等式成立。另外，我們可以驗證$(p,q,r)=[\alpha (x),g(x),h(x)]\in clA$，因此
$$u_0\alpha (x)+u^{T}g(x)+v^{T}h(x)\ge 0$$

其中$(u_0,u)\ge 0,(u_0,u,v)=0$，所以System 2有解。
證畢

---

下面我們正式開始證明強對偶定理。

證明
先定義一個記號，$\gamma =\inf \{f(x):x\in X,g(x)\le 0,h(x)=0\}$，假設(shè)$\gamma <+\infty$，需要注意一下的是如果$\gamma =?\infty$，根據(jù)弱對偶，
$$\inf \{f(x):x\in X,g(x)\le 0,h(x)=0\}\ge \sup \{\theta (u,v):u\ge 0\}$$

$\sup \{\theta (u,v):u\ge 0\}=?\infty$，在某種程度上，因為這個結(jié)果非常平凡，相當(dāng)于什么都沒告訴我們，所以某種程度上我們可以認(rèn)為
$$\inf \{f(x):x\in X,g(x)\le 0,h(x)=0\}=\sup \{\theta (u,v):u\ge 0\}$$

是成立的。

下面討論$|\gamma |<\infty$。定義System 1如下：
$$f(x)?\gamma <0,g(x)\le 0,h(x)=0,x\in X$$

按$\gamma$的定義，$f(x)?\gamma$肯定是不成立的，因此System 1無解。現(xiàn)在使用前面敘述的引理，$$u_0[f(x)?\gamma ]+u^{T}g(x)+v^{T}h(x)\ge 0,?x\in X$$

其中$(u_0,u)\ge 0,(u_0,u,v)=0$。接下來我們利用這個不等式(下文稱之為(1)式)導(dǎo)出想要的結(jié)論，具體操作分為三步：

$u_0>0$

$\bar{u}=u/u_0,\bar{v}=v/u_0$是對偶問題的一個解，并且$\theta (\bar{u},\bar{v})=\gamma$

如果$\bar{x}$是原問題的解，則${\bar{u}}^{T}g(\bar{x})=0$

我們先用反證法完成第一步，假設(shè)$u_0=0$，定理的假設(shè)提到
$$?\hat{x}\in X,g(\hat{x})<0,h(\hat{x})=0,0\in inth(X)$$

代入(1)式，
$$u_0[f(\hat{x})?\gamma ]+u^{T}g(\hat{x})+v^{T}h(\hat{x})=u^{T}g(\hat{x})\ge 0$$

因為$g(\hat{x})<0,u\ge 0$，因此要使$u^{T}g(\hat{x})\ge 0$成立，除非$u=0$。這時，如果我們再使用一次(1)式，并代入$u_0=0,u=0$，會得到$v^{T}h(x)\ge 0,?x\in X$。因為$0\in inth(X)$，這說明$h(X)$是$X$的線性子空間，選擇$x\in X$使得$h(x)=?\lambda v,\lambda >0$，則
$$v^{T}h(x)=?\lambda {\Vert v\Vert }^2\le 0,?v$$

考慮到$v^{T}h(x)\ge 0,?x\in X$，要使上式成立除非$v=0$，也就是說假設(shè)$u_0=0$，我們導(dǎo)出了$u,v$也都是零向量，這與定理假設(shè)矛盾。因此，$u_0>0$。

接下來我們完成第二步。使用(1)式，兩邊除以$u_0$可以得到
$$f(x)+{\bar{u}}^{T}g(x)+{\bar{v}}^{T}h(x)\ge \gamma ,?x\in X$$

記這個不等式為(2)式。進而
$$\theta (\bar{u},\bar{v})=\inf \{f(x)+{\bar{u}}^{T}g(x)+{\bar{v}}^{T}h(x):x\in X\}\ge \gamma$$

根據(jù)弱對偶定理，$\theta (\bar{u},\bar{v})\le \gamma$，因此$\theta (\bar{u},\bar{v})=\gamma$。

最后我們完成第三步。假設(shè)$\bar{x}$是一個原問題的最優(yōu)解，也就是$\bar{x}\in X,g(\bar{x})\le 0,h(\bar{x})=0,f(\bar{x})=\gamma$。利用(2)式，取$x=\bar{x}$，
$${\bar{u}}^{T}g(\bar{x})\ge 0$$

因為$\bar{u}\ge 0,g(\bar{x})\le 0$，因此${\bar{u}}^{T}g(\bar{x})=0$。

證畢

總結(jié)

以上是生活随笔為你收集整理的UA SIE545 优化理论基础4 对偶理论简介3 强对偶的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。