本文讨论正则牛顿方法，这是一种灵活的无约束优化算法，与线搜索和信任域方法竞争，并可能结合两者的吸引元素。重点是利用有限内存算法的特殊结构，将正则化与有限内存拟牛顿方法相结合。在温和的假设条件下，证明了正则化方法的全局收敛性，并讨论了正则化有限内存拟牛顿更新的细节，包括它们的紧凑表示。使用CUTEst集合中所有大规模测试问题的数值结果表明，我们的正则化版本的L-BFGS与最先进的线搜索和信任区域L-BFGS算法以及之前将L-BFGS与正则化相结合的尝试相竞争，同时可能优于其中一些算法，特别是在涉及非单调性时。

设，为二次连续可微函数，并考虑非线性极小化问题

（1)

牛顿或准牛顿型方法通常被认为是解决这类问题的一些最有效的算法。给定当前迭代，这些方法通过求解形式的(拟)牛顿方程来计算迭代步骤

(2）

这里是黑森曲线或它的近似值。当n较大时，通常不显式存储矩阵。相反，人们使用所谓的有限内存准牛顿方法，它需要存储一些向量对

并利用这些信息构造一个隐式逼近黑森矩阵。这种近似从来没有明确地形成;相反，这些对用于直接计算形式为或的矩阵向量乘积。可以说最成功的准牛顿方案是Broyden-Fletcher-Goldfarb-Shanno (BFGS)方法[10]及其有限内存对应的L-BFGS[6,19,22]。其他的例子包括对称秩一(SR1)，鲍威尔-对称-布洛登(PSB)，戴维顿-弗莱彻-鲍威尔(DFP)，所谓的布洛登类等等;参见[10,18,31]。

在当今的优化领域，L-BFGS是平滑大规模优化的事实上的标准。该方法通常与直线搜索技术相结合，以确保全局收敛[19]。也有人致力于使准牛顿方法与信任域框架兼容;L-BFGS见[2,4,12]，L-SR1见[1]。大多数准牛顿公式都承认所谓的紧表示形式，这一事实有助于这一点

（3)

其中，和。(我们把instead of放在上面的等式中，因为这样以后会更方便。)初始矩阵通常是单位矩阵或其他对角矩阵的倍数。许多作者已经给出了上述形式的分解[3,6,9]，它们在优化方法中非常有用，因为它们通常允许计算涉及较低维数的矩阵运算。特别是，它们有助于准牛顿方向的有效计算和信赖域子问题的求解;请参阅上面的参考资料。

在本文中，我们将追求一种不同的全球化技术，它可以被视为线搜索和信任区域方法的兄弟(不太知名)，即所谓的正则化牛顿方法[15,17,29,30,32]。这些通常用正则拟牛顿方程的形式来表示

其中称为正则化参数。这些方法吸引人的特点是它们结合了线搜索和信任域方法各自的一些优点，而且它们与准牛顿矩阵的紧凑表示高度兼容。因此，我们将提出一个算法框架，旨在有效地结合有限的内存和正则化技术，具有以下好处:

• 步进计算几乎与线搜索L-BFGS算法一样便宜。更具体地说，每次成功迭代的成本(在m步BFGS的情况下)是4mn加上对称线性系统的解。特别是，计算特征值分解或信任域解时不需要内环。

• 同时，由于正则化参数模拟了信任域子问题中的拉格朗日乘子问题，该算法的步长质量接近于信任域型有限内存算法。因此，该方法可以看作是一种“隐式”信任域算法。

• 综上所述，接受步骤的比例非常高，导致函数和梯度评估的数量相对较少(与信任区域类型方法相同)，同时保留了线搜索方法的“廉价”步骤。

正则化技术的使用比行搜索方法有另一个重要的好处。在行搜索设置中，许多作者主张先尝试“全”步长，其动机是L-BFGS和类似方法本质上是牛顿型算法，全步长可能会导致快速收敛。然而，步长也用于使算法适应问题的非线性，并且在每一步重新初始化线搜索过程使得难以将该信息从一步传递到下一步。相比之下，我们在这里提倡的正则化方法在完整(拟)牛顿步和截断版本(类似于信任域方法)之间提供了更无缝的过渡，这表明这种类型的算法可能能够更有效地处理非线性或非凸问题。

