c - 梯度(最速)下降的实现

Question

我正在寻找有关如何实现 Gradient (steepest) Descent 的建议在 C 中。我正在寻找 f(x)=||Ax-y||^2 的最小值，其中给出了 A(n,n) 和 y(n)。

这在 C 中很难(我认为)，因为计算梯度 Δf(x)=[df/dx(1), ..., df/dx(n)] 需要计算导数。

我只是想把它扔给 SO 以获得一些关于如何编程的方向，例如:

1) 什么维度最好从 (1,2,...) 开始

2) 关于如何进行偏导数的建议

3) 我是否应该先用更简单的语言(如 python)实现——然后再转换为 C

4) 等

让我知道你的想法!提前致谢

Answer 1

1) 从 2D 开始，这样您就可以绘制下降路径并实际看到您的算法正在运行。

2) df/dx = (f(x+h)-f(x-h))/(2*h) 如果 f 评估很便宜，(f(x+h)-f(x))/h 如果它是昂贵的。 h的选择应平衡截断误差(多为大h)和舍入误差(小h)。 h 的典型值为 ~ pow(DBL_EPSILON, 1./3)，但实际指数取决于导数公式，理想情况下应该有一个取决于 f 的前置因子。对于参数空间中的某些给定样本点，您可以在对数尺度中将数值导数绘制为 h 的函数。然后，您将清楚地看到最适合采样点的 h 范围。

3) 是的，只要你觉得更容易。

4) 难点在于找到最佳步长。您可能希望在此处使用内部循环来搜索最佳步骤。