带约束的梯度下降（拉格朗日乘子）

Question

我试图用梯度下降法在N个参数中找到函数的最小值。不过，我想这样做，而限制参数的绝对值的总和为1（或< = 1，无所谓）。出于这个原因，我使用拉格朗日乘子法，所以如果我的函数是f（x），我将最小化f（x）+ lambda *（g（x）-1），其中g（x）是参数绝对值之和。

现在据我所知，当g（x）= 1时，这个函数的渐变只会是0，所以找到一个局部最小值的方法应该找到我的函数的最小值，其中我的条件也满足。问题是这个附加函数是无界的，所以渐变下降只是发现越来越大的lambda表达式（绝对值）越来越大，从不会收敛。

目前我使用Python的CG（scipy）实现，所以我更喜欢那些不需要我自己重写/调整CG代码但是使用现有方法的建议。

Answer 1

问题是，当使用拉格朗日乘子时，临界点不会发生在拉格朗日的局部最小值处 - 它们发生在鞍点处。由于梯度下降算法设计用于查找局部最小值，因此当您给它一个约束问题时它不会收敛。

通常有三种解决方法：

• 使用数值方法，其能够找到鞍点，例如牛顿的方法。然而，这些通常需要梯度和Hessian的解析表达式。
• 使用惩罚方法。在这里，您为成本函数添加了一个额外的（平滑）项，当约束条件满足（或接近满意）时，该项为零，当不满意时为非常大。然后，您可以照常运行渐变下降。但是，这通常收敛性较差，因为它会进行很多小的调整以确保参数满足约束条件。
• 不是寻找拉格朗日的临界点，而是最小化拉格朗日的梯度的平方。显然，如果拉格朗日函数的所有导数都是零，那么梯度的平方将为零，并且由于某物的平方不可能小于零，所以您会发现与通过极限拉格朗日函数的方法相同的解。然而，如果你想使用梯度下降，那么你需要一个表达拉格朗日梯度梯度的梯度，这可能不容易。

就个人而言，我会用第三种方法去，并找到拉格朗日梯度的平方的梯度数值，如果它太难以得到的解析表达式它。另外，你不太清楚你的问题 - 你是使用梯度下降还是CG（共轭梯度）？

Answer 2

可能为时已晚是有帮助的OP，但可能是有用的人在同样的情况：

与绝对值约束的问题往往可以改写成只有线性约束，用等效问题增加一些“帮手”变量。

例如，考虑问题1：

查找（X1，X2），该F（X1，X2）受试者最小化到非线性约束| X1 | + | X2 | < = 10。

有一个线性约束版本，问题2：

1. ：

   查找（X1，X2，X3，X4），该F（X1，X2）受以下线性约束最小化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）中，X 4> = ABS（×2））
• 如果（X1，X2）满足问题1的限制，那么我们就可以延伸到（X1，X2，X3，X4），用于问题满足约束2通过设置X3 = ABS（X1），X 4 = ABS（×2）
• X3，X4对目标函数没有影响

由此可见，找到最佳的问题2将会给你一个最佳的问题1，反之亦然。