非凸优化问题的两步正则化牛顿法

The Two-Step Regularized Newton Method for Non-Convex Optimization Problems

摘要: 本文提出了非凸的无约束优化问题的一种在信赖域框架下的两步正则化牛顿算法，其在适当条件下证明了该方法具有局部收敛性。在局部误差界的条件下，该方法具有三阶收敛速度。此外我们还进行了数值实验，数值结果显示，与单步正则化牛顿法相比我们有更少的迭代次数更快的迭代速度，说明两步正则化牛顿法比后者更有效。

Abstract: In this paper, we propose a two-step regularized Newton algorithm for solving non-convex uncon-strained optimization problems within the trust region framework. Under appropriate conditions, we prove that this method possesses local convergence. Under the condition of a local error bound, the method exhibits third-order convergence rate. Additionally, numerical experiments are con-ducted, and the results show that our two-step regularized Newton method outperforms the sin-gle-step regularized Newton method in terms of fewer iterations and faster convergence speed, in-dicating its higher efficiency.

1. 引言

本文主要考虑如下的优化问题

$\underset{x\in R^n}{\min }f\left(x\right)$ (1)

其中 $f:R^n\to R$ 是二次连续的可微函数。牛顿法是求解问题(1)的经典算法之一，其具有如下的迭代格式：

$x_{k+1}=x_k-{\left[{\nabla }^{2}f\left(x_k\right)\right]}^{-1}\nabla f(\; x\; k\; )$

其中 $\nabla f\left(x^k\right)$ 为一阶梯度， ${\nabla }^{2}f\left(x^k\right)$ 为二阶海瑟矩阵。

牛顿法是求解问题(1)的经典方法，他的突出特点是：当初始点离最优解较近且目标函数在最优处的Hessian阵非奇异而且在最优解附近的Hessian矩阵满足Lipschitz条件时，经典牛顿法具有快速的二次收敛速度，收敛速度快是牛顿法的显著特点。但是当初始点的选择离最优点较远的时候，牛顿法可能不收敛，通常采取正则化来保证牛顿法的全局收敛性。此外，当Hessian矩阵奇异的时候，牛顿法无法使用。2001年Yamashita和Fukushima [1] 证明了当 $\Vert \nabla f\left(x\right)\Vert$ 在问题(1)的最优解 $x^{*}$ 的领域内，在提供局部误差界的假设下，证明了求解非线性方程组的Levebverg-marquardt方法在比非奇异假设更弱的局部误差界的条件下仍然具有局部的二次收敛速度。因此，研究在比Hessian阵非奇异假设更弱的局部误差界条件下牛顿算法有着研究价值，本文将进一步研究求解非凸优化问题的两步正则化牛顿法。

对于奇异凸优化问题，2004年Li [2] 等人通过近似计算如下线性方程组得到搜索方向 $d_k$ ：

$\left(G_k+{\mu }_{k}I\right)d_k+g_k=r_k,\Vert r_k\Vert \le \alpha {\mu }_k\Vert d_k\Vert .$

其中 ${\mu }_k=C\Vert g\left(x_k\right)\Vert$ ，Li等人证明了该算法在求解奇异凸优化问题时具有全局收敛性并且在局部误差界的条件下其仍具有二次收敛速度。

2009年Ueda和Yamashita，在文献 [3] 中对Levebverg-marquardt正则化进行了推广，当目标函数f是非凸函数的时候，使用Armijo步长规则，设 $x_k$ 为第k个迭代点，将梯度 $\nabla f\left(x^k\right)$ 和二阶海瑟矩阵 ${\nabla }^{2}f\left(x^k\right)$ ，分别用 $g_k$ 和 $H_k$ 表示，令正则化参数 ${\mu }_k=c_1{\psi }_{k}I+c_2{\Vert g_k\Vert }^{\delta }I$ ，其中， ${\psi }_k=\max \left(0,-{\lambda }_{\min }\left(H_k\right)\right)$ ， $\lambda$ 为矩阵 $H_k$ 的特征值， $d_k=-{\left(H_k+c_1{\psi }_{k}I+c_2{\Vert g_k\Vert }^{\delta }I\right)}^{-1}$ 为下降方向， $0<\delta <1$ ，并证明了该算法在适当的条件下有着全局收敛性，并且具有超线性收敛速度，并加以延申，当 $f\left(x\right)$ 是强凸的且 $\delta =1$ 时该方法二阶收敛。

Homeier在文献 [4] [5] 里根据牛顿法提出了一种改进的牛顿法——两阶段牛顿法，算法如下：

