具有约束的梯度下降(拉格朗日乘数)

Question

我试图使用梯度下降在N个参数中找到函数的最小值.但是我想这样做,同时将参数的绝对值之和限制为1(或<= 1,无关紧要).由于这个原因,我使用了拉格朗日乘数的方法,所以如果我的函数是f(x),我将最小化f(x)+ lambda*(g(x)-1)其中g(x)是平滑近似值参数绝对值的总和.

根据我的理解,当g(x)= 1时,此函数的梯度将仅为0,因此找到局部最小值的方法应该找到我的条件也满足的最小函数.问题是这个加法我的函数是无界的,因此Gradient Descent只是找到越来越大的lambdas,它们具有越来越大的参数(绝对值)并且永远不会收敛.

目前我正在使用CG的python(scipy)实现,所以我真的更喜欢不要求我自己重新编写/调整CG代码但使用现有方法的建议.

Answer 1

问题在于,当使用拉格朗日乘数时,临界点不会出现在拉格朗日的局部最小值 - 它们发生在鞍点处.由于梯度下降算法旨在找到局部最小值,因此当您给出约束问题时,它无法收敛.

通常有三种解决方案:

• 使用能够找到鞍点的数值方法,例如牛顿法.然而,这些通常需要梯度和Hessian的解析表达式.
• 使用惩罚方法.在这里,您可以在成本函数中添加一个额外的(平滑)项,当约束满足(或接近满足)时为零,而当不满足约束时则为非常大.然后你可以像往常一样运行梯度下降.然而,这通常具有较差的收敛性,因为它进行了许多小的调整以确保参数满足约束.
• 而不是寻找拉格朗日的临界点,最小化拉格朗日梯度的平方.显然,如果拉格朗日量的所有导数都为零,那么梯度的平方将为零,并且由于某些东西的平方永远不会小于零,您将找到与拉格朗日极值相同的解决方案.但是,如果你想使用渐变下降,那么你需要一个拉格朗日渐变的平方渐变的表达式,这可能不容易得到.

就个人而言,我会选择第三种方法,如果很难得到它的解析表达式,那么在数值上找到拉格朗日梯度的平方渐变.

另外,你在问题中没有说清楚 - 你使用的是梯度下降还是CG(共轭渐变)？

Answer 2

在1987 年的论文“约束微分优化”中，Platt 和 Barr 以一种非常简单又简单的方式解决了这个问题。他们将他们的方法称为基本微分乘子法（BDMM）。

该方法声称对于拉格朗日： L(x, b) = f(x) + bg(x)

通过对 x 进行梯度下降，同时对 b 进行梯度“上升”，您最终将收敛到 L(x, b) 的驻点，这是约束 g(x)=0 下 f(x) 的局部最小值。还可以结合惩罚方法来使收敛更快、更稳定（作者称之为改进的微分乘子法）。

一般来说，只需反转 b 的梯度即可。

我已经在几个简单的案例中尝试过它并且它有效，尽管在读完那篇论文后我不太明白为什么。

Answer 3

可能为时已晚,无法对OP有所帮助,但在相同情况下可能对其他人有用:

绝对值约束的问题通常可以通过添加一些"辅助"变量重新表述为仅具有线性约束的等效问题.

例如,考虑问题1:

查找(x1,x2)使f(x1,x2)最小化受非线性约束| x1 | + | x2 | <= 10的影响.

有一个线性约束版本,问题2:

查找(x1,x2,x3,x4)使f(x1,x2)最小化,但受以下线性约束的影响:

1. X1 <= X3
2. -x1 <= X3
3. X2 <= X4
4. -x2 <= X4
5. X3 + X4 <= 10

注意:

• 如果(x1,x2,x3,x4)满足问题2的约束,则(x1,x2)满足问题1的约束(因为x3> = abs(x1),x4> = abs(x2))
• 如果(x1,x2)满足问题1的约束,那么我们可以通过设置x3 = abs(x1),x4 = abs(x2)来扩展到满足问题2约束的(x1,x2,x3,x4)
• x3,x4对目标函数没有影响

因此,找到问题2的最优值将为问题1提供最优,反之亦然.