【凸最佳化筆記6】-拉格朗日對偶（Lagrange duality）、KKT條件

1.問題背景

2.原始問題極其轉化

3.拉格朗日對偶問題

4.Slater 條件

5.KKT 條件

6.例子

1。問題背景

在一個最佳化問題中，原始問題通常會帶有很多約束條件，這樣直接求解原始問題往往是很困難的，於是考慮將原始問題轉化為它的對偶問題，透過求解它的對偶問題來得到原始問題的解。

對偶性（Duality）

是凸最佳化問題的核心內容。

2。原始問題極其轉化

2.1 原始問題（Primal problem）

將一個原始最最佳化問題寫成如下形式：

$\\\begin{aligned} \min_x &\quad f_0(x) \\ s.t. &\quad f_i(x) \leq 0, i=1,2,...,m \\ &\quad h_j(x) = 0,j=1,2,...,p\end{aligned}$

這裡可以參考【凸最佳化筆記3】-第1節-凸最佳化問題中對凸最佳化問題的定義。

需要注意的是

$f_i(x)\leq0$

的形式，若是大於等於

，則需要修改符號轉成這種形式，以避免不必要的麻煩。

事實上，在求解原問題的對偶問題時，並不要求原始問題一定是凸問題，

和

可以是一般函式而不一定非得是凸函式。

2.2 拉格朗日函式（Lagrangian function）

將原始問題的拉格朗日函式定義為：

$L(x, \lambda, v) = f_0(x)+\sum_{i=1}^{m}{\lambda_if_i(x)}+\sum_{j=1}^{p}{v_jh_j(x)}\\$

其中

$x\in R^n,\lambda\in R^m,v\in R^p$

。

可以看到，拉格朗日函式

相對於原始問題引入了兩個新變數（向量）

$\lambda,v$

，稱為拉格朗日乘子。

拉格朗日函式

如果看成是關於

的函式，那它其實就是對原始問題中目標函式與約束條件進行線性加權，目標函式的權係數是

，約束條件的權係數是

$\lambda_i$

或

；

如果

看成是關於

$\lambda$

或

的函式，則其餘部分可看成常數，

就可看作是一個關於

$\lambda$

或

的仿射函式（即最高次冪為1的多項式函式）。

2.3 拉格朗日對偶函式（ Lagrange dual function）

拉格朗日對偶函式（簡稱對偶函式）透過對拉格朗日函式關於

取下確界得到，即：

$g(\lambda, v) = \inf_xL(x,\lambda,v) \\$

符號表示取下確界。求解析式可先將

看成是關於

的函式，而將拉格朗日乘子看作常數，求出

的極小值點，再將該點代入

，得到的關於

$\lambda$

和

的表示式就是對偶函式。

對偶函式具有如下兩條重要性質：

i。對偶函式一定是凹函式，其凹性與原目標函式和約束函式凹凸與否無關。

證明：

$L(x,\lambda,v)$

可以看作是一個無限的函式集，這個函式集中每個元素是

$L(x_i,\lambda,v)$

，

取遍其在定義域上的所有值得到不同的

。針對不同的

，

$L(x_i,\lambda,v)$

的表示式不一樣，由於這個表示式是隻關於

$\lambda$

和

的，故用

$g_i(\lambda,v)$

來表示。所以有：

$\\ g(\lambda,v)=inf\{g_1(\lambda,v),g_2(\lambda,v),...,g_\infty(\lambda,v)\}\\$

由本章 2。2 節已提到過，當

看成是關於

$\lambda$

或

的函式時，

是一個仿射函式，亦即，

$g_i(\lambda,v)$

是仿射函式，對仿射函式集取下確界，得到的函式是凹函式，如圖 2-3 所示：

圖 2-3

黑線加粗部分就是

$g(\lambda,v)$

，是凹函式。

ii。對

$\forall\lambda\geq0,\forall v$

（泛指向量中的每個分量），如果原問題最優解對應的目標函式值為

