LagrangianDuality.pdf

立即下载 作者: 一生流水
上传时间: 2024-12-19
关键词: 函数 约束 条件 优化 解决 简单 大于 等于 problem 仿射
大小 317.2 KB
描述
Lagrangian Duality for Dummies
By David Knowles
Translated by hittlle
来源：
https://cs.stanford.edu/people/davidknowles/lagrangian_duality.pdf
我们想解决下面这个优化问题
我们先不对函数的凸性做任何假设。为了简单起见我们也没有给出不等式约束，但是后面我
们会直接加上这些约束条件。一个很直接（也很笨）的解决办法也是优化下面这个函数：
这儿 I[u]是一个无穷阶跃函数：
如果不满足约束条件，阶跃函数就会给出一个的惩罚。如果能最小化 J(x)，就能解决我们
的问题。但是呢从优化的角度来说，J(x)是一个非常糟糕的函数，因为它既不可微也不是连
续的。能不能用一个更好的函数替换 I[u]呢？表示直线的函数 u 处理起来更简单。选用后
者可能看起来很蠢， 但是在大于等于 0 的情况下，如果约束条件不满足，惩罚项是在正
确的方向上，并且 u是 I[u]的一个下界(见图 1)。
如果用 u 替换 J(x)中的 I[u]， 我们就得到一个 x 和的拉格朗日函数：
应该看到，在求 L 相对于 的最大值时，对 L 取 的偏导数就得到原来的函数 J(x)。对 x 的
每一个取值，如果函数满足约束条件，也即
那么我们尽量能做的就是让
从而有
当然，也可以让 ，从页 L(x,  )也趋于无穷大。综上，我们有
这个结论很不错，但是它对解决原来那个优化问题有什么作用呢？注意到我们是要求 J(x)的
最小值，现在变成了求
求这个问题很难。但是如果我们改变一下求的顺序会怎么样？我们有
这儿 g( ) = ,即所谓的对偶函数。求对偶函数的极大值问题就变
成了所谓的对偶问题（dual problem），这有别于原始问题(primal problem)。因为 g( )是仿
射函数的点态极小值（L(x,  )是仿射函数），所以它是一个凹函数。求 L(x, )相对于 x 的极
小值可能很困难。但是因为 g( )是一个凹函数并且在 大于等于 0 是一个线性约束条件，
所以求 g( )相对于 的极大值是一个凸优化问题，也是一个简单的问题。但是解决这个问
题和原来那个问题有关系吗？注意到 u
目录
函数/约束/条件/优化/解决/简单/大于/等于/problem/仿射/ 函数/约束/条件/优化/解决/简单/大于/等于/problem/仿射/