16

我正在尝试使用梯度下降在 N 个参数中找到函数的最小值。但是我想这样做，同时将参数的绝对值之和限制为 1（或 <= 1，没关系）。出于这个原因，我使用拉格朗日乘数法，所以如果我的函数是 f(x)，我将最小化 f(x) + lambda * (g(x)-1) 其中 g(x) 是参数的绝对值之和。

现在据我了解，当 g(x)=1 时，该函数的梯度仅为 0，因此找到局部最小值的方法应该找到我的函数的最小值，其中我的条件也满足。问题是这个添加我的函数是无界的，所以梯度下降只是找到越来越大的 lambdas 和越来越大的参数（绝对值）并且永远不会收敛。

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

4

3 回答 3

29

问题是当使用拉格朗日乘子时，临界点不会出现在拉格朗日的局部最小值处——而是出现在鞍点处。由于梯度下降算法旨在找到局部最小值，因此当您给它一个约束问题时，它无法收敛。

通常有以下三种解决方案：

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

就个人而言，我会采用第三种方法，如果很难得到解析表达式，我会用数值方法找到拉格朗日梯度的平方的梯度。

另外，您的问题并没有说清楚-您使用的是梯度下降还是 CG（共轭梯度）？

于 2012-09-05T15:31:01.730 回答
5

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

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

例如，考虑问题 1：

在非线性约束 |x1|+|x2|<=10 下，找到使 f(x1,x2) 最小化的 (x1,x2)。

有一个线性约束版本，问题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) 扩展到 (x1,x2,x3,x4) 满足问题 2 的约束
  • x3,x4 对目标函数没有影响

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

于 2014-12-17T02:19:38.903 回答
5

我发现一篇题为“约束差分优化”的旧论文写于 1988 年，解决了这个问题非常好和容易。

在那篇论文中，作者声称对于拉格朗日：L(x, b) = f(x) + bg(x)

通过在 x 上进行梯度下降，同时在 b 上进行梯度“上升”，您最终将收敛到 L(x, b) 的静止点，这是在约束 g(x)=0 下 f(x) 的局部最小值. 也可以结合惩罚法，使收敛更快更稳定。

通常只需反转 b 的梯度即可。

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

于 2019-08-14T11:13:23.363 回答