$\{\begin{array}{l}{y}_n=x_n-F^{\prime }{\left(x_n\right)}^{-1}F\left(x_n\right),n\ge 0,x_0\in D;\\ x_{n+1}=x_n-F^{\prime }{\left(z_n\right)}^{-1}F\left(x_n\right),z_n=\frac{x_n+y_n}{2},\end{array}$

用以解决具有F-可导的非线性方程 $F\left(x\right)=0$ 的近似解问题，其在特定的情况下有着全局收敛性以及局部收敛性，为我们提出两步牛顿法提供了理论支持。

Zhou和Chen在文献 [6] 中提出了一个基于凸函数无约束优化问题的两步正则化牛顿法，

$\left(G_k+{\lambda }_{k}I\right)d=-g_k,$

$\left(G_k+{\lambda }_{k}I\right)\bar{d}=-g\left(y_k\right),y_k=x_k+d_k,$

$x_{k+1}=x_k+s_k,$

该方法结合了正则化牛顿法与信赖域方法，通过证明该算法求解凸的无约束优化问题在具有全局收敛和局部误差界的条件下具有三次收敛速度。

根据上述研究，我们发现凸函数的收敛性讨论的较多，而非凸函数的讨论较少，而关于非凸函数的无约束优化问题的两步正则化牛顿算法国内外研究还是甚少，所以本文将对此进行研究并去证明他的有效性，具有全局收敛性且是具有三阶收敛速度的。

2. 非凸优化问题的两步正则化牛顿法

首先，f是 $R^n\to R$ 的非凸函数且二阶连续可微，将梯度 $\nabla f\left(x^k\right)$ 和二阶海瑟矩阵 ${\nabla }^{2}f\left(x^k\right)$ ，分别用 $g_k$ 和 $H_k$ 表示。用 $\Vert .\Vert$ 表示2-范数。

该正则化牛顿法主要方案如下，在每次迭代中，求解如下方程：

$\left(H_k+{\lambda }_{k}I\right)d=-g_k,$ (2)

得到牛顿步长 $d_k$ ，其中 $c_1>1$ ， ${\lambda }_k$ 为合适的正则化参数，有：

${\lambda }_k=c_1{\psi }_k+c_k\Vert g_k\Vert .$

${\psi }_k=\max \left(0,-{\nu }_{\min }\left(H_k\right)\right).$

$\nu$ 为矩阵 $H_k$ 的特征值。

再求解：

$\left(H_k+{\lambda }_{k}I\right)d=-g\left(y_k\right),y_k=x_k+d_k,$ (3)

得到的近似的牛顿步长 $\overline{d_k}$ 。

设 $d_k$ 和 ${\bar{d}}_k$ 由(2)和(3)给出，因为 $H_k+c_1{\psi }_{k}I+{\lambda }_{k}I$ 正定，因此 $d_k$ 是 $f\left(x\right)$ 在 $x_k$ 处的下降方向，但 $d_k+{\bar{d}}_k$ 可能不是，下面我们来讨论其是否为下降方向。

我们定义实际减少为：

$Are{d}_k=f\left(x_k\right)-f\left(x_k+d_k+{\bar{d}}_k\right).$ (4)

称为在第k次迭代时 $f\left(x\right)$ 的实际减少。

我们记牛顿步长 $d_k$ 为下列问题的极小值，

$\underset{d\in R^n}{\min }{\phi }_{k,1}\left(d\right)=\frac{1}{2}{d}^{\text{T}}{H}_{k}d+g_k^{\text{T}}d+\frac{1}{2}{\lambda }_k{\Vert d\Vert }^2.$ (5)

令：

${\Delta }_{k,1}=\Vert d_k\Vert =\Vert -{\left(H_k+{\lambda }_{k}I\right)}^{-1}{g}_k\Vert .$

由 [7] 知， $d_k$ 也是如下最值问题的解：

$\underset{d\in R^n}{\min }\frac{1}{2}{d}^{\text{T}}{H}_{k}d+g_k^{\text{T}}d,\text{s}\text{.t}\Vert d_k\Vert \le {\Delta }_{k,1}.$ (6)

根据 [7] ，得：

${\phi }_{k,1}\left(0\right)-{\phi }_{k,1}\left(d\right)\ge \frac{1}{2}\Vert g_k\Vert \min \left\{\Vert d_k,\frac{\Vert g_k\Vert }{\Vert H_k\Vert }\Vert \right\}.$ (7)

仿照 $d_k$ ，根据相似的式子也定义了 ${\bar{d}}_k$ ，

$\underset{d\in R^n}{\min }{\phi }_{k,2}\left(d\right)=\frac{1}{2}{d}^{\text{T}}{H}_{k}d+g{\left(y_k\right)}^{\text{T}}d+\frac{1}{2}{\lambda }_k{\Vert d\Vert }^2.$

${\bar{d}}_k$ 为下列信赖域问题的解，

$\underset{d\in R^n}{\min }\frac{1}{2}{d}^{\text{T}}{H}_{k}d+g{\left(y_k\right)}^{\text{T}}d,\text{s}\text{.t}\Vert d_k\Vert \le {\Delta }_{k,2}.$

其中：

${\Delta }_{k,2}=\Vert {\bar{d}}_k\Vert =\Vert -{\left(H_k+{\lambda }_{k}I\right)}^{-1}g\left(y_k\right)\Vert .$

我们有，

${\phi }_{k,2}\left(0\right)-{\phi }_{k,2}\left(d\right)\ge \frac{1}{2}\Vert g\left(y_k\right)\Vert \min \left\{\Vert \Vert {\bar{d}}_k\Vert ,\frac{\Vert g\left(y_k\right)\Vert }{\Vert H\left(y_k\right)\Vert }\Vert \right\}.$ (8)

我们定义预测减少为：

$Pre{d}_k={\phi }_{k,1}\left(0\right)-{\phi }_{k,1}\left(d\right)+{\phi }_{k,2}\left(0\right)-{\phi }_{k,2}\left(d\right).$ (9)

且：

$Pre{d}_k\ge \frac{1}{2}\Vert g_k\Vert \min \left\{\Vert \Vert d_k\Vert ,\frac{\Vert g_k\Vert }{\Vert H_k\Vert }\Vert \right\}+\frac{1}{2}\Vert g\left(y_k\right)\Vert \min \left\{\Vert \Vert {\bar{d}}_k\Vert ,\frac{\Vert g\left(y_k\right)\Vert }{\Vert H\left(y_k\right)\Vert }\Vert \right\}$ (10)

根据定义 $Pre{d}_k$ 总是非负的，定义比率：

$r_k=\frac{Are{d}_k}{Pre{d}_k}.$ (11)

下面详细给出本论文的求解非凸无约束优化问题(1)的两步正则化牛顿法。

3. 收敛性分析

在本节中，我们主要研究该正则化牛顿法的全局收敛性，但由于f不是凸函数，由就算该正则化牛顿法全局收敛并不意味着该方法找到了全局最优解。并且在一定条件下有着超线性收敛性。

我们提出了如下的假设。

假设1：g(x)和H(x)都是lipschitz连续的，则有L > 0，有如下式子成立。

$\Vert g\left(x\right)-g\left(y\right)\Vert \le L\Vert x-y\Vert .$ (12)

$\Vert H\left(x\right)-H\left(y\right)\Vert \le L\Vert x-y\Vert .$ (13)

由lipschitz连续，我们有：

$\Vert g\left(y\right)-g\left(x\right)-H\left(x\right)\left(y-x\right)\Vert \le L{\Vert y-x\Vert }^2.$ (14)

假设2：

1) 存在该问题的局部最优解 $x^{*}$ 。

2) $\Vert g\left(x\right)\Vert$ 在 $x^{*}$ 的某个领域上提供了一个局部误差界，即存在两个正常数 $c_1$ 和 $b_1$ ，使得：

$\Vert g\left(x\right)\Vert \ge c_{1}dist\left(x,X\right),\forall x\in N\left(x^{*},b_1\right)=\left\{x|\Vert x-x^{*}\Vert \le b_1\right\}$ (15)

