拉格朗日乘子法是一种寻找多元函数在一组约束下的极值的方法,通过引入拉格朗日乘子,可将有d个变量与k个约束条件的最优化问题转化为具有d+k个变量的无约束优化问题的求解。
假设
,
,
是定义在
上的连续可微函数,考虑约束最优化问题:
,
s.t.
,
称此约束最优化问题为原始最优化问题或原始问题。
广义拉格朗日函数(generalized Lagrange function):
这里,
,
和
是拉格朗日乘子,
,考虑x的函数:
下标P表示原始问题,给定某个x,如果x违反原始问题的约束条件,即存在某个i使得
,或者存在某个j使得
,那么就有
,如果x满足约束条件,则
考虑极小化问题:
是广义拉格朗日函数的极小极大问题,把原始最优化问题表示为广义拉格朗日函数的极小极大问题.
定义原始问题的最优值为:
定义:
考虑极大化
,即:
为广义拉格朗日函数的极大极小问题:
可以将广义拉格朗日函数的极大极小问题表示为约束最优化问题:
称为原始问题的对偶问题,定义对偶问题的最优值为:
,为对偶问题的值
若原始问题和对偶问题都有最优值,则:
1、
设
和
,
分别是原始问题和对偶问题的可行解,并且
,则
和
,
分别是原始问题和对偶问题的最优解。
2、考虑原始问题和对偶问题,假设函数
和
是凸函数,
是仿射函数,并且假设不等式约束
是严格可行的,即存在x,对所有i有
,则存在
,
,
,使得
是原始问题的解,
,
是对偶问题的解,并且:
3、对原始问题和对偶问题,假设函数 是凸函数, 是仿射函数,并且假设不等式约束是严格可行的,则分别是原始问题和对偶问题的解的充分必要条件是 满足下面的Karush-kuhn-Tucker(KKT)条件:
(KKT对偶互补条件)
由KKT对偶互补条件可知,若
,则
。
内容参考: