algorithm - BFGS 对凸过参数化问题的收敛性

Question

“众所周知”BFGS优化算法对于严格凸问题是超线性收敛的，但是对于非严格凸问题是否有任何分析。例如，假设 f(x) 对于某个标量 x 是凸的。然后，假设我们优化 g(x1,x2)=f(x1+x2)。这仍然会一直是超线性收敛的吗？

Answer 1

BFGS 是否完全收敛于非凸问题仍然是一个悬而未决的问题。事实上，鲍威尔在 1984 年给出了一个反例，表明具有不精确线搜索搜索的 BFGS 可能无法收敛。可以做的是局部语句，例如：给定一个局部最小值 x*，如果你最终进入 x* 附近的空间区域，BFGS 将超线性收敛。这样做的原因是在 x* 附近，目标函数可以通过凸二次方程准确建模。

至于你给出的合成功能是什么，我不确定。有关 BFGS 属性的详细说明，请参阅 Dennis 和 Schnabel 或 Nocedal 和 Wright。

祝你好运。

Answer 2

如果我错了，请纠正我，但在这种情况下，“解决方案”实际上不是一条线，而不是一个点吗？如果 x' 是 f(x) 的最小化器，那么在对 g(x1, x2) 应用任何方法时，您所能期望的最好结果就是让它收敛到线 x2 = x' - x1。

Answer 3

在实践中，我发现精心编写的算法会收敛，但不一定是超线性的。舍入误差是罪魁祸首。收敛标准开始发挥作用。对于“几乎”非凸函数（即“僵硬”）也是如此。

必须小心 BFGS 更新，以确保得到的近似 Hessian 保持正定“足够”，即使理论上的 Hessian 不是。我所做的是保留和更新 Hessian 的 Cholesky 分解，而不是 Hessian本身或其逆。