信任域算法的全局收敛

计算科学 优化 收敛 非凸的 信任区域
2021-12-17 19:41:14

我正在阅读有关 TR 方法的内容,其中有些术语让我感到困惑。

它说,方法是全局收敛的。它的真正含义是什么?收敛到全局最小值,或者肯定收敛到局部最小值,如果有的话?

感谢您的澄清!

1个回答

非线性(即基于导数)优化的标准术语是“全局收敛”意味着“无论您从哪里开始都收敛到一个固定点”(实际上限制可能取决于起点)。这与局部收敛形成对比,局部收敛要求您从足够接近静止点开始;如果您的初始点太远,则该方法根本不需要收敛。这是著名的牛顿方法的情况,另一方面(对于足够好的函数)二次收敛(即比最陡下降更快)。许多非线性优化都涉及在不破坏快速收敛的情况下试图摆脱对足够好的初始猜测(也称为“全球化”,其中一种方法是信任域方法)的要求。

原因是,如果您(仅)使用基于导数的算法,

  1. 不可能区分局部最小化器和全局最小化器(因为导数只携带局部信息),并且
  2. 一旦你到达一个固定点,定义上的导数就会消失,因此算法必须终止。

(该术语的另一个原因是,对于一大类实际相关的问题(凸问题),任何驻点实际上都是(全局!)最小化。)

相比之下,全局优化与实际计算全局最小化器有关(对于它,TANSTAAFL,收敛理论要少得多)。