将有限内存和正则化技术结合起来的想法并不是全新的。多位作者[15,26,28]主张修改准牛顿方法中的割线方程，以近似求和。然而，这些方法都没有充分利用Hessian的准牛顿近似和紧表示(3)。我们提出的方法充分利用了这些工具。

除了算法之外，本文还包含正则牛顿方法的一般收敛结果，据作者所知，在文献中不存在这种一般性。特别地，收敛结果不假设任何特定的拟牛顿公式，允许其不确定。这可能会引起该领域研究人员的兴趣，并为今后相关方法的研究提供基础。

本文组织如下。第2节包含了一类正则拟牛顿方法的详细描述。第3节在相当温和的假设下给出了这类方法的全局收敛结果。在第4节中，我们展示了如何利用有限内存准牛顿方法的紧凑表示来创建有效的算法实现。我们还给出了似乎是新的PSB公式的紧凑表示。第5节的数值实验表明，新技术与其他正则化L-BFGS的尝试[28]以及基于线搜索和信任域的L-BFGS方法[2,19]具有竞争力。我们在第六节中作最后的总结。

矩阵和向量将分别用黑体字和表示。给定一个矩阵，对于的严格下，对角线和严格上部分，我们分别写，和。特别是，它总是这样

平滑函数f在一次迭代中求值的梯度通常表示为。我们用对所有i都有无限索引集的子序列来表示序列，同样地，意味着收敛于s。

正如在引言中所讨论的，本文方法的基本原理是正则牛顿和准牛顿方法的基本原理，它们通常以形式的正则拟牛顿方程为特征

（4）

式中为黑森函数或其近似值，为正则化参数。显然，如果，则(4)化简为标准拟牛顿方程。另一方面，如果很大，则矩阵是可逆的，由(4)产生的步长本质上是负梯度方向(直到归一化;参见引理1)。

通过认识到这本质上相当于最小化正则化二次模型，可以理解正则化方法的优点

（5）

这与吉洪诺夫正则化的传统牛顿模型不同。因此，正值可以抑制负特征值对搜索方向的影响，防止在负曲率方向上的步长过长，并可能保证模型(5)存在唯一的最小值(即矩阵是正定的)。预期的设置是，最初将保持足够大以保证全局收敛，最终将迅速减小以不妨碍快速的局部收敛。

通过信任域方法给出了更严格的解释。确实，如果对于某些，并且如果，则是信任区域子问题的一个平稳点

在哪里