3) 海瑟矩阵H(x)是局部lipschitz连续的，即存在常数 $b_2\in \left(0,1\right)$ 和 $L_H>0$ ，有：

$\Vert H\left(y\right)-H\left(x\right)\Vert \le L_H\Vert y-x\Vert ,\forall x\in N\left(x^{*},b_1\right).$ (16)

$\Vert H\left(y\right)\left(x-y\right)-\left(g\left(x\right)-g\left(y\right)\right)\Vert \le \frac{1}{2}{L}_H{\Vert y-x\Vert }^2,\forall x\in N\left(x^{*},b_1\right).$ (17)

由于f是两次连续可微的，因此存在正常数 $L_1,L_2$ ：

$\Vert g\left(x\right)\Vert \le L_1,\forall x\in N\left(x^{*},b_1\right).$ (18)

$\Vert g\left(x\right)-g\left(y\right)\Vert \le L_2\Vert x-y\Vert ,\forall x\in N\left(x^{*},b_1\right).$ (19)

在本文的后面部分，我们用 $\bar{x}\in X$ 满足，

$\Vert \bar{x}-x\Vert =dist\left(x,X\right)=\underset{y\in x}{\inf }\Vert y-x\Vert .$ (20)

定理1：若假设1成立，如果f有界，根据AlgorithmI，我们有该算法终止于有限迭代或者满足 ${\lim }_{k\to \infty }\inf \Vert g_k\Vert =0$ 。

证明：采用反证法，假设定理为假，则存在一个整数 $\bar{k}$ ，对 $\forall k\ge \bar{k}$ 有：

$\Vert g_k\Vert \ge \tau .$ (21)

在不失一般性的条件下，我们能假设 $\bar{k}=1$ ，我们令 $T=\left\{k|x_k\ne x_{k+1}\right\}$ ，我们有：

$\left\{1,2,\cdots \right\}=T\cup \left\{k|x_k=x_{k+1}\right\}.$

下面我们来考虑如下两种情况：

情况1：若T是无限的，我们能找到一个整数 $k_1$ ，有：

$x_{k_1}=x_{k_1+1}=x_{k_1+2}=\cdots$

通过上述算法的步4，我们有：

$r_k<p_0,\forall k\ge k_1.$

由步5和式(21)我们有：

$c_k\to \infty ,{\lambda }_k\to \infty .$

因为 $x_k=x_{k+1}$ ，对任意 $k\ge k_1$ 都成立，得到：

$\Vert d_k\Vert =\Vert -{\left(H_k+c_1{\psi }_{k}I+{\lambda }_{k}I\right)}^{-1}{g}_k\Vert \le {\lambda }_k^{-1}\Vert g_k\Vert \to 0.$

从步3，我们得到，

$\begin{array}{c}\Vert {\bar{d}}_k\Vert =\Vert -{\left(H_k+{\lambda }_{k}I\right)}^{-1}g\left(y_k\right)\Vert \\ \le \Vert {\left(H_k+c_1{\psi }_{k}I+c_{k}I\right)}^{-1}\left(g\left(y_k\right)-g_k-H_k{d}_k\right)\Vert \\ +\Vert {\left(H_k+c_1{\psi }_{k}I+c_{k}I\right)}^{-1}{g}_k\Vert +\Vert {\left(H_k+c_1{\psi }_{k}I+c_{k}I\right)}^{-1}{H}_k{d}_k\Vert \\ \le L{c}_k^{-1}{\Vert d_k\Vert }^2+2\Vert d_k\Vert \\ \le m\Vert d_k\Vert .\end{array}$

得到

$\begin{array}{l}\left|Are{d}_k-Pre{d}_k\right|\\ =\left|f\left(x_k\right)-f\left(x_k+d_k+{\bar{d}}_k\right)-\left({\phi }_{k,1}\left(d\right)-{\phi }_{k,1}\left(d\right)+{\phi }_{k,2}\left(d\right)-{\phi }_{k,2}\left(d\right)\right)\right|\\ \le \left|f\left(y_k+{\bar{d}}_k\right)-f\left(y_k\right)-\frac{1}{2}{\bar{d}}^{\text{T}}{H}_{k}d-g{\left(y_k\right)}^{\text{T}}\bar{d}\right|+\left|f\left(y_k\right)-f\left(x_k\right)-d^{\text{T}}{H}_{k}d+g_k^{\text{T}}d\right|\\ =o\left({\Vert d_k\Vert }^2\right)+o\left({\Vert {\bar{d}}_k\Vert }^2\right)=o\left({\Vert d_k\Vert }^2\right).\end{array}$

从(10)和(21)得到：

$Pre{d}_k\ge \frac{1}{2}\tau \min \left\{\Vert d_k\Vert ,\frac{\tau }{L}\right\}\ge \frac{1}{2}\tau \Vert d_k\Vert .$

那么对于足够大的k，下式都成立，

$\left|r_k-1\right|=\frac{\left|Are{d}_k-Pre{d}_k\right|}{Pre{d}_k}=\frac{o\left({\Vert d_k\Vert }^2\right)}{\Vert d_k\Vert }\to 0.$

这意味着 $r_k\to 1$ ，因此，根据算法中的步5，那么有一个正数 $b_1$ 有： $c_k\le b_1$ 。

情况2：若T是有界的，那么有，

$\begin{array}{c}\infty >f\left(x_1\right)-\underset{k\to \infty }{\lim }\inf f\left(x_k\right)\\ \ge {\displaystyle \underset{i=1}{\overset{\infty }{\sum }}f\left(x_i\right)-f\left(x_{i+1}\right)}={\displaystyle \underset{k\in T}{\sum }{p}_{0}Pre{d}_k}\\ \ge {\displaystyle \underset{k\in T}{\sum }{p}_0}\left(\frac{1}{2}\Vert g_k\Vert \min \left\{\Vert d_k\Vert ,\frac{\Vert g_k\Vert }{L}\right\}+\frac{1}{2}\Vert g\left(y_k\right)\Vert \min \left\{\Vert \Vert {\bar{d}}_k\Vert ,\frac{\Vert g\left(y_k\right)\Vert }{\Vert H\left(y_k\right)\Vert }\Vert \right\}\right)\\ \ge {\displaystyle \underset{k\in T}{\sum }{p}_0}\frac{\tau }{2}\min \left\{\Vert d_k\Vert ,\frac{\tau }{L}\right\}.\end{array}$

