凸優化第五章對偶 5.5最優性條件

5.5最優性條件

1. 互補松弛性
2. KKT最優性條件

互補松弛性

假設問題具有強對偶性，

為其原問題的最優解，

為其對偶問題的最優解，可知：

根據對偶函數的定義，可知

小于等于任意的

是以取

時，也成立，故

再根據

可知

是以上述不等式的等号成立。

推出兩點：

（1）

最小化

（2）上式等号成立，即：

且

（等式限制），是以可推出

，而

是以

，成為互補松弛性。

也可寫成：

KKT最優性條件

非凸問題的KKT條件

和前面一樣，假設問題的限制函數和目标函數可微，

為其原問題的最優解，

為其對偶問題的最優解，KKT條件：

稱上式為Karush-Kuhn-Tucker條件，簡稱KKT條件。

對于目标函數和限制函數均可微的任意優化問題，如果強對偶性成立，那麼任意一對原問題最優解和對偶問題最優解都必須滿足KKT條件。

凸問題的KKT條件

當原問題是凸問題時，滿足KKT條件的點也是原、對偶問題的最優解。

證明：假設

滿足KKT條件，且原問題是凸問題。

前兩個條件表明

是可行解。而因為條件（3）可知

是關于x的凸函數，根據條件（5）可知L在

處倒數為0，故

極小化L（根據互補松弛性也可知

極小化L。）

故：

是以對偶間隙為0，

分别是原問題和對偶問題的最優解。

例子

KKT條件：

根據（5）可知

，

再看（4），考慮兩種情況1）

，此時

，

。2）

，此時

，是以

有兩種情況，

整理得

，再根據條件（2）得到