(6）

是f的标准二次逼近。如果是正定的，那么实际上就是这个辅助问题的一个解。因此，正则牛顿方法可以解释为“隐式”信任域方法，其中控制正则化参数而不是控制信任域半径。

最后，分析正则化技术如何影响二次模型的条件也是很有趣的(5)。假设目前是正定的(例如，在bfgs类型的方法中)，正则化参数在某种意义上改善了底层矩阵的条件数

的最大和最小特征值。

为了控制正则化参数，我们考虑f从(6)的二次逼近，并借用了信任域算法中的一些术语。给定一个候选步骤，定义f as的预测缩减量

（7）

最后一个等式用的是。(特别要注意的是，矩阵不需要用于计算。)这个量将与步骤k中实际的或实现的减少量进行比较，

（8）

与信任域方法[8]类似，我们使用这些量之间的比率来控制正则化参数。为此，我们区分了三种情况，不成功(u)，成功(s)和非常成功(h)的步骤。还需要特别注意，因为没有先验的肯定保证(因为可能是不确定的);这些步骤被当作不成功的步骤一样对待。

算法1(正则化拟牛顿法)

选择和参数;;;;．

步骤1:

如果满足合适的停止条件，则终止。

步骤2:

(步进计算)选择并尝试求解正则化拟牛顿方程

（9）

若无解，或设，，转到步骤4。否则，请执行步骤3。

步骤3:

(变量更新)设置并执行以下步骤之一:

步骤3u()。设置和。

步骤3()。设置和。

步骤3 h()。设置和。

步骤4:

设置完成后，执行步骤1。

步骤2中的条件是一个充分下降准则，类似于直线搜索方法中的角度条件或信任域方法中的柯西条件。该数量表示要尝试的步骤的目标值(相对于和)的最小期望减少。

如上所述，在接下来的内容中，如果一个步骤通过了步骤3u，或者由于步骤2中的检查而跳过了步骤3，我们将把它称为不成功的步骤。(特别是，可能不会在不成功的步骤中定义。)

这些参数用于对步骤进行分类并相应地调整正则化(如果步骤不成功则增加，如果步骤非常成功则减少)。

算法1与信任域方法密切相关。信任域方法和正则化框架的主要区别在于参数的更新。前者使用一种间接的方法来计算(通过信任区域半径)，而这里我们直接更新正则化参数。虽然间接更新遵循一个很好理解和良好动机的哲学，但它的实际计算有时是耗时和昂贵的。因此，我们期望直接更新的优越行为，特别是对于大规模问题。

该报告[28]提出了一种形式上与算法1几乎相同的方法(除了正则化参数的更新略有不同)。主要区别在于[28]关注的是由有限内存BFGS方案更新的矩阵(不使用紧凑表示，我们将在第4节中使用)。[28]中的收敛理论假设有界水平集条件;这在我们的后续分析中是不需要的，因为我们只假设有界性(允许其他准牛顿公式或不确定性)和目标的有界性(考虑，例如，指数函数)。

摘要
1 介绍
2 正则化拟牛顿方法
3.一般的公司 nvergence分析
4 正则拟牛顿矩阵
5 数值实验
6 最后的评论
数据可用性声明
代码的可用性
参考文献

作者信息
道德声明



搜索
导航

#####

正如我们将看到的，算法1为准牛顿类型更新的应用提供了一个强大的框架。在开始这个讨论之前(这是本文的主要动机)，我们将把本节专门用于一个简单的收敛分析。由于该算法一般形式的非特异性，便于在较一般的假设下进行收敛性分析。为此，我们将不对矩阵的特定选择作任何假设，这些矩阵可能是也可能不是黑森矩阵的近似。我们在本节中所做的唯一假设如下。

(有界性)是有界序列。

大多数实际相关的拟牛顿方案都不存在满足上述假设的问题，特别是当梯度在适当的水平集中是Lipschitz连续时。事实上，许多这些技术产生的Hessian近似满足额外的性质，如对称性(我们省略了，因为它对下面的理论是不必要的)或正确定性。

(梯度近似)设假设1成立，令。在足够大的情况下是可逆的

上述结果更精确地定义了第2节中提到的直观关系;即，如果正则化参数足够大，则正则化牛顿方程(9)有唯一解，得到的矢量近似负梯度方向为。

引理1的另一个结论是，该方法执行了无限多个成功步骤。这是由于当的时候变得越来越小，并且趋近于(局部)最陡下降方向，从而产生一个局部下降步长，该步长满足算法第2步的充分减小条件。

(定义良好)设假设1成立，并假设对于所有k，则算法1执行了无限多个成功或高度成功的步骤。

为了矛盾起见，假设存在这样的情况，即所有步骤都不成功。特别地，这意味着作为和为所有人。由于是一个有界序列，由引理1可知，对于足够大的k是可逆的，即，和。而且，正则化牛顿方程(9)表明。从这些极限关系很容易推导出

(只需将这个不等式除以并回忆一下)。因此，算法最终必须只执行步骤3u，这意味着对于所有足够大的。接下来就是

（10）

不等式两边同时除以。回想一下，左边就变成了

(11)

反过来，回想一下，(10)的右边除以满足

（12）

因为，从(11)(12)可以得出，一个矛盾。

下面的结果建立在该算法的良好定义的基础上，并表明它达到了渐近平稳。

(全局收敛I)设假设1成立，设f从下有界，由算法1生成。然后

特别地，给定任意，算法在有限次迭代后终止于。

让它成为成功或非常成功步骤的一组指标。注意，根据引理2。为了避免矛盾，假设

（13）

由于每一步都是成功的，根据定义，我们有

根据(13)，所有的人都有这样的存在。利用f从下有界的事实，我们得到

(14)

特别是……既然每一步都是成功的，我们就有了所有。这意味着不能有有界子序列[因为它和(13)一起违反]。因此,。特别是，该算法还执行无限多不成功的步骤(即)，并且在不成功的迭代期间不能减少。

现在，由于和是无限的，我们可以选择一个无限集，使得无论何时。由于在不成功的步骤中没有更新，由式(14)可知

因此是柯西序列，因此是收敛的。表示它的极限点。特别地，我们得到;因此，像在引理2的证明中那样使用和论证，可以得出，对于足够大，步骤一定是成功的。这是一个矛盾。

注意，定理1的对应物也适用于同一组假设下的信任域方法。此外，这里使用的证明技术与已知的信任区域方法的相应证明技术相关。然而，我们强调，在将标准的可信区域证明转换为我们的正则化框架时必须小心，因为在我们的情况下，可信区域子问题解的众所周知的性质可能不成立。

与信任域方法理论类似，我们可以利用定理1在附加假设下得到更强的收敛结果。

(全局收敛II)设假设1成立，设f从下有界，由算法1生成。假设它在满足的集合上是一致连续的。然后;的每一个累加点都是f的一个驻点。

假设存在且存在子序列

因为根据定理1，我们可以找到，对于每一个索引

对于任意且成功或高度成功的迭代，我们得到

同样的不等式也适用于我不成功，因为在这种情况下。这意味着

对所有人来说。由于f从下有界且单调递减，我们得到。这意味着。在集合X上的一致连续性因此产生

另一方面，索引的选择意味着

这个矛盾完成了证明。

在结束本节时，我们注意到算法1中的正则化技术有时用于证明牛顿型方法的局部快速收敛性质。这对应于作为确切的黑森的选择。使用更精细的正则化参数更新，假设局部误差界条件和f的Hessian为局部Lipschitz连续，可以验证凸目标函数的局部二次收敛性，参见[17,29,30]。由于我们的重点是大规模的问题，我们的后续分析集中在有限内存的准牛顿矩阵计算。

本节提供准牛顿方法的有限内存类型实现的细节。下面的一些材料可以以最小的修改应用于全内存准牛顿方法，但由于我们关注大规模优化，我们放弃了这些研究。

为了与传统的有限内存符号保持一致，我们假设一个算法框架，其中最后m个变量步与相应的梯度差一起被跟踪，我们回忆一下。为了方便标记，我们将这些集合到矩阵中

如果可用的先前迭代少于m个，即If，则设置

这些定义看起来似乎只是符号的问题，但实际上有相当实用的论据，为什么和应该被视为矩阵而不是向量的集合。许多有限的内存操作可以表示为循环索引上的循环，而矩阵表示法有时允许我们将底层计算表示为矩阵-向量操作(而不是向量-向量操作序列)。在实际实现中，只要有可能，就应该使用这种方法，因为它利用了低级BLAS(基本线性代数子程序)和并行性的能力，从而显著提高了计算效率。

(拒绝准牛顿更新)为了简单起见并避免符号开销，我们假设算法在每次成功迭代中总是“接受”数据对。对于某些拟牛顿格式，特别是对于非凸目标函数，则不是这样。一般来说，准牛顿更新通常使用所谓的谨慎更新方案接受或拒绝(见第5节);当一对被拒绝时，前面步骤的矩阵简单地保持原样。

大多数有限内存的准牛顿方法隐式地生成所谓的紧凑表示形式

(15)

式中为非奇异对称矩阵，，是依赖于特定拟牛顿格式的常数。例如，在有限内存中的BFGS方法，以及在有限内存中的SR1。

上面的表示为正则化方法提供了一个非常方便的框架:给定一个参数(例如，算法1中的一个值)，正则化的Hessian近似可以写成

这有利于应用低秩更新公式来明确而廉价地计算正则牛顿步长。为此，让和。那么谢尔曼-莫里森-伍德伯里公式意味着

（16）

只要它是非单数的。注意，这通常是一个对角矩阵，它的逆是微不足道的。而且，内矩阵的大小，使得它相对于维数n的反演可以很便宜地进行。通过Woodbury矩阵恒等式，这个内矩阵的可逆性等价于的可逆性。

在下文中，我们主要假设初始矩阵是单位矩阵的标量倍。然后是写作

(17)

准牛顿方法的实际效率很大程度上取决于先前计算量的记忆和重用。为此，观察拟牛顿递归式所暗示的

（18）

在哪里

（19）

因此，主要的计算成本发生在形成乘积，获得对称线性方程的解，以及乘积。此外，矩阵和需要在每次迭代中更新，并且矩阵需要可用。正如我们稍后将看到的，可以通过使用底层公式之间的固有依赖关系来减少这些计算的成本。

(正则化割线方程)代替紧凑的表示，也可以通过直接逼近和来结合正则化和准牛顿技术;参见[28]。这个想法是基于这样一个事实，即正则化的Hessian(近似地)满足修正的sec方程

因此，可以通过对修改后的初始猜测和对修改后的对应用任意拟牛顿格式来构造对的近似。对于某些准牛顿方案，如SR1和PSB，这实际上与基于紧凑表示的方法产生相同的结果(参见第4.2节，4.3节)。但总的来说，这两种方法是不同的。

BFGS的更新通常被认为是最成功的准牛顿方案。在本节中，让我们来看一些。下[6]，L-BFGS的紧化表示为

（20）

在哪里

(21）

(回想一下，它表示给定矩阵的对角线部分和严格的下三角形)。通过定义，可以写成(15)的形式

(22)

注意这一点。

BFGS公式有一个显著的优点，即可以控制更新的良好定义。更具体地说，假设对于所有k，可以证明BFGS矩阵是正定的，因此正则化的BFGS矩阵也是正定的，因此是非奇异的。根据Woodbury矩阵恒等式，这意味着(17)中的内矩阵是可逆的，因此正则牛顿阶跃对所有矩阵都是定义良好的。

在实践中，定义的良好性是通过所谓的谨慎更新机制来控制的[16]。以前有限的内存数据只有在下一对中更新

（23）

其中是某个预定义的常数。这保证了L-BFGS矩阵是一致正定的。如果在迭代集(或适当的水平集)上Lipschitz连续，则(23)也保证它是有界的。

以下4.4.1更新L-BFGS信息

我们现在描述如何以有效的方式更新L-BFGS信息。为了避免重复，我们只描述以前的信息已经“完整”的情况，即至少有m个以前的数据对可用。处理初始步骤所需的修改基本上相当于重新编制索引，这里不再详细说明。

正则化L-BFGS的大部分计算工作量可以通过记忆某些中间结果来减轻。受[2]中相关信任区域方法的启发，我们除了跟踪矩阵和数量外，还跟踪数量

这两个量对于正则化拟牛顿步(18)、(19)的计算都是必需的，但它们也会出现在迭代和更新过程的其他地方，因此记住它们可以节省冗余的计算量。回想一下，特别是这个

因此，矩阵包含块，，和from(22)作为子矩阵。

当从k传递到时，这些矩阵和向量可以更新如下。如果数据对被拒绝，则保持不变，我们可以直接计算更新。如果数据对被接受，那么更新过程需要更加小心，因为两者都需要递增。在这种情况下，新矩阵和分别由旧矩阵和的最后一列组成，新向量和被附加在最后一列中。然后我们开始计算向量

(24)

式(19)给出;以及标量。然后使用该信息使用公式进行块更新

(25a) (25b) (25c)

其中“”由对称给出，形式为或的表达式表示由下标索引范围构建的子矩阵和-向量。最后，我们有，根据定义，这个新向量等于。

4.1.2 Computatio部分的复杂性

现在让我们评论一下正则化拟牛顿步的计算所涉及的复杂性。假设乘积已经形成，其主要代价是解一个对称的线性系统形成，并与矩阵相乘。因此，正则化拟牛顿方程的复杂性是乘法。

当一个步骤成功时，需要根据上面开发的公式更新现有数据。它的主要成本是200万次乘法的计算。因此，对于一个不成功的步骤，总体计算工作量最多为200万次乘法，而对于一个成功的步骤，则最多为400万次乘法。

的线性方程(19)的计算代价为阶。因此，如果，这个成本与mn相比可以忽略不计。通过使用的Schur补将反演简化为两次Cholesky分解，可以进一步减轻由该线性方程引起的轻微计算开销。参见[4]了解更多细节。

对于SR1，紧凑表示采用如下形式

（26）

式中，又由式(21)给出。通过定义，可以写成(15)的形式

(27)

注意，在这种情况下。

如果，则(26)可化简为

(28)

在实践中很难保证SR1更新的良好定义，因为底层的排名1公式涉及到形式的分母，它可能会消失。因此，当将公式(16)应用于SR1设置时，澄清如何处理这种情况是很重要的。请注意，不可能预测哪些新数据可能导致条件反射不良，因为这在很大程度上取决于先前的信息。事实上，即使在迭代过程中的某些时候丢弃旧数据也可能会影响并改变SR1更新的良好定义。

幸运的是，有一种简单而有效的方法可以“在飞行中”跳过病态更新，即在准牛顿步骤的计算过程中。这实际上相当于在必要时跳过中间步骤，而是使用。在[6]中观察到，这些更新中的一个的不定义性相当于的主次的奇异性，或者等价地，在的三角化过程中消失的枢轴元素。当发生这种情况时，[6]建议跳过更新，本质上忽略的当前行和列，以及的当前列(其中包含相应的向量和)。

通过观察SR1更新在某种意义上与正则化“交换”，上述过程可以适应正则化SR1设置。更具体地说，如果表示SR1更新，则

对于所有，只要左边存在。此外，一个简单的计算表明，(16)中的矩阵在正则化牛顿步长计算中需要被反转，与对应的SR1更新将产生的模拟相吻合(直到缩放)。

4.2.1 更新L-SR1信息

L-SR1计算中涉及的量可以以与L-BFGS情况类似的方式更新;见4.1节。我们再次保持数量不变

(29)

这些可以像以前一样形成和更新。此外，它们还可以直接构成矩阵和、乘积和矩阵。

4.2.2 Computatio部分的复杂性

正则化L-SR1方法的计算代价如下:在每次成功迭代中，更新数量(29)，并形成矩阵。使用4.1节的技术，这些操作需要3百万次乘法。

此外，每一步都需要计算准牛顿步，这需要一个对称线性系统的解来获得，并与矩阵相乘，需要另外进行mn次乘法。

因此，一个成功步骤的总成本为400万次乘法，而一个不成功步骤的成本为mn次乘法(低于BFGS的200万次)。

作为第三个例子，我们引用了经典的PSB公式[25]。这种方法很有趣，因为PSB更新总是定义良好的，并且具有某些众所周知的最小化属性。PSB更新由

（30）

下一个定理给出了PSB的紧表示。

请注意，在[3]中有一个多点割线版本PSB的相关表示。这两种表述同时出现在。

(PSB的紧凑表示)PSB公式允许紧凑表示

（31)

式中，为的(非严格)上三角部分，为的严格下三角部分，为的对角部分。

为了简化一些技术细节，我们将证明限制在以下情况下(即，算法执行了恰好m步，并且矩阵和是“满的”)。首先观察(30)可以改写为

因此，我们可以写，其中都是通过公式递归定义的

i.现在观察到，通过[6,Lem. 2.1]，所以

我们用(有限)归纳法来证明这一点

(32)

在哪里和。在我们验证这个公式之前，我们将展示它产生PSB公式所需的紧凑表示。实际上，分别使用(32)和矩阵的定义，我们得到

另一方面，利用这个事实

使用(31)并展开，很容易看出我们得到了相同的表达式。

因此，仍然需要用归纳法来验证(32)。因为，我们有

同时观察到

(33)

初步计算表明(32)成立。假设这个命题对某些人是成立的。将归纳假设与(33)结合使用，一个简单的计算表明

另一方面，让我们计算表达式(32)。基于分区

我们获得

因此

使用这些表达式，将(32)展开，将i替换为，并再次考虑的定义，初等计算表明，得到的矩阵与前面得到的矩阵一致。归纳就完成了。

如果对于某些，则(31)可以重写为

(34)

和以前一样。这种形式的优点是所有涉及的量都可以作为乘积的子矩阵得到。

4.3.1 更新和复杂性

如前所述，L-PSB数量可以以与L-BFGS情况类似的方式更新;见4.1节。我们再次保持数量不变

(35)

这些可以像以前一样更新，并通过反式(16)用于计算准牛顿方向。L-PSB步骤的复杂度与L-BFGS步骤相当。

这里描述的基准测试实现可以在http://k1.fpubli.cc/file/upload/202308/17/nsjxwvyyzsj上找到。[27]。

在本节中，我们比较了正则化拟牛顿方法(算法1)之间的选择，并与文献中现有的L-BFGS型线搜索和信任域算法进行了比较。

算法在CUTEst集合中的所有大规模()问题上进行测试[14]。在Python3中使用PyCUTEst接口实现[13]。所有问题都是用库提供的初始点计算的。我们排除了所有算法在100,000次迭代阈值内失败的测试问题(见下文)。我们还省略了FLETCBV2，因为初始点是一个静止点。经过这些考虑后的最终测试集由77个问题组成。

使用基于函数评估次数的性能概况[11]来比较不同算法的结果。注意，正则化方法在每个成功或不成功的步骤中只对函数求值一次，因此函数求值的次数等于迭代的次数。此外，除了函数或梯度评估之外，所有测试的方法每一步的计算复杂度都相似(见[2,19]和第4节)，因此函数评估提供了一个简单而有意义的基线度量。

注意，我们在比较中没有考虑梯度评估;正则化方法(以及5.2节中的信任区域比较方法)在每次成功迭代中精确评估一次，而基于wolfe的线搜索方法在内线搜索循环中评估。因此，考虑梯度评估将使我们的许多方法在随后的比较中受益。然而，为了简单起见，我们避免了更细粒度的分解，只关注函数求值。

每当一个算法不能在允许范围内解决特定问题时(见下文)，函数求值的次数被设置为，以便进行比较。

我们实现了以下四种基于正则化的算法:

regLBFGS:：

算法1使用第4.1节所述的L-BFGS技术;

regLBFGSsec:：

算法1使用正则化割线版本的L-BFGS，如在注释2中讨论(参见[28]);

regLSR1:：

算法1使用第4.2节所述的L-SR1技术;

regLPSB:：

算法1使用第4.3节所述的L-PSB技术。

所有实现都使用相同的超参数

（36）

为了保证良好的定义，regLBFGS和regLBFGSsec使用谨慎的更新方案(23)来实现。regLSR1和regLPSB算法得益于不定Hessian近似[5,7]，因此没有与谨慎更新方案相结合。然而，对于这些方法，仍然采用谨慎方案来更新滚动初始近似(37);见下文。

受[2]中的一种技术的启发，所有算法在主迭代循环之前，都从沿着归一化负梯度方向的单个mor - thuente线搜索开始(详细信息参见5.2节)。这样做的好处是提供了一个通过谨慎更新检查(23)的初始内存对，并减少了任何初始回溯对迭代数的影响。

算法被终止了

步骤k中的初始估计由标准公式定义

（37)