得：

$\underset{k\to \infty ,k\in T}{\lim }{d}_k=0.$ (22)

由Step5可知，

${\lambda }_k\to \infty .$

与情况1类似，我们有

$\Vert \overline{d_k}\Vert \le b_2\Vert d_k\Vert ,\forall k\in T.$ (23)

根据(23)我们有，

$\Vert s_k\Vert =\Vert d_k+{\bar{d}}_k\Vert \le \left(1+b_2\right)\Vert d_k\Vert ,\forall k\in T.$

${\displaystyle \underset{k\in T}{\sum }\Vert s_k\Vert }<\infty .$

这意味着，

$x_k\to x^{*},d_k\to 0,{\bar{d}}_k\to 0.$

因为 $\left(H_k+{\mu }_k{\Vert g_k\Vert }^{\delta }I\right)d=-g_k$ ，由(12) (14) (23)，有：

$\begin{array}{c}{c}_k\Vert d_k\Vert =\Vert g_k+H_k{d}_k+c_1{\psi }_k{d}_k\Vert \\ \ge \Vert g_k\Vert -\Vert H_k\Vert \Vert d_k\Vert -\Vert c_1{\psi }_k\Vert \Vert d_k\Vert \\ \ge \tau -L\Vert d_k\Vert .\end{array}$

有：

$c_k\ge \frac{\tau }{\Vert d_k\Vert }-L\to \infty .$

由(11)可知， $r_k\to 1$ 。同理有那么有一个正数 $b_2$ 有： $c_k\le b_1$ 。

根据这两个情况所得 $c_k$ 均我们的假设相矛盾。定理得证。

根据定理1，我们可以得到AlgorithmI是全局收敛的，且若f是凸函数，定理1可以保证AlgorithmI产生的解集 $\left\{x_k\right\}$ 收敛于全局最优解。但f是非凸函数，全局收敛并不能保证找到全局最优解，为了证明该算法的超线性收敛性，我们给出如下的引理。

引理1：若假设2成立，那么我们有

$\Vert d_k\Vert =o\left(\Vert {\bar{x}}_k-x_k\Vert \right).$

$\Vert {\bar{d}}_k\Vert =o\left(\Vert {\bar{x}}_k-x_k\Vert \right).$

$\Vert s_k\Vert =o\left(\Vert {\bar{x}}_k-x_k\Vert \right).$

证明：因为 $x_k\to x^{*}\in X$ ，我们有：

$\begin{array}{c}\Vert d_k\Vert =\Vert {\left(H_k+c_1{\psi }_{k}I+c_k\Vert g_k\Vert I\right)}^{-1}{g}_k\Vert \\ =\Vert {\left(H_k+c_1{\psi }_{k}I+c_k\Vert g_k\Vert I\right)}^{-1}\left(g_k-\nabla f\left({\bar{x}}_k\right)-H_k\left(x_k-{\bar{x}}_k\right)+H_k\left(x_k-{\bar{x}}_k\right)\right)\Vert \\ \le \Vert {\left(H_k+c_1{\psi }_{k}I+c_k\Vert g_k\Vert I\right)}^{-1}\left(g_k-\nabla f\left({\bar{x}}_k\right)-H_k\left(x_k-{\bar{x}}_k\right)\right)\Vert \\ +\Vert {\left(H_k+c_1{\psi }_{k}I+c_k\Vert g_k\Vert I\right)}^{-1}{H}_k\left(x_k-{\bar{x}}_k\right)\Vert \end{array}$

$\begin{array}{c}\le \Vert {\left(H_k+c_1{\psi }_{k}I+c_k\Vert g_k\Vert I\right)}^{-1}\Vert \Vert g_k-\nabla f\left({\bar{x}}_k\right)-H_k\left(x_k-{\bar{x}}_k\right)\Vert \\ +\Vert {\left(H_k+c_1{\psi }_{k}I+c_k\Vert g_k\Vert I\right)}^{-1}\Vert \Vert H_k\left(x_k-{\bar{x}}_k\right)\Vert \\ \le \left(\frac{L_H}{2}{\Vert x_k-{\bar{x}}_k\Vert }^2+H_k\Vert x_k-{\bar{x}}_k\Vert \right)\Vert {\left(H_k+c_1{\psi }_{k}I+c_k\Vert g_k\Vert I\right)}^{-1}\Vert \\ =\frac{L_H}{2}dist{\left(x_k,X\right)}^2\Vert {\left(H_k+c_1{\psi }_{k}I+c_k{\Vert g_k\Vert }^{\delta }I\right)}^{-1}\Vert \\ +dist\left(x_k,X\right)\Vert {\left(H_k+c_1{\psi }_{k}I+c_k{\Vert g_k\Vert }^{\delta }I\right)}^{-1}{H}_k\Vert .\end{array}$

其中

$\begin{array}{c}{\left(H_k+c_1{\psi }_{k}I+c_k\Vert g_k\Vert I\right)}^{-1}=v_{\max }\left({\left(H_k+c_1{\psi }_{k}I+c_k{\Vert g_k\Vert }^{\delta }I\right)}^{-1}\right)\\ =\frac{1}{v_{\min }\left(H_k+c_1{\psi }_{k}I+c_k{\Vert g_k\Vert }^{\delta }I\right)}\\ \le \frac{1}{c_k\Vert g_k\Vert }\le \frac{1}{c_{k}Ldist\left(x_k,X^{*}\right)}.\end{array}$

下面我们考虑 $\Vert {\left(H_k+c_1{\psi }_{k}I+c_k\Vert g_k\Vert I\right)}^{-1}{H}_k\Vert$ ，我们称 $v_k^{\left(l\right)}$ 为 $H_k$ 中第l大的特征值。那么 ${\left(H_k+c_1{\psi }_{k}I+c_k\Vert g_k\Vert I\right)}^{-1}{H}_k$ 的特征值为

$\frac{v_k^{\left(l\right)}}{v_k^{\left(l\right)}+c_1{\psi }_k+c_k\Vert g_k\Vert },1\le l\le n.$

下面我们分两种情况讨论：1) $v_k^{\left(l\right)}\ge 0$ ，2) $v_k^{\left(l\right)}<0$ 。

