1.原始問題

假設

f(x), C_{i}(x), h_{j}(x)

是定義在

R^{n}

上的連續可微函式，考慮約束最最佳化問題：

\min _{x \in R^{n}} f(x) \\

\left\{\begin{array}{c}\text {s.t. } C_{i}(x) \leq 0, i=1,2, \ldots k \\ h_{j}(x)=0, j=1,2, \ldots l\end{array}\right. \\

現在如果不考慮約束條件，原始問題就是：

\min _{x \in R^{n}} f(x) \\

而這種式子可直接對

f(x)

求導，然後令導數為0，就可解出最優解，而偏偏有約束條件，所以就要想辦法去掉約束條件，所以拉格朗日函式就是幹這個的。

格朗日函式：

L(x, \alpha, \beta)=f(x)+\sum_{i=1}^{k} \alpha_{i} C_{i}(x)+\sum_{j=1}^{l} \beta_{j} h_{j}(x) \\

現在，把

L(x, \alpha, \beta)

看作是關於

\alpha_{i}, \beta_{j}

的函式，要求其最大值：

\max _{\alpha, \beta: \alpha_{i} \geq 0} L(x, \alpha, \beta) \\

經過我們最佳化，確定

\alpha_{i}, \beta_{j}

的值使得取

L(x, \alpha, \beta)

得最大值（此過程把

x

看作常量），因為已經確

\alpha_{i}, \beta_{j}

定，顯然最大值

\max _{\alpha, \beta: \alpha_{i} \geq 0} L(x, \alpha, \beta)

就只是和有關的函式

x

，定義這個函式為：

\theta_{p}(x)=\max _{\alpha, \beta: \alpha_{i} \geq 0} L\left(x, \alpha^{*}, \beta^{*}\right) \\

下面透過

x

是否滿足約束條件兩方面分析

\theta_{p}(x)

函式。

考慮某個

x

違反原始條件的約束，即

C_{i}(x)>0

或者

h_{j}(x) \neq 0

，那麼：

\theta_{p}(x)=\max _{\alpha, \beta: \alpha_{i} \geq 0} f(x)+\sum_{i=1}^{k} \alpha_{i} C_{i}(x)+\sum_{j=1}^{l} \beta_{j} h_{j}(x)=+\infty \\

注意中間的最大化式子就是確定

\alpha_{i}, \beta_{j}

之後的結果，若

C_{i}(x)>0

，則令

\alpha_{i} \rightarrow+\infty

；如果，很

h_{j}(x) \neq 0

容易取值

\beta_{j}

使得。

\beta_{j} h_{j}(x) \rightarrow+\infty

。

考慮x滿足原始條件的約束，因為

C_{i}(x) \leq0

且

h_{j}(x) = 0

，

\alpha_{i} \geq 0

，可以得到

\alpha_{i} C_{i}(x) \leq0

，

\beta_{j} h_{j}(x)=0

，所以：

\theta_{p}(x)=\max _{\alpha, \beta: \alpha_{i} \geq 0} f(x)+\sum_{i=1}^{k} \alpha_{i} C_{i}(x)+\sum_{j=1}^{l} \beta_{j} h_{j}(x)=f(x) \\

注意，我們的最大化是確定

\alpha_{i}, \beta_{j}

的過程，

f(x)

就是常量，常量的最大值就是其本身；

\alpha_{i} C_{i}(x) \leq0

的最大值是0。

透過上面兩條分析可以得出：

\theta_{p}(x)=\left\{\begin{array}{l}f(x), x \text { 滿足原始問題約束 } \\ +\infty, x \text { 不滿足原始問題約束 }\end{array}\right. \\

那麼在約束條件下找最小值：

\min _{x} \theta_{p}(x)=\min _{x} \max _{\alpha, \beta: \alpha_{i} \geq 0} L(x, \alpha, \beta)=\min _{x} f(x) \\

即

\min _{x} \theta_{p}(x)

與原始問題等價，所以用

\min _{x} \theta_{p}(x)

代表原始問題。

以上便把有約束問題轉變成無約束問題：

\min _{x \in R^{n}} f(x) \\

\left\{\begin{array}{c}\text {s.t. } C_{i}(x) \leq 0, i=1,2, \ldots k \\ h_{j}(x)=0, j=1,2, \ldots l\end{array}\right. \\

=>\min _{x} \max _{\alpha, \beta: \alpha_{i} \geq 0} L(x, \alpha, \beta) \\

2.對偶問題

定義關於

\alpha, \beta

的函式：

\theta_{D}(\alpha, \beta)=\min _{x} L(x, \alpha, \beta) \\

（關於

x

的函式最小化，

x

確定以後，最小值只與有

\alpha, \beta

關，便於理解，假設

x=x^{*}

，

\left.\theta_{D}(\alpha, \beta)=\min _{x} L(x, \alpha, \beta)=L\left(x^{*}, \alpha, \beta\right)\right)

考慮極大化

\theta_{D}(\alpha, \beta)=\min _{x} L(x, \alpha, \beta)=L\left(x^{*}, \alpha, \beta\right)

，即：

\max _{\alpha, \beta: \alpha_{i} \geq 0} \theta_{D}(\alpha, \beta)=\max _{\alpha, \beta: \alpha_{i} \geq 0} \min _{x} L(x, \alpha, \beta) \\

這就是原始問題的對偶問題，再把原始問題寫出來：

\min _{x} \theta_{p}(x)=\min _{x} \max _{\alpha, \beta: \alpha_{i} \geq 0} L(x, \alpha, \beta) \\

定義對偶問題的最優值：

d^{*}=\max _{\alpha, \beta: \alpha_{i} \geq 0} \theta_{D}(\alpha, \beta) \\

3.原始問題與對偶問題的關係

定理：

d^{*}=\max _{\alpha, \beta: \alpha_{i} \geq 0} \min _{x} L(x, \alpha, \beta) \leq L(x, \alpha, \beta) \leq \min _{x} \max _{\alpha, \beta: \alpha_{i} \geq 0} L(x, \alpha, \beta)=p^{*} \\

證明：對任意的

x,\alpha, \beta

\theta_{D}(\alpha, \beta)=\min _{x} L(x, \alpha, \beta) \leq L(x, \alpha, \beta) \leq \max _{\alpha, \beta: \alpha_{i} \geq 0} L(x, \alpha, \beta)=\theta_{p}(x) \\

所以

\theta_{D}(\alpha, \beta) \leq \theta_{p}(x)

，即對於任意

\theta_{D}

的值，都小於

\theta_{p}

：

\max _{\alpha, \beta: \alpha_{i} \geq 0} \theta_{D}(\alpha, \beta) \leq \min _{x} \theta_{p}(x) \\

就可以得出弱對偶的表示式：

d^{*}=\max _{\alpha, \beta: \alpha_{i} \geq 0} \min _{x} L(x, \alpha, \beta) \leq L(x, \alpha, \beta) \leq \min _{x} \max _{\alpha, \beta: \alpha_{i} \geq 0} L(x, \alpha, \beta)=p^{*} \\

也就是說，原始問題的最優解不小於對偶問題的最優解，但我們要透過對偶問題求原始問題的最優解就必須使得原始問題的最優值與對偶問題的最優值相等。到底滿足什麼樣的條件才能使得這兩個問題的最優值相等？當然是KKT條件啦！，下面證明一下為什麼？

對於原始問題，KKT條件給出了滿足原始問題最優解的判斷條件：

\left\{\begin{array}{c}\frac{\partial L}{\partial x}=0 \\ \alpha_{i} C_{i}(x)=0 \\ h_{i}(x)=0 \\ \alpha_{i} \geq 0\end{array}\right. \\

具體為什麼是這個式子可參考第一的章節原始問題中對

\theta_{p}(x)

描述。

在滿足這個式子的前提下，再看一下原始問題和對偶問題。

原始問題：

\min _{x} \max _{\alpha, \beta: \alpha_{i} \geq 0} f(x)+\sum_{i=1}^{k} \alpha_{i} C_{i}(x)+\sum_{j=1}^{l} \beta_{j} h_{j}(x)=\min _{x} f(x) \\

對偶問題：

\max _{\alpha, \beta: \alpha_{i} \geq 0} \min _{x} f(x)+\sum_{i=1}^{k} \alpha_{i} C_{i}(x)+\sum_{j=1}^{l} \beta_{j} h_{j}(x)=\max _{\alpha, \beta: \alpha_{i} \geq 0} \min _{x} f(x) \\

因為

\min _{x} f(x)

與

\alpha, \beta

無關，所以

\max _{\alpha, \beta: \alpha_{i} \geq 0} \min _{x} f(x)=\min _{x} f(x)

所以原始問題等於對偶問題：

\max _{\alpha, \beta: \alpha_{i} \geq 0} \min _{x} L(x, \alpha, \beta)=L(x, \alpha, \beta)=\min _{x} \max _{\alpha, \beta: \alpha_{i} \geq 0} L(x, \alpha, \beta) \\

（這也叫做強對偶，在滿足KKT的條件下，弱對偶問題可以變成強對偶問題）之所以要把原始問題變成對偶問題，是因為在很多情況下原始問題無法求解，對偶問題很容易求解。