此外，我们对正则化参数采用了较低的阈值。这改善了该方法的实际性能(特别是在L-BFGS情况下)，并且还防止了正则化参数在有限精度算法中变为零(图1)。

似乎上述选择导致高正则化参数优于低正则化参数，因此可能阻碍快速渐近收敛。我们的经验发现，当正则化参数变化不频繁时，算法1(使用L-BFGS)通常表现最好。这表明该参数应在必要时急剧增加(以避免重复增加)，只有在步进质量非常好的情况下才减少。这反映在我们对参数的选择上。

还要注意，有限内存的方法很少实现实际的超线性收敛;典型的行为是渐近线性的[19]，非精确牛顿方法的经典结果(例如[23,Thm. 7.1])表明，较小但不衰减的值通常会保持线性收敛。这表明，从理论的角度来看，这里做出的选择是合理的。

其他论文[2,28]中的可比研究表明，正则化方法可能受益于非单调性策略。因此，为了获得更大的数据集，我们还实现了所有算法的非单调版本，其中被选为非单调偏移量;通过替换正则化控制(8)和行搜索例程中的参考值，将其纳入方法中。最初的步骤没有经过修改。

基于5.1节中四种算法的函数评估数量的性能概况:单调情况(左)，非单调情况(右)

基于5.1节中四种算法的函数评估数量的性能概况:单调与非单调(索引n)算法