1) $\frac{\left|v_k^{\left(l\right)}\right|}{\left|v_k^{\left(l\right)}+c_1{\psi }_k+c_k\Vert g_k\Vert \right|}\le 1.$

2) 因为：

$-{\psi }_k=v_{\min }\left(H_k\right)\le v_k^{\left(l\right)}<0,$

$v_k^{\left(l\right)}-v_{\min }\left(H_k\right)\ge 0,$

$\left|v_k^{\left(l\right)}\right|\le \left|v_{\min }\left(H_k\right)\right|.$

因此，我们有

$\begin{array}{c}\frac{\left|v_k^{\left(l\right)}\right|}{\left|v_k^{\left(l\right)}+c_1{\psi }_k+c_k\Vert g_k\Vert \right|}=\frac{\left|v_k^{\left(l\right)}\right|}{\left|\left(v_k^{\left(l\right)}-v_{\min }\left(H_k\right)\right)-\left(c_1-1\right)v_{\min }\left(H_k\right)+c_k\Vert g_k\Vert \right|}\\ \le \frac{\left|v_k^{\left(l\right)}\right|}{v_k^{\left(l\right)}-v_{\min }\left(H_k\right)+\left(c_1-1\right)\left|v_{\min }\left(H_k\right)\right|+c_k\Vert g_k\Vert }\\ \le \frac{1}{c_1-1}.\end{array}$

那么我们有

$\frac{\left|v_k^{\left(l\right)}\right|}{\left|v_k^{\left(l\right)}+c_1{\psi }_k+c_k\Vert g_k\Vert \right|}\le \max \left(1,\frac{1}{c_1-1}\right).$

因此，我们有

$\begin{array}{c}\Vert d_k\Vert \le \frac{L_H}{2c_{k}L}dist\left(x_k,X^{*}\right)+\max \left(1,\frac{1}{c_1-1}\right)dist\left(x_k,X^{*}\right)\\ \le L_{1}dist\left(x_k,X^{*}\right).\end{array}$

同理

$\begin{array}{c}\Vert {\bar{d}}_k\Vert =\Vert {\left(H_k+c_1{\psi }_{k}I+c_k\Vert g_k\Vert I\right)}^{-1}g\left(y_k\right)\Vert \\ =\Vert {\left(H_k+c_1{\psi }_{k}I+c_k\Vert g_k\Vert I\right)}^{-1}\left(g\left(y_k\right)-\nabla f\left(x_k\right)-H_k\left(y_k-x_k\right)+H_k\left(y_k-x_k\right)\right)\Vert \\ \le \Vert {\left(H_k+c_1{\psi }_{k}I+c_k\Vert g_k\Vert I\right)}^{-1}\left(g\left(y_k\right)-\nabla f\left(x_k\right)-H_k\left(y_k-x_k\right)\right)\Vert \\ +{\left(H_k+c_1{\psi }_{k}I+c_k\Vert g_k\Vert I\right)}^{-1}\Vert H_k\left(y_k-x_k\right)\Vert \\ \le \Vert {\left(H_k+c_1{\psi }_{k}I+c_k\Vert g_k\Vert I\right)}^{-1}\Vert \Vert g\left(y_k\right)-\nabla f\left(x_k\right)-H_k\left(y_k-x_k\right)\Vert \end{array}$

$\begin{array}{c}+\Vert {\left(H_k+c_1{\psi }_{k}I+c_k\Vert g_k\Vert I\right)}^{-1}\Vert \Vert H_k\left(y_k-x_k\right)\Vert \\ \le \left(\frac{L_H}{2}{\Vert y_k-x_k\Vert }^2+H_k\Vert y_k-x_k\Vert \right)\Vert {\left(H_k+c_1{\psi }_{k}I+c_k\Vert g_k\Vert I\right)}^{-1}\Vert \\ =\frac{L_H}{2}{\Vert d_k\Vert }^2\Vert {\left(H_k+c_1{\psi }_{k}I+c_k\Vert g_k\Vert I\right)}^{-1}\Vert +\Vert d_k\Vert \Vert {\left(H_k+c_1{\psi }_{k}I+c_k\Vert g_k\Vert I\right)}^{-1}{H}_k\Vert \\ \le mdist\left(x_k,X\right)+\max \left(1,\frac{1}{c_1-1}\right)dist\left(x_k,X\right)\\ \le \max \left(1,\frac{1}{c_1-1}\right)dist\left(x_k,X\right)\end{array}$

$\Vert s_k\Vert =\Vert d_k+{\bar{d}}_k\Vert =o\left(\Vert {\bar{x}}_k-x_k\Vert \right).$

引理成立。

引理2：若假设2成立，那么我们总有一个常数 $c_2$ ，有 $c_k\le c_2$ 。

证明：从

$\begin{array}{c}{\phi }_{k,1}\left(0\right)-{\phi }_{k,1}\left(d_k\right)\ge \frac{1}{2}\Vert g_k\Vert \min \left\{\Vert d_k,\frac{\Vert g_k\Vert }{\Vert G_k\Vert }\Vert \right\}\\ \ge \frac{1}{2}{c}_1\Vert x_k-{\bar{x}}_k\Vert \min \left\{\Vert d_k\Vert ,\frac{c_1}{L}\Vert x_k-{\bar{x}}_k\Vert \right\}\\ \ge c_2\Vert x_k-{\bar{x}}_k\Vert .\end{array}$

对于某个 $c_2$ 来说成立

从(11)我们得到

$\left|r_k-1\right|=\left|\frac{Are{d}_k-Pre{d}_k}{Pre{d}_k}\right|=\frac{o\left({\Vert d_k\Vert }^2\right)}{\Vert x_k-{\bar{x}}_k\Vert \min \left\{\Vert x_k-{\bar{x}}_k\Vert ,\Vert d_k\Vert \right\}}\to 0.$

因此有 $r_k\to 1$ ，我们由算法中的步骤5的更新规则推断出，存在一个常数 $c_2$ ，有 $c_k\le c_2$ 。

引理得证。

引理3：若假设2成立，我们有

${\psi }_k\le L_{H}dist\left(x_k,X\right)$

证明：

情况1)：当 $H_k\ge 0$ 时，我们有 ${\psi }_k=0$ 。

