UA SIE545 優化理論基礎4 對偶理論簡介1 松弛問題與Lagrange對偶

優化理論基礎第四部分介紹對偶問題(Dual problem)及其簡單性質，是對偶理論的入門，后續章節會更深入地討論對偶問題的數學基礎及其求解方法。這一講我們介紹松弛(relaxation)這個概念以及為什么我們需要討論對偶問題。

---

定義1 Relaxation
考慮兩個優化問題：
$$\begin{gathered} z_P=\min \{f(x):x\in X\} \\ {z}_R=\min \{g(x):x\in Y\} \end{gathered}$$

稱優化問題R是優化問題P的一個松弛問題，如果

$f(x)\ge g(x),?x\in X$

$X?Y$

評注1 根據第一個條件，我們知道最優值一定滿足$z_P\ge z_R$，因為
$$\underset{x\in X}{\min }f(x)\ge \underset{x\in X}{\min }g(x)\ge \underset{x\in Y}{\min }g(x)$$

根據第二個條件，優化R的可行域比優化P的可行域更大，所以如果優化R是infeasible，那么優化P也是infeasible。

性質1 假設$x_R$是優化R的一個最優解，如果它滿足$x_R\in X$, $f(x_R)=g(x_R)$，則$x_R$也是優化P的一個最優解。

證明
$x_R$是優化R的一個最優解說明$?x\in Y$, $g(x)\ge g(x_R)$，根據relaxation的條件，$?x\in X,f(x)\ge g(x)\ge g(x_R)=f(x_R)$，因此$x_R$也是優化P的一個最優解。
證畢

---

例1 不求解線性規劃，考慮$z^{?}$的下界，其中$z^{?}$為
$$\begin{gathered} z^{?}=\underset{x_1,x_2}{\min }2x_1+4x_2 \\ s.t.?\begin{array}{l}{x}_1+x_2\ge 20\\ 5x_1+3x_2\ge 90\\ x_2\le 10,x_1,x_2\ge 0\end{array} \end{gathered}$$

我們記這個線性規劃為P，為了找$z^{?}$的下界，根據評注1的討論，我們可以找線性規劃P的一個relaxation。但我們知道，隨便修改一個數字，讓可行域變大或者目標函數變小，比如第一個約束的20改成19或者目標函數系數從2，4改成1，2等，都可以是relaxation，那么怎么樣的relaxation才是值得我們去討論的呢？

我們在KKT理論的框架下來討論這個問題。定義Lagrange函數
$$\begin{gathered} ?(x_1,x_2,u_1,u_2,u_3)=2x_1+4x_2+u_1(?x_1?x_2+20) \\ +u_2(?5x_1?3x_2+90)+u_3(x_2?10) \end{gathered}$$

則KKT定理說明線性規劃P等價于加入KKT條件的優化R，其中優化R為
$$\min ?(x_1,x_2,u_1,u_2,u_3),x_1,x_2,u_1,u_2,u_3\ge 0$$

不難發現優化R就是線性規劃P的一個relaxation，記$\theta (u_1,u_2,u_3)$是優化R目標函數的最優值，則
$$z^{?}\ge \theta (u_1,u_2,u_3),u_1,u_2,u_3\ge 0$$

接下來我們分析優化R的目標函數，
$$\begin{gathered} ?(x_1,x_2,u_1,u_2,u_3)=(2?u_1?5u_2)x_1 \\ +(4?u_1?3u_2+u_3)x_2+20u_1+90u_2?10u_3 \end{gathered}$$

我們需要牢記，我們的目標是最小化這個目標函數從而得到$z^{?}$的有價值的下界。如果$2?u_1?5u_2<0$，目標函數關于$x_1$單調遞減，那么對于$x_1\ge 0$，最小值就是$x_1\to +\infty$的時候取得，為$?\infty$，這個下界說明$z^{?}>?\infty$，這就是沒有價值的下界，因為我們不做這些分析也知道這個結果。因此我們需要$2?u_1?5u_2\ge 0$，同理，$4?u_1?3u_2+u_3\ge 0$，此時目標函數的最小值將在$x_1=x_2=0$時取得，因此
$$\begin{gathered} \theta (u_1,u_2,u_3)=20u_1+90u_2?10u_3 \\ 2?u_1?5u_2\ge 0 \\ 4?u_1?3u_2+u_3\ge 0 \\ {u}_1,u_2,u_3\ge 0 \end{gathered}$$

現在我們進一步討論，雖然得到了一個比較合理的下界了，但它是關于$u_1,u_2,u_3$的函數，為了得到一個最大的下界，我們考慮線性規劃D
$$\begin{gathered} \max \theta (u_1,u_2,u_3)=20u_1+90u_2?10u_3 \\ s.t.2?u_1?5u_2\ge 0 \\ 4?u_1?3u_2+u_3\ge 0 \\ {u}_1,u_2,u_3\ge 0 \end{gathered}$$

顯然在線性規劃的對偶理論中，線性規劃D是線性規劃P的對偶問題。

---

接下來我們討論怎么將線性規劃的對偶理論推廣到非線性規劃中。從例1中我們可以總結，對偶問題的決策變量是Lagrange乘子，將原來的決策變量作為對偶問題的“乘子”，這種思路是建立在KKT理論與Lagrange函數上的，我們稱這種對偶為Lagrange對偶(Lagrangian Duality)。

定義2 Lagrange對偶問題。考慮優化問題P：
$$\begin{gathered} \min f(x) \\ s.t.g(x)\le 0,h(x)=0,x\in X \end{gathered}$$

定義其對偶問題為優化D：
$$\begin{gathered} \underset{u,v}{\sup }\theta (u,v) \\ s.t.u\ge 0 \end{gathered}$$

評注2
我們按例1的邏輯順序來梳理一下定義2，首先寫出優化P的Lagrange函數，
$$?(x,u,v)=f(x)+u^{T}g(x)+v^{T}h(x)$$

然后關于$x$做最小化，
$$\theta (u,v)=\underset{x\in X}{\inf }?(x,u,v)$$

最后就是定義中的最大化了。

---

例2 線性規劃的對偶，考慮最小化
$$\begin{gathered} \min c^{T}x \\ s.t.b?Ax\le 0 \end{gathered}$$

它的對偶問題的目標函數為
$$\begin{gathered} \theta (u)=\inf \{c^{T}x+u^T(b?Ax)\} \\ =\inf \{(c^T?u^{T}A)x+u^{T}b\}=\{\begin{array}{l}{u}^{T}b,if{A}^{T}u=c\\ ?\infty ,otherwise\end{array} \end{gathered}$$

因此對偶問題為
$$\begin{gathered} \underset{u}{\sup }{u}^{T}b \\ s.t.A^{T}u=c,u\ge 0 \end{gathered}$$

總結

以上是生活随笔為你收集整理的UA SIE545 优化理论基础4 对偶理论简介1 松弛问题与Lagrange对偶的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。