理解拉格朗日对偶1
需积分: 0 138 浏览量
2022-08-03
14:55:54
上传
评论
收藏 446KB PDF 举报
理解拉格朗日对偶
本笔记是对凸优化理论中拉格朗日对偶性的总结与理解，主要参考了以下资料：
Convex Optimization, Stephen Boyd and Lieven Vandenberghe, Cambridge University
如何通俗地讲解对偶问题？尤其是拉格朗日对偶lagrangian duality？
本笔记的目的在于帮助读者更好地理解拉格朗日对偶性的概念，因此不会包含严谨的数学证明过程。
1. 拉格朗日对偶问题
我们先给出拉格朗日对偶性的定义形式。
考虑具有等式约束和不等式约束的原始优化问题：
这个问题的定义域是目标函数、等式约束函数和不等式约束函数定义域的交集，即
，将原始问题的最优值记为 。
构造拉格朗日函数：
我们将拉格朗日函数 在定义域上针对 求下界的结果称为拉格朗日对偶函数(Lagrange dual function)，
它是拉格朗日乘子 和 的函数，即
上式最右端括号中的函数可以看作是关于一组 的仿射函数，因此函数 是关于这个仿射函数的逐点下确界。由
于凹函数（仿射函数既凸且凹）的逐点下确界仍是凹函数，因此 总是凹函数，不管原问题是否为凸。
函数 的另一个重要性质是它给出了原问题最优值 的一个下界，即对任意的 和 下式成立：
可以很容易地验证这个重要的性质。设 是原问题的一个可行点，即 且 ，假设 ，我们有
这是因为左边的第一项非正而第二项为零。根据上述不等式，有
因此
评论0
最新资源