拉格朗日对偶性

在约束最优化问题中,常常利用拉格朗日对偶性将原始问题转换为对偶问题,通过解对偶问题而得到原始问题的解。

该方法应用在许多统计学习方法中,例如,最大熵模型与支持向量机。

9.1 原始问题

假设是定义在上的连续可微函数。考虑约束最优化问题:

称此约束最优化问题为原始最优化问题或原始问题。

首先,引进广义拉格朗日函数:

这里,是拉格朗日乘子,。考虑x的函数:

这里,下标P表示原始问题。

假设给定某个x。如果x违反原始问题的约束条件,即存在某个i使得或者存在某个j使得,那么就有:

由于某个i使得,它会使得,同样的若存在某个j使得,它会使得,而将其他的均取为0。

相反地,如果x满足约束条件式(9.2)和式(9.3),则由式(9.5)和式(9.4)可知,。因此,

所有如果考虑极小化问题:

它是与原始最优化问题(9.1)~(9.3)等价的

问题称为广义拉格朗日函数的极大极小问题

定义原始问题的最优解:

9.2 对偶问题

定义

再考虑极大化,即

将广义拉格朗日函数的极大极小问题表示为约束最优化问题

称为原始问题的对偶问题。

定义对偶问题的最优解:

9.3 原始问题和对偶问题的关系

下面讨论原始问题和对偶问题的关系。

定理9.1 若原始问题和对偶问题都有最优值,则

证明 由式(9.12)和式(9.5),对任意的和x,有

由于原始问题和对偶问题均有最优值,所以,

推论9.1分别是原始问题(9.1)~(9.3)和对偶问题(9.12)~(9.13)的可行解,并且,则分别是原始问题和对偶问题的最优解。

在某些条件下,原始问题和对偶问题的最优解相等,,这时对偶问题和原始问题等效

定理9.2 考虑原始问题(9.1)~(9.3)和对偶问题(9.12)~(9.13),假设函数是凸函数,是仿射函数,并且不等式约束是严格可行的(即存在x,对所有i有,则存在,,使是原始问题的解,是对偶问题的解,并且

定理9.3 对原始问题(9.1)~(9.3)和对偶问题(9.12)~(9.13),假设函数是凸函数,是仿射函数,并且不等式约束是严格可行的,则分别是原始问题和对偶问题的解的充分必要条件是满足下面的KKT条件

特别指出,式(9.24)称为KKT的对偶互补条件。由此条件可知:若,则