图2说明了单调和非单调实现的相对行为。所有算法似乎都受益于非单调性策略。应该强调的是，我们选择这种战略相当简单，但我们认为这足以说明总体情况。

总而言之，L-BFGS被证明是迄今为止最有效的准牛顿方案，即使是在正则化的背景下。L-SR1和L-PSB的正则化变体具有中等竞争力，但总体性能不及regLBFGS和regLBFGSsec。

我们在测试过程中观察到的一个有趣现象是，L-SR1，特别是L-PSB在使用更“乐观”的正则化方案(即更低的正则化参数)时实际上效率更高。这有点令人惊讶，因为这些方法产生不确定的Hessian近似，直观地说，应该从正则化中获益最多;另一方面，L-BFGS生成的近似值无论如何都是正定的，这表明这里可能不太需要正则化。我们观察到的数值证据与这种直觉相矛盾。

对于这一现象，我们只能给出部分的解释。众所周知，BFGS和L-BFGS与经典共轭梯度法有关[21]，这表明L-BFGS在连续搜索方向上施加了某种关系(广义的“共轭”)(参见[2,Eq. 65]之后的讨论)。我们不知道这种性质的严格定义，但是当L-BFGS与不频繁变化的正则化参数一起使用时，连续搜索方向的关系可能以某种方式保留。另一方面，L-SR1和L-PSB通常被认为可以生成更精确的精确Hessian近似(特别是当它是不确定的)，这表明这些方法的行为更类似于传统的牛顿算法，因此受益于更快地减少正则化参数。

