在约束最优化问题中,拉格朗日对偶性将原始问题转换为对偶问题,通过解对偶问题而得到原始问题的解。该方法在统计学习方法中得到广泛的应用
1. 原始问题
假设f(x),ci(x),hj(x)是连续可微函数,考虑约束最优化问题:
引入广义拉格朗日函数:
(2)广义拉格朗日函数 其中, x 表示列向量, α , β 表示拉格朗日乘子,且 α>=0 ,考虑 x 的函数:
(3)极大原始问题 这里,下标 p 表示原始问题
个人理解:将 α ,β 看成是自变量,求极大值。假设给定某个 x ,如果 x 违反原始问题的约束条件,即存在某个 i ,使得ci(x)>0,或者存在某个 j,使得 hj(w)≠0,则可令 β 使 βhj(x)--->+∞,而将其与各 αi,βi 取为0.
相反,如果x满足公式(1)原始问题的约束条件式,则可知: 因此,问题等价于:
所以考虑极小化问题:
广义拉格朗日函数的极小极大问题 它与原始优化问题(1)是完全等价的,两者有相同的解。即:先求 max —— 先将 α , β 看成自变量求极大值,再求 min ——将 x 看成自变量求最小值。通过这样的转换,就把原始最优化问题表示为广义拉格朗日函数的极小极大问题,为便于表示,定义原始问题的最优值: 原始问题的值
2. 对偶问题
定义 再考虑将其进行极大化,得到: 广义拉格朗日函数的极大极小问题 称为广义拉格朗日函数的极大极小问题。可以将广义拉格朗日函数的极大极小问题表示为约束最优化问题: 原始问题的对偶问题 定义对偶问题的最优值: 对偶问题的值
3. 原始问题与对偶问题的关系
讨论原始问题与对偶问题的关系:
由于原始问题与对偶问题均有最优值
最后,补充一个充要条件:
参考
《统计学习方法》李航
网友评论