，則

$g(\lambda, v)\leq p^*$

。

證明：

設原問題的最優解為

，結合

$f_i(x)\leq0,h_j(x)=0$

，很容易有：

$L(x^*, \lambda, v) = f_0(x^*)+\sum_{i=1}^{m}{\lambda_if_i(x^*)}+\sum_{j=1}^{p}{v_jh_j(x^*)}\leq f_0(x^*)=p^* \\$

假設這個最優解

在

處取得，結合性質 i 中的證明部分，有：

$L(x^*,\lambda,v)=g_1(\lambda,v) \\$

很顯然，由圖 2-3 可以看到

$g(\lambda,v)$

的影象總在

$g_1(\lambda,v)$

下方，即以下不等式總成立：

$g(\lambda,v)\leq L(x^*,\lambda,v)\leq p^* \\$

3。拉格朗日對偶問題（Lagrange dual problem）

根據對偶函式的重要性質 ii ，對

$\forall\lambda\geq0,\forall v$

，對偶函式

$g(\lambda,v)$

是原問題最優值

的一個下界，最好的下界就是最大化對偶函式，因此構造原問題的對偶問題：

$\\ \begin{aligned} \max_{\lambda,v} &\quad g(\lambda,u) \\ s.t. &\quad \lambda\geq 0\end{aligned}$

由於對偶函式是凹函式，故拉格朗日對偶問題一定是凸最佳化問題，其對應的最優解為

$\lambda^*,v^*$

（最優拉格朗日乘子），若對應的最優值為

，則總有

$d^*\leq p*$

。

當

$d^*\leq p^*$

時，稱為

弱對偶（weak duality）

。

當

時，稱為

強對偶（strong duality）

。

將

稱為

對偶間隙（duality gap）。

在解存在的情況下，弱對偶總是成立的。

滿足強對偶時，可以透過求解對偶問題來得到原始問題的解。

4。 Slater 條件（Slater‘s condition）

Slater 條件用於判斷什麼情況下強對偶是成立的。

在

原問題是凸問題

的情況下，若

$\exists \ x\in relint(D)$

，使得約束條件滿足：

$f_i(x)<0,h_j(x)=0\ \ \ i=1,2...,m;j=1,2,...,p \\$

則強對偶成立。

表示原始凸問題定義域的相對內部，即在定義域上除了邊界點以外的所有點。只要能找到一個這樣的點使原凸問題等式約束依然成立且不等式約束都嚴格小於

即可。

幸運的是，對大多數一般的原凸問題，強對偶都是成立的。

若滿足 Slater 條件，則強對偶一定成立，不滿足 Slater 條件，強對偶也可能成立，它是一個充分不必要條件。

5。 KKT 條件（KKT conditions）

在對偶間隙為

（強對偶），且

對

可微的前提下，設

$x^*;\lambda^*,v^*$

分別是原問題和對偶問題的最優解，則以下四組條件稱為 KKT 條件：

$\\ \begin{cases} \frac{\partial L(x,\ \lambda^*,\ v^*)}{\partial x}|_{x=x^*} =0 \ \ \ \ \ \ \ &\text(stationarity)\\ \lambda^*_if_i(x^*)=0\ \ \ \ \ \ \ &\text(complementary\ slackness)\\ f_i(x^*)\leq0,\ h_j(x^*)=0 \ \ \ \ \ \ \ &\text(primal\ feasibility)\\ \lambda^*_i\geq0 \ \ \ \ \ \ \ &\text(dual\ feasibility) \\ \end{cases}\\$

i。穩定性條件（stationarity）

若

是原問題的最優解（極值點），則

$L(x,\lambda^*,v^*)$

在

處的微分等於

。

ii。互補鬆弛條件（complementary slackness）

這個條件表明，當

$\lambda^*_i>0$

時，

；當

時，

$\lambda^*_i=0$

。

下面給出這個條件的證明。

先給出如下推導過程：