正则化的割线版本regLBFGSsec很有趣，因为它实现起来相当简单(通过使用标准的双循环递归)，但它的鲁棒性与regLBFGS相当;见图1。

最后，表1显示了所有四种基于正则化的算法的可接受步骤的比例和已解决问题的总数。L-BFGS算法以其解决的问题数量多而突出，在非单调情况下的接受率约为99%。有趣的是，在单调的情况下，regLPSB的接受率达到了99%左右，而在非单调的情况下，接受率逐渐下降到72%左右。

现在让我们根据文献中可用的相关算法来测量regLBFGS。我们使用的“参考”算法是:

armijoLBFGS:：

采用Armijo线搜索和谨慎更新方案的普通L-BFGS方法(23);

wolfeLBFGS:：

基于mor<s:1> - thuente线搜索的L-BFGS方法[19];

eigLBFGS:：

[2]中EIG信任区域L-BFGS算法的稍微简化版本。

Armijo搜索使用标准回溯，反复将步长减半，直到

这里是准牛顿阶跃。mor - thuente线搜索使用Diane O 'Leary[24]的实现，翻译成Python。它终止于

eglbfgs算法基于可在https://gratton.perso.enseeiht.fr/LBFGS/index.html上获得的EIG实现。为了使比较公平，我们略微简化了该算法，将EIG的两阶段初始线搜索替换为沿着归一化负梯度方向的单个mor - thuente搜索(这与正则化方法的实现一致;见5.1节)。此外，EIG的停止准则、谨慎更新机制和信任域控制参数与其他实现保持一致。

