凸优化第五章对偶 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）得到