$\begin{aligned}f_0(x^*) &=g(\lambda^*,v^*) &\text(1)\\ &=\inf_{x}\{f_0(x)+\sum_{i=1}^{m}{\lambda^*_if_i(x)}+\sum_{j=1}^{p}{v^*_jh_j(x)}\} &\text(2)\\ &\leq f_0(x^*)+\sum_{i=1}^{m}{\lambda^*_if_i(x^*)}+\sum_{j=1}^{p}{v^*_jh_j(x^*)} &\text(3)\\ &\leq f_0(x^*) &\text(4) \end{aligned}\\$

說明：第（1）步由對偶間隙為

這個前提可以得到；第（2）步是對偶函式的定義；第（3）步，需結合本章 2。3 節對偶函式兩條重要性質的證明部分以及圖 2-3 ，假設

在

處取得，對偶函式

$g(\lambda^*,v^*)$

總是在

$g_1(\lambda^*,v^*)$

的下方，故小於等於號成立；第（4）步由原問題和對偶問題約束條件易得。

結論：觀察（1）和（4），上述式子中的小於等於號就只能取等號，故（3）中

$\sum_{i=1}^{m}{\lambda^*_if_i(x^*)}=0\\$

又因為其中的每一項都有

$\lambda^*_if_i(x^*)\leq 0$

，故

$\lambda^*_if_i(x^*)= 0$

。

iii。原問題的可行性（primal feasibility）

原問題的最優解必然滿足原問題的約束條件。

iv。對偶問題的可行性（dual feasibility）

對偶問題的最優解必然滿足對偶問題的約束條件。

對

一般的原問題

，KKT 條件是

$x^*;\lambda^*,v^*$

為最優解的必要條件，即只要

$x^*;\lambda^*,v^*$

為最優解，則一定滿足 KKT 條件。

對

原問題為凸問題

， KKT 條件是

$x^*;\lambda^*,v^*$

為最優解的充要條件。

6。例子

求lasso問題的對偶問題和 KKT 條件。

i。 lasso問題

$\min_\beta \ \frac{1}{2}||y-X\beta||_2^2 + \lambda||\beta||_1 \\$

ii。將其寫成標準凸最佳化問題的形式

$\begin{aligned} &\min_{\beta,z}\ \frac{1}{2}||y-z||_2^2 + \lambda||\beta||_1 \\ &\ s.t. \ \ \ z-X\beta=0 \end{aligned} \\$

iii。構造 Lagrangian

$L(\beta,z,u)=\frac{1}{2}||y-z||_2^2+\lambda||\beta||_1+u^T(z-X\beta) \\$

iv。寫出對偶函式

$\begin{aligned} g(u)&=\min_{\beta,z}\ \ \frac{1}{2}||y-z||_2^2+\lambda||\beta||_1+u^T(z-X\beta) &\text(1) \\ &=\min_z\ \{\frac{1}{2}||y-z||_2^2+u^Tz\}+\min_\beta\ \{\lambda||\beta||_1-u^TX\beta\} &\text(2) \\ &= u^Ty - \frac{1}{2}||u||^2_2 +\min_\beta\ \{\lambda||\beta||_1-u^TX\beta\} &\text(3) \\ &= -\frac{1}{2}(||u||^2_2-2u^Ty+||y||_2^2)+\frac{1}{2}||y||_2^2 +\min_\beta\ \{\lambda||\beta||_1-u^TX\beta\} &\text(4) \\ &=\frac{1}{2}||y||_2^2-\frac{1}{2}||u-y|| _2^2-\lambda\ \max_\beta\ \{\frac{u^TX}{\lambda}\beta -||\beta||_1 \} &\text(5) \\ &=\frac{1}{2}||y||_2^2-\frac{1}{2}||u-y|| _2^2-\lambda\ I_{\{v:\ ||v||_\infty\leq1\}}(\frac{X^Tu}{\lambda}) &\text(6) \end{aligned}\\$