regLBFGS基于函数评估次数的性能概况和5.2节中的三种算法:单调情况(左)，非单调情况(右)

注意，[2]中EIG算法的非单调实现不可用，因此我们将其排除在相应的比较之外。

本节中的算法都使用停止准则

取决于算法是线搜索还是信任区域类型。其中，为线搜索步长，表示信任域半径。

图3展示了上述三种算法和regLBFGS的性能。带有mor - thuente线搜索的L-BFGS算法[20]在最快的问题上具有竞争力。然而，与[2]的结果相似，我们发现这种算法和类似的基于Wolfe-Powell的算法的效率明显低于其他算法，因为函数评估的次数过多。

regLBFGS和egiglbfgs在单调情况下的表现非常相似，其中egiglbfgs(基于[2]的算法)具有轻微的优势。这并不完全令人惊讶，因为正则化可以看作是信任域算法的近似。反过来，eglbfgs需要在每次迭代中进行(低维)特征值分解，而regLBFGS只求解对称线性方程。

基于regLBFGS的函数评估数量和第5.2节中的三种算法的性能概况:单调与非单调(索引n)算法

图4比较了单调和非单调算法的行为。regLBFGS的非单调版本似乎优于eglbfgs和armijoLBFGS和wolfeLBFGS的非单调版本(见图3)。

再次注意，我们上面的比较完全基于函数求值，而不是CPU时间。对CPU时间进行分析可能会很有趣，但这实际上需要另一种编程语言，因为在Python或MATLAB等语言中缺乏优化编译，这会在循环和重复赋值操作上产生巨大的开销。我们预计实际的CPU时间将略微有利于直线搜索L-BFGS方法，因为正则化方法中与有限内存更新相关的逻辑努力(参见第4.1节)。

最后，表2显示了本节中所有算法和regLBFGS的接受步骤和解决问题总数的平均比率。基于插值的mor - thuente线搜索在单调和非单调实现中获得了约95%的接受度。不出所料，基于信任域的eglbfgs算法在单调情况下获得了最高的接受率。在非单调情况下，regLBFGS再次以99%的接受度脱颖而出。

(进一步的改进)将进一步的修改和改进纳入正则化拟牛顿方案是可能的，但为了便于公平的比较，我们放弃了这样做。例如，在被拒绝的步骤中更新准牛顿信息可能是有益的，因为试验函数值和梯度提供了有意义的信息[28]。注意，这个技术被算法1的框架所覆盖，因为我们允许在每次迭代中重新选择。

下载原文档：https://link.springer.com/content/pdf/10.1007/s12532-023-00238-4.pdf