情况2)：当 $H_k<0$ 时，我们假设 $v_{\min }\left(H_k\right)<0$ ，我们称 $\overline{v_k^{\left(l\right)}}$ 为 ${\nabla }^{2}f\left({\bar{x}}_k\right)$ 中第l大的特征值。

因为 ${\bar{x}}_k\in X$ ，我们有 $\overline{v_k^{\left(l\right)}}\ge 0$ ，根据假设，非凸函数 $f\left(x\right)$ 满足二阶连续的条件，那么 ${\nabla }^{2}f\left({\bar{x}}_k\right)$ 是实对称矩阵，则存在正交矩阵 $Q_k$ ，有：

$Q_k^{\text{T}}{\nabla }^{2}f\left({\bar{x}}_k\right)Q_k=diag\left(\overline{v_k^{\left(l\right)}}\right).$

其中 $diag\left(\overline{v_k^{\left(l\right)}}\right)$ 表示的为对角线元素为 $\overline{v_k^{\left(l\right)}}$ 的对角矩阵，

$\begin{array}{c}{v}_{\min }\left(H_k\right)I-Q_k^{\text{T}}{H}_k{Q}_k=v_{\min }\left(H_k\right)I-Q_k^{\text{T}}\left({\nabla }^{2}f\left({\bar{x}}_k\right)+\left(H_k-{\nabla }^{2}f\left({\bar{x}}_k\right)\right)\right)Q_k\\ =v_{\min }\left(H_k\right)I-diag\left(\overline{v_k^{\left(l\right)}}\right)-Q_k^{\text{T}}\left(H_k-{\nabla }^{2}f\left({\bar{x}}_k\right)\right)Q_k.\end{array}$

因为 $Q_k^{\text{T}}{H}_k{Q}_k$ 总会有特征值 $v_{\min }\left(H_k\right)$ ，因此我们有 $v_{\min }\left(H_k\right)I-Q_k^{\text{T}}{H}_k{Q}_k$ 是奇异的，因此 $v_{\min }\left(H_k\right)I-diag\left(\overline{v_k^{\left(l\right)}}\right)-Q_k^{\text{T}}\left(H_k-{\nabla }^{2}f\left({\bar{x}}_k\right)\right)Q_k$ 也是奇异的。因为 $v_{\min }\left(H_k\right)<0$ 且 $\overline{v_k^{\left(l\right)}}\ge 0$ Math_201#是非奇异的。我们令：

$M={\left(v_{\min }\left(H_k\right)I-diag\left(\overline{v_k^{\left(l\right)}}\right)\right)}^{-1}\ast v_{\min }\left(H_k\right)I-diag\left(\overline{v_k^{\left(l\right)}}\right)-Q_k^{\text{T}}\left(H_k-{\nabla }^{2}f\left({\bar{x}}_k\right)\right)Q_k.$

根据引理，我们有：

$\begin{array}{c}1\le \Vert I-M\Vert \\ =\Vert I-\left(I-{\left(v_{\min }\left(H_k\right)I-diag\left(\overline{v_k^{\left(l\right)}}\right)\right)}^{-1}\right)Q_k^{\text{T}}\left(H_k-{\nabla }^{2}f\left({\bar{x}}_k\right)\right)Q_k\Vert \\ =\Vert {\left(v_{\min }\left(H_k\right)I-diag\left(\overline{v_k^{\left(l\right)}}\right)\right)}^{-1}{Q}_k^{\text{T}}\left(H_k-{\nabla }^{2}f\left({\bar{x}}_k\right)\right)Q_k\Vert \\ \le \Vert {\left(v_{\min }\left(H_k\right)I-diag\left(\overline{v_k^{\left(l\right)}}\right)\right)}^{-1}\Vert \Vert Q_k^{\text{T}}\left(H_k-{\nabla }^{2}f\left({\bar{x}}_k\right)\right)Q_k\Vert \\ =\Vert {\left(v_{\min }\left(H_k\right)I-diag\left(\overline{v_k^{\left(l\right)}}\right)\right)}^{-1}\Vert \Vert H_k-{\nabla }^{2}f\left({\bar{x}}_k\right)\Vert .\end{array}$

我们分别考虑 $\Vert {\left(v_{\min }\left(H_k\right)I-diag\left(\overline{v_k^{\left(l\right)}}\right)\right)}^{-1}\Vert$ 和 $\Vert H_k-{\nabla }^{2}f\left({\bar{x}}_k\right)\Vert$ 。

因为 $v_{\min }\left(H_k\right)<0$ ，且 $\overline{v_k^{\left(l\right)}}\ge 0$ 。

$\begin{array}{c}{\left(v_{\min }\left(H_k\right)I-diag\left(\overline{v_k^{\left(l\right)}}\right)\right)}^{-1}=\underset{1\le l\le n}{\max }\left|{\left(v_{\min }\left(H_k\right)I-diag\left(\overline{v_k^{\left(l\right)}}\right)\right)}^{-1}\right|\\ =\frac{1}{\underset{1\le l\le n}{\min }\left|v_{\min }\left(H_k\right)I-diag\left(\overline{v_k^{\left(l\right)}}\right)\right|}\\ \le \frac{1}{\left|v_{\min }\left(H_k\right)\right|}=\frac{1}{{\psi }_k}.\end{array}$

根据假设2，我们有

$\Vert H_k-{\nabla }^{2}f\left({\bar{x}}_k\right)\Vert \le L_H\Vert x_k-{\bar{x}}_k\Vert =L_{H}dist\left(x_k,X\right).$

因此，我们有：

${\psi }_k\le L_{H}dist\left(x_k,X\right).$

引理得证。

根据上述引理，我们有：

${\lambda }_k=c_1{\psi }_k+c_k\Vert g_k\Vert \ge c_k\Vert g_k\Vert \ge mcdist\left(x_k,X\right)=mc\Vert x_k-{\bar{x}}_k\Vert .$

${\lambda }_k=c_1{\psi }_k+c_k\Vert g_k\Vert \le L_{H}dist\left(x_k,X\right)+c_k\Vert g_k\Vert \le c\Vert x_k-{\bar{x}}_k\Vert$

即： ${\lambda }_k,c_k$ 等价于 $\Vert x_k-{\bar{x}}_k\Vert$ 。

${\lambda }_k=\Vert x_k-{\bar{x}}_k\Vert ,c_k=\Vert x_k-{\bar{x}}_k\Vert .$ (24)

