牛顿法的线搜索

计算科学 优化 非线性规划
2021-12-08 09:28:55

如果我们要解决非线性最小化问题

minxf(x),

做出最小二乘假设并使用 Gauss-Newton 方法,以便在第 k迭代时我们有:th

JkTJkpk=JkTrk,

向量为残差,矩阵雅可比矩阵。rJ

然后我们通过以下方式更新x

xk+1=xk+αpk,

其中α(0,1]

问题是如何找到使得αf(xk+1)=min

换句话说,考虑到计算成本高且高度非线性,什么样的步长计算策略足够好?ff

我知道用多项式近似这个问题的方法,例如在二次近似的情况下:

p0+p1α+p2α2=min

其中p0=f(xk),p1=f(xk),p2=f(xk+αpk)

但我想知道还有哪些其他选择可以尝试?有人可以指出一个很好的概述或简短地写下不同的技术。

2个回答

Nocedal 和 Wright 关于非线性优化的优秀著作对此进行了详细讨论。我无法比他们描述的更好地总结该方法。

流行的、易于实现的线搜索策略是加倍和回溯,但它们通常需要比严格需要的更多的函数值。您描述的插值方案需要有效的保障措施,但所有(或至少大多数)当前使用的方案都基于某种形式的插值。

最常用的高质量线搜索(执行 Wolfe 条件)是 More 和 Thuente 的一种,http://www.mcs.anl.gov/research/projects/tao/src/linesearch/impls/morethuente/morethuente.c 它使用受保护的三次 Hermite 插值,并附有彻底的理论分析。http://www.ii.uib.no/~lennart/drgrad/More1994.pdf