引理4：若假设2成立，我们有

$dist\left(x_{k+1},X\right)=o\left(dist{\left(x_k,X\right)}^2\right).$

证明：由(18)可知

$\begin{array}{c}{k}_{1}dist\left(x_{k+1},X\right)\le \Vert g_{k+1}\Vert =\Vert g\left(y_k+{\bar{d}}_k\right)\Vert \\ \le \Vert g\left(y_k+{\bar{d}}_k\right)-g\left(y_k\right)-G\left(y_k\right){\bar{d}}_k\Vert +\Vert g\left(y_k\right)+G\left(y_k\right){\bar{d}}_k\Vert \\ \le L{\Vert {\bar{d}}_k\Vert }^2+\Vert g\left(y_k\right)+G\left(x_k\right){\bar{d}}_k\Vert +\Vert \left(G\left(y_k\right)-G\left(x_k\right)\right){\bar{d}}_k\Vert \\ \le L{\Vert {\bar{d}}_k\Vert }^2+\left({\psi }_k+{\lambda }_k\right)\Vert {\bar{d}}_k\Vert +L\Vert d_k\Vert \Vert {\bar{d}}_k\Vert \\ =o(dist{\left(x_k,X\right)}^2.\end{array}$

定理2：若假设成立，我们假设 $\left\{x_k\right\}$ 是由AlgorithmI生成的序列，那么我们称 $dist\left(x_k,X\right)$ 是二阶收敛于0，且 $\left\{x_k\right\}$ 是局部收敛于最优解 $x^{*}$ 的。

证明：由引理4，我们总能找到一个序列 $\left\{x_k\right\}$ 使得 $dist\left(x_k,X\right)$ 2阶趋近于0的。

而根据 [1] ，我们总能找到序列 $\left\{x_k\right\}$ ，在其中找出两个元素 $x_p,x_q\in \left\{x_k\right\}$ ，使得 $\left|x_p-x_q\right|\le \epsilon$ 。

那么我们可知， $\left\{x_k\right\}$ 是一个柯西序列那么其肯定是一个收敛数列，定理得证。

引理5 [7] ：如果 $\left\{x_k\right\}$ 是超线性收敛于 $x^{*}$ 的，那么有：

$\underset{k\to \infty }{\lim }\frac{\Vert x_{k+1}-x_k\Vert }{\Vert x_k-x^{*}\Vert }=1.$

由引理4我们有

$\Vert {\bar{x}}_k-x_k\Vert \le \Vert {\bar{x}}_{k+1}-x_{k+1}+x_{k+1}-x_k\Vert \le 2\Vert s_k\Vert$

由引理5可得， $\Vert s_k\Vert$ 等价于 $\Vert x_k-x^{*}\Vert$ 。因此有 $\Vert x_k-x^{*}\Vert$ 等价于 $\Vert {\bar{x}}_k-x_k\Vert$ 。

我们知道 $H\left(x^{*}\right)\ne 0$ ，又 $H\left(x^{*}\right)$ 是对称的，而且， $H\left(x^{*}\right)+c_1{\psi }_{*}I$ ，是半正定的，且 ${\psi }_{*}\ge 0$ ，此时 $G\left(x^{*}\right)=H\left(x^{*}\right)+c_1{\psi }_{*}I\ne 0$ ，因此存在正交矩阵U使得：

$G\left(x^{*}\right)=\left(U_1,U_2\right)\left(\begin{array}{cc}{\Sigma }_1^{*}& 0\\ 0& 0\end{array}\right){\left(U_1,U_2\right)}^{\text{T}},$

其中 ${\Sigma }_1^{*}$ 是一个正对角矩阵，类似的，我们假设 $H\left(x\right)$ 的奇异值分解为：

$G\left(x\right)=\left(U_1,U_2\right)\left(\begin{array}{cc}{\Sigma }_1& 0\\ 0& {\Sigma }_2\end{array}\right){\left(U_1,U_2\right)}^{\text{T}}=U_1{\Sigma }_1{U}_1^{\text{T}}+U_2{\Sigma }_2{U}_2^{\text{T}}.$

其中 $Rank\left({\Sigma }_1\right)=Rank\left({\Sigma }_1^{*}\right)$ ， ${\Sigma }_2$ 随着 $x\to x^{*}$ 收敛于0。在后文中，我们将 $G\left(x_k\right)$ 简写成 $G_k$ ，则根据矩阵扰动理论 [8] [9] ，我们有：

$\Vert {\Sigma }_1-{\Sigma }_2\Vert +\Vert {\Sigma }_2\Vert \le \Vert G_k-G\left(x^{*}\right)\Vert \le L\Vert x_k-x^{*}\Vert .$

即： $\Vert {\Sigma }_1-{\Sigma }_1^{*}\Vert \le L\Vert {\bar{x}}_k-x_k\Vert$ ， $\Vert {\Sigma }_2\Vert \le \Vert {\bar{x}}_k-x_k\Vert$ ，

引理6：若假设成立，我们有：

$\Vert g\left(y_k\right)\Vert =o\left({\Vert x_k-{\bar{x}}_k\Vert }^2\right),\Vert U_2{U}_2^{\text{T}}g\left(y_k\right)\Vert =o\left({\Vert x_k-{\bar{x}}_k\Vert }^3\right).$

证明：根据式(24)，我们有 $\Vert g_k+G_k{d}_k\Vert ={\lambda }_k\Vert d_k\Vert =o\left({\Vert x_k-{\bar{x}}_k\Vert }^2\right)$ 。

相似的，我们有： $\Vert g_k+G_k{\bar{d}}_k\Vert ={\lambda }_k\Vert {\bar{d}}_k\Vert =o\left({\Vert x_k-{\bar{x}}_k\Vert }^2\right)$ 。

因此，我们有，

$\Vert g\left(y_k\right)\Vert =\Vert g\left(x_k+d_k\right)-g_k-G_k{d}_k\Vert +\Vert g_k+G_k{d}_k\Vert =o\left({\Vert x_k-{\bar{x}}_k\Vert }^2\right).$

且

$\Vert {\bar{y}}_k-y_k\Vert \le L\Vert g\left(y_k\right)\Vert =o\left({\Vert x_k-{\bar{x}}_k\Vert }^2\right).$

令 $M_k=U_1{\Sigma }_1{U}_1^{\text{T}}$ ， $t_k=-M_k^{+}g\left(y_k\right)$ 。那么我们易得 $t_k$ 是如下最小二乘算法的解：

$\min \Vert g\left(y_k\right)+M_k{t}_k\Vert .$

因此：

$\begin{array}{c}\Vert U_2{U}_2^{\text{T}}g\left(y_k\right)\Vert =\Vert g\left(y_k\right)+M_k{t}_k\Vert \le \Vert g\left(y_k\right)+M_k\left({\bar{y}}_k-y_k\right)\Vert \\ \le \Vert g\left(y_k\right)-G\left(y_k\right)\left({\bar{y}}_k-y_k\right)\Vert +\Vert \left(G\left(y_k\right)-G_k\right)\left({\bar{y}}_k-y_k\right)\Vert +\Vert \left(G_k-M_k\right)\left({\bar{y}}_k-y_k\right)\Vert \\ \le L{\Vert {\bar{y}}_k-y_k\Vert }^2+L\Vert d_k\Vert \Vert {\bar{y}}_k-y_k\Vert +\Vert {\Sigma }_2\Vert \Vert {\bar{y}}_k-y_k\Vert \\ =o\left({\Vert x_k-{\bar{x}}_k\Vert }^3\right).\end{array}$

引理7：若假设成立，我们有： $\Vert {\bar{d}}_k\Vert =o\left({\Vert x_k-{\bar{x}}_k\Vert }^2\right)$ 。

证明： $\begin{array}{c}{\bar{d}}_k=-{\left(H_k+{\lambda }_{k}I\right)}^{-1}g\left(y_k\right)=-{\left(G_k+c_{k}I\right)}^{-1}g\left(y_k\right)\\ =-U_1{\left({\Sigma }_1+c_{k}I\right)}^{-1}{U}_1^{\text{T}}g\left(y_k\right)-U_2{\left({\Sigma }_2+c_{k}I\right)}^{-1}{U}_2^{\text{T}}g\left(y_k\right).\end{array}$

因为 $x_k\to x^{*}$ ，令 ${\Sigma }_1\to {\Sigma }_1^{*}$ ，那么我们有 ${\Sigma }_1^{-1}$ 是一致有界的，即存在一个常数 $c_4$ ，有： $\Vert {\Sigma }_1^{-1}\Vert \le c_4$ 。

因此我们有：

$\Vert {\bar{d}}_k\Vert \le \Vert {\Sigma }_1^{-1}\Vert \Vert U_1{U}_1^{\text{T}}g\left(y_k\right)\Vert +c_k^{-1}\Vert U_2{U}_2^{\text{T}}g\left(y_k\right)\Vert \le c_4\Vert g\left(y_k\right)\Vert +c_k^{-1}\Vert U_2{U}_2^{\text{T}}g\left(y_k\right)\Vert =o\left({\Vert x_k-{\bar{x}}_k\Vert }^2\right).$

定理3：若假设成立，我们假设 $\left\{x_k\right\}$ 是由AlgorithmI生成的序列，那么我们称 $dist\left(x_k,X\right)$ 是三阶收敛于0，且 $\left\{x_k\right\}$ 是局部收敛于最优解 的。

证明：

$\begin{array}{c}\Vert {\bar{x}}_{k+1}-x_{k+1}\Vert \le \Vert g\left(x_{k+1}\right)\Vert =\Vert g\left(y_k+{\bar{d}}_k\right)\Vert \\ \le \Vert g\left(y_k+{\bar{d}}_k\right)-g\left(y_k\right)-G\left(y_k\right){\bar{d}}_k\Vert +\Vert g\left(y_k\right)+G\left(y_k\right){\bar{d}}_k\Vert \\ \le L{\Vert {\bar{d}}_k\Vert }^2+\Vert \left(G\left(y_k\right)-G_k\right){\bar{d}}_k\Vert +\Vert g\left(y_k\right)+G_k{\bar{d}}_k\Vert \\ \le L{\Vert {\bar{d}}_k\Vert }^2+L\Vert d_k\Vert \Vert {\bar{d}}_k\Vert +{\lambda }_k\Vert {\bar{d}}_k\Vert \\ =o\left({\Vert x_k-{\bar{x}}_k\Vert }^2\right).\end{array}$

定理得证。

4. 数值实验

下面求解两个不等式约束优化问题的数值算例，验证AlgorithmI的有效性，并与[3]进行比较，算法在MATLB R2022a编程实现，数值实验在windows系统中进行。实验中，我们取终止条件为 ${\epsilon }_{stop}\le {10}^{-7}$ ，取初始的正则化参数为， $c_1=2$ ， $c_k=2$ ，比率的取值为 $p_0=0.1$ ， $p_1=0.2$ ， $p_2=0.3$ 。

考虑如下无约束优化问题且统一算例的初始值相同，实验结果见下表，每组表都给出了选取的初值 $x_1$ ，并在所取初值相等的情况下比较，所需迭代次数k、迭代点 $x^{*}$ 和此时函数的值 $f\left(x^{*}\right)$ 。

例1：考虑如下无约束优化问题

$\min f\left(x\right)=\frac{1}{2}{x}_1^2+\frac{1}{2}{x}_1^2{x}_2^2$

例2：考虑如下无约束优化问题

$\min f\left(x\right)=\sin x_1+\cos x_2+x_1{x}_2^2$

例3：考虑如下无约束优化问题

$\min f\left(x\right)=x_1^2+x_2^2+x_3^2+x_1{x}_2+x_2{x}_3+x_1{x}_3$

从上述例子我们可以看出，上述例子对于非凸函数的无约束优化问题的最优解是有效的,而在取不同的初始值时，迭代效果依旧强于单步正则化牛顿法，于是我们说该算法是可行的。

5. 结论

本文根据非凸无约束优化问题的单步正则化牛顿法进行改进提出了非凸无约束优化问题的两步正则化牛顿法，并对方法的收敛性进行研究。证明了在一定的条件下该方法是全局收敛的并且在局部误差界下具有三次收敛速度。理论分析证明，该算法有着良好的性质并证明了对应算法的全局收敛性。根据所提出的方法进行了部分数值实验，并将运算结果与单步的正则化牛顿法进行了对比，我们的方法有着更好的性质，进一步验证了本文算法的有效性。

参考文献