基于不定系数常微分方程的加速梯度算法研究

Research on Accelerated Gradient Algorithm Based on Ordinary Differential Equations with Uncertain Coefficients

摘要: 随着人工智能功能的日益强大，对机器学习、深度学习的研究也日趋完善。深度学习的核心思想是求解优化问题，而随着当前实际问题规模的日益扩大，梯度类算法由于运算成本相对较低，日益受到人们的关注和青睐，设计新的加速梯度算法是加快问题求解的关键。本文基于常微分方程，得到了一系列新的加速梯度算法。本文考虑了一类系数不定的二阶常微分方程，证明了系数在满足什么条件下，该微分方程能够快速收敛。对于该微分方程，本文采用两种不同的离散格式：显式欧拉格式、隐式欧拉格式进行离散，分别得到了两类不同的优化算法，分别证明了算法的收敛速率。最后，本文通过数值实验证明了算法的有效性。

Abstract: With the increasingly powerful functions of artificial intelligence, research on machine learning and deep learning is also becoming increasingly sophisticated. The core idea of deep learning is to solve optimization problems, and with the increasing scale of practical problems, gradient algorithms are increasingly receiving attention and favor due to their relatively low computational costs. Designing new accelerated gradient algorithms is the key to accelerating problem solving. This article presents a series of new accelerated gradient algorithms based on ordinary differential equations. This article considers a class of second-order ordinary differential equations with uncertain coefficients and proves under what conditions the coefficients satisfy that the differential equation can converge quickly. For this differential equation, this paper adopts two different discretization schemes: explicit Euler scheme and implicit Euler scheme for discretization, and obtains two different optimization algorithms, respectively proving the convergence rate of the algorithms. Finally, this article demonstrates the effectiveness of the algorithm through numerical experiments.

1. 引言

随着计算机与网络的飞速发展，机器学习在各个领域中起着越来越大的作用，正在不断改变着我们的生活。不管是机器学习还是神经网络，它们往往都可以归结为求解最优化问题‎[1]。

机器学习中的优化问题根据目标函数的凸性，可分为凸优化问题和非凸优化问题；根据目标函数是否带有约束，可分为约束优化问题和无约束优化问题。对于非凸优化问题，在实际应用中，有时候可以通过如局部线性化、凸松弛等技巧将非凸优化问题转化为凸优化问题，从而利用凸优化的相关算法来求解。对于约束优化问题，可以通过如罚函数等方法将其转化为无约束优化问题。本文考虑的是无约束凸优化问题。

机器学习在现代社会扮演着越来越重要的角色，对医疗健康、金融领域、智能交通、自然语言处理等领域都产生了深远的影响。而作为机器学习的根本，对求解优化问题相关算法的研究在近年来日益受到人们的关注。

本文考虑的问题为无约束优化问题：

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

其中$f\left(x\right)$ 是光滑的强凸函数。定义$R^n$ 上的一类光滑凸函数为${ℱ}_L^1$ ，若$\forall x,y\in R^n$ ，函数梯度满足Lipschitz连续：

$\Vert \nabla f\left(y\right)-\nabla f\left(x\right)\Vert \le L\Vert y-x\Vert$ (2)

其中L是Lipschitz系数。定义$R^n$ 上的强凸函数$f\in {\mathcal{S}}_{\mu }^1$ ，若存在常数$\mu$ ，使得函数$g\left(x\right)=f\left(x\right)-\frac{\mu }{2}{\Vert x\Vert }^2$ 为凸函数，则称函数$f\left(x\right)$ 为μ-强凸函数。若函数$f\left(x\right)$ 为μ-强凸函数，则$\forall x,y\in R^n$ ，满足：

$f\left(y\right)\ge f\left(x\right)+\langle \nabla f\left(x\right),y-x\rangle +\frac{\mu }{2}{\Vert y-x\Vert }^2$ (3)

最基础的梯度算法是梯度下降法：

$x_{k+1}=x_k-s\nabla f\left(x_k\right)$ (4)

其中s是步长。梯度下降法的基本思想是沿着函数梯度的反方向逐步迭代更新参数，以减小目标函数的值。然而，梯度下降法的算法性能在很大程度上受到目标函数的约束。为了解决这一问题，提高算法的收敛速率，近几十年来，学者们从不同的角度出发，设计了不同的加速梯度算法，其中较为典型的有重球方法‎[2]与Nesterov加速梯度算法(NAG算法) ‎[3]，其中NAG算法具有优秀的算法性能，在机器学习中被广泛运用。然而，算法的加速原理至今未能得到合理的解释。

常微分方程(Ordinary Differential Equations, ODE)与一阶优化算法之间存在密切的联系。在无约束优化问题中，求解优化问题的过程可以被视为一个微分方程的求解过程。因此，微分方程理论为我们提供了一种理论框架，帮助我们理解梯度类算法在优化问题中的工作原理，并为算法的收敛性和稳定性提供理论支持。基于这一思想，人们开始从ODE的角度来解释算法的加速原理，并设计新的加速梯度算法。Attouch ‎[4]在重球方法对应ODE的基础上引入含有Hessian矩阵的项，得到惯性动力系统。Su等人‎[5]将NAG算法的迭代点视为一个连续变量在某些特定时间点取值的近似，利用泰勒展开，得到了NAG算法对应连续时间下的ODE。Shi B等人‎[6]在此基础上，通过更高阶的泰勒展开，分别得到了NAG算法与重球方法对应的高精度ODE，高精度ODE更能反应算法的新能。Chen等人‎[7]以ODE为工具，给出了一阶凸优化算法的统一收敛性分析框架，并提出了一种新的动态惯性牛顿系统，以此得到了新的加速梯度算法‎[8]。

本文基于文献‎[6]中提出的Layapunov函数构建方法，考虑一类系数不定的ODE：

$\ddot{X}+\alpha \dot{X}+\beta {\nabla }^{2}f\left(X\right)\dot{X}+\nabla f\left(X\right)=0$ (5)

首先，通过构造合适的Layapunov函数，证明该ODE在不定系数$\alpha ,\beta$ 在满足什么条件下能够快速收敛。其次，本文使用两种不同的离散格式：显式欧拉格式和隐式欧拉格式对该ODE进行离散，得到两种不同的优化算法，并分别构造合适的Layapunov函数，证明这两类算法的收敛速率。最后，通过数值实验，验证所得算法的实用性。

2. 系数不定的二阶常微分方程与收敛速率

在本章中，我们考虑一个系数不定的二阶ODE：

$\ddot{X}+\alpha \dot{X}+\beta {\nabla }^{2}f\left(X\right)\dot{X}+\nabla f\left(X\right)=0$ (6)

定理2.1. 证明了系数$\alpha ,\beta$ 在满足什么条件时，ODE能够快速收敛。

定理2.1. 假设目标函数$f\in {\mathcal{S}}_{\mu ,L}^1$ ，$X\left(t\right)$ 为ODE：$\ddot{X}+\alpha \dot{X}+\beta {\nabla }^{2}f\left(X\right)\dot{X}+\nabla f\left(X\right)=0$ 的一个解，当系数$\alpha ,\beta$ 满足$\{\begin{array}{l}\frac{3}{4}{\alpha }^2\le \frac{\mu }{2}\hfill \\ \beta \le \frac{8}{3\alpha }\hfill \\ \alpha \ge 0\hfill \end{array}$ 时，$X\left(t\right)$ 满足$f\left(X\left(t\right)\right)-f\left(x^{*}\right)\le C{\Vert x_0-x^{*}\Vert }^2{\text{e}}^{-\frac{\alpha }{4}t}$ ，其中$C=\left(\frac{L}{2}+\left(1+\frac{3}{4}{\beta }^2\right)L^2+\frac{3}{4}{\alpha }^2\right){\Vert X_0-x^{*}\Vert }^2.$

证明：设Layapunov函数为：

$\epsilon \left(t\right)=f\left(X\right)-f\left(x^{*}\right)+\frac{1}{4}{\Vert \dot{X}\Vert }^2+\frac{1}{4}{\Vert \dot{X}+\alpha \left(X-x^{*}\right)+\beta \nabla f\left(X\right)\Vert }^2$ .

$\begin{array}{c}\frac{\text{d}\epsilon }{\text{d}t}=\langle \nabla f\left(X\right),\dot{X}\rangle +\frac{1}{2}\langle \dot{X},-\alpha \dot{X}-\beta {\nabla }^{2}f\left(X\right)\dot{X}-\nabla f\left(X\right)\rangle +\frac{1}{2}\langle \dot{X}+\alpha \left(X-x^{*}\right)+\beta \nabla f\left(X\right),-\nabla f\left(X\right)\rangle \\ =-\frac{1}{2}\alpha {\Vert \dot{X}\Vert }^2-\frac{1}{2}\beta {\Vert \nabla f\left(X\right)\Vert }^2-\frac{1}{2}\alpha \langle \nabla f\left(X\right),X-x^{*}\rangle -\frac{1}{2}\beta {\dot{X}}^T{\nabla }^{2}f\left(X\right)\dot{X}\\ \le -\frac{1}{2}\alpha {\Vert \dot{X}\Vert }^2-\frac{1}{2}\beta {\Vert \nabla f\left(X\right)\Vert }^2-\frac{1}{2}\alpha \langle \nabla f\left(X\right),X-x^{*}\rangle .\end{array}$

由$f\left(x\right)$ 的强凸性可得

$\begin{array}{c}\frac{1}{2}\alpha \langle \nabla f\left(X\right),X-x^{*}\rangle \ge \frac{1}{2}\alpha \left[f\left(X\right)-f\left(x^{*}\right)\right]+\frac{\mu \alpha }{4}{\Vert X-x^{*}\Vert }^2\\ \ge \frac{1}{4}\alpha \left[f\left(X\right)-f\left(x^{*}\right)\right]+\frac{\mu \alpha }{4}{\Vert X-x^{*}\Vert }^2,\end{array}$

故

$\begin{array}{c}\frac{\text{d}\epsilon }{\text{d}t}\le -\frac{1}{2}\alpha {\Vert \dot{X}\Vert }^2-\frac{1}{2}\beta {\Vert \nabla f\left(X\right)\Vert }^2-\frac{1}{4}\alpha \left[f\left(X\right)-f\left(x^{*}\right)\right]-\frac{\mu \alpha }{8}{\Vert X-x^{*}\Vert }^2\\ =-\alpha \left(\frac{1}{4}\left[f\left(X\right)-f\left(x^{*}\right)\right]+\frac{1}{2}{\Vert \dot{X}\Vert }^2+\frac{1}{4}\mu {\Vert X-x^{*}\Vert }^2+\frac{\beta }{2\alpha }{\Vert \nabla f\left(X\right)\Vert }^2\right).\end{array}$ (7)

由柯西–施瓦茨不等式，

${\Vert \dot{X}+\alpha \left(X-x^{*}\right)+\beta \nabla f\left(X\right)\Vert }^2\le 3\left({\Vert \dot{X}\Vert }^2+{\alpha }^2{\Vert X-x^{*}\Vert }^2+{\beta }^2{\Vert \nabla f\left(X\right)\Vert }^2\right).$

故

$\epsilon \left(t\right)\le f\left(X\right)-f\left(x^{*}\right)+{\Vert \dot{X}\Vert }^2+\frac{3}{4}{\alpha }^2{\Vert X-x^{*}\Vert }^2+\frac{3}{4}{\beta }^2{\Vert \nabla f\left(X\right)\Vert }^2.$ (8)

对比式(7)和式(8)中的各项，当系数$\alpha ,\beta$ 满足$\{\begin{array}{l}\frac{3}{4}{\alpha }^2\le \mu \hfill \\ \beta \le \frac{8}{3\alpha }\hfill \end{array}$ 时，

$\frac{\text{d}\epsilon }{\text{d}t}\le -\frac{\alpha }{4}\epsilon \left(t\right)$ ,

即

$\epsilon \left(t\right)\le {\text{e}}^{-\frac{\alpha }{4}t}\epsilon \left(0\right)$ ,

$f\left(X\left(t\right)\right)-f\left(x^{*}\right)\le \epsilon \left(t\right)\le {\text{e}}^{-\frac{\alpha }{4}t}\epsilon \left(0\right).$

设$X\left(0\right)=X_0$ ，$\dot{X}\left(0\right)=\nabla f\left(X_0\right)$ ，由于$f\in {\mathcal{S}}_{\mu ,L}^1$ ，则有

$f\left(X_0\right)-f\left(x^{*}\right)\le \frac{L}{2}{\Vert X_0-x^{*}\Vert }^2,\Vert \nabla f\left(X_0\right)\Vert \le L\Vert X_0-x^{*}\Vert$ .

$\begin{array}{c}\epsilon \left(0\right)=f\left(X_0\right)-f\left(x^{*}\right)+\frac{1}{4}{\Vert \nabla f\left(X_0\right)\Vert }^2+\frac{1}{4}{\Vert \nabla f\left(X_0\right)+\alpha \left(X_0-x^{*}\right)+\beta \nabla f\left(X_0\right)\Vert }^2\\ \le f\left(X_0\right)-f\left(x^{*}\right)+\left(1+\frac{3}{4}{\beta }^2\right){\Vert \nabla f\left(X_0\right)\Vert }^2+\frac{3}{4}{\alpha }^2{\Vert X_0-x^{*}\Vert }^2\\ =\left(\frac{L}{2}+\left(1+\frac{3}{4}{\beta }^2\right)L^2+\frac{3}{4}{\alpha }^2\right){\Vert X_0-x^{*}\Vert }^2.\end{array}$

综上，

$f\left(X\left(t\right)\right)-f\left(x^{*}\right)\le C{\Vert x_0-x^{*}\Vert }^2{\text{e}}^{-\frac{\alpha }{4}t},$

其中$C=\left(\frac{L}{2}+\left(1+\frac{3}{4}{\beta }^2\right)L^2+\frac{3}{4}{\alpha }^2\right){\Vert X_0-x^{*}\Vert }^2.$

3. 一类新的加速梯度算法

在第二章中，我们证明了系数不定的ODE：

$\ddot{X}+\alpha \dot{X}+\beta {\nabla }^{2}f\left(X\right)\dot{X}+\nabla f\left(X\right)=0$

在系数$\alpha ,\beta$ 在满足什么条件时，ODE能够快速收敛。式(6)等价于：

$\dot{X}=V,\dot{V}=-\alpha V-\beta {\nabla }^{2}f\left(X\right)V-\nabla f\left(X\right)$ (9)

本章将使用两种不同的离散格式：显式欧拉格式和隐式欧拉格式对式(9)进行离散得到相应的优化算法，并分别证明它们的收敛速率。

3.1. 显式欧拉格式

第一种离散格式是显式欧拉格式，它的近似规则如下：

$x_{k+1}-x_k=\sqrt{s}{v}_k,\sqrt{s}{\nabla }^{2}f\left(x_k\right)v_k\approx \nabla f\left(x_{k+1}\right)-\nabla f\left(x_k\right)$ .

由显式欧拉格式离散式(9)可得如下优化算法：

$\{\begin{array}{l}{x}_{k+1}-x_k=\sqrt{s}{v}_k\hfill \\ v_{k+1}-v_k=-\alpha \sqrt{s}{v}_k-\beta \left(\nabla f\left(x_{k+1}\right)-\nabla f\left(x_k\right)\right)-\sqrt{s}\nabla f\left(x_k\right)\hfill \end{array}$ (10)

定理3.1. 假设目标函数$f\in {\mathcal{S}}_{\mu ,L}^1$ ，对于显式欧拉格式产生的迭代点序列${\left\{x_k\right\}}_{k\in N}$ ，当系数$\alpha ,\beta$ 满足$\{\begin{array}{l}\frac{3}{4}{\alpha }^2\le \frac{\mu }{2}\hfill \\ \beta \le \frac{8}{3\alpha }\hfill \\ \alpha \ge 0\hfill \end{array}$ ，步长s满足$s\le \min \left\{\frac{4}{9L^2{\beta }^2},\frac{{\alpha }^2}{{\left(3{\alpha }^2+2L\right)}^2},\frac{{\left(\alpha \gamma -\beta \gamma L\right)}^2}{16L^2{\gamma }^4},\frac{1}{L}\right\}$ 时，收敛速率满足

$f\left(x_k\right)-f\left(x^{*}\right)\le C{\left(1-\frac{\alpha \sqrt{s}}{8}\right)}^k{\Vert x_0-x^{*}\Vert }^2,$

其中$C=\left(\frac{L}{2}+\left(1+\frac{3}{4}{\beta }^2\right)L^2+\frac{3}{4}{\alpha }^2\right){\Vert X_0-x^{*}\Vert }^2.$

证明：设Layapunov 函数为：

$\epsilon \left(k\right)=f\left(x_k\right)-f\left(x^{*}\right)+\frac{1}{4}{\Vert v_k\Vert }^2+\frac{1}{4}{\Vert \alpha \left(x_k-x^{*}\right)+v_k+\beta \nabla f\left(x_k\right)\Vert }^2$ .

$\begin{array}{c}\epsilon \left(k+1\right)-\epsilon \left(k\right)\\ =\frac{1}{4}\langle v_{k+1}-v_k,v_{k+1}+v_k\rangle +f\left(x_{k+1}\right)-f\left(x_k\right)\\ +\frac{1}{4}\langle \alpha \left(x_{k+1}\text{}-x_k\right)+v_{k+1}\text{}-v_k+\beta \left(\nabla f\left(x_{k+1}\right)-\nabla f\left(x_k\right)\right),\alpha \left(x_{k+1}+x_k\text{}-\text{}2x^{*}\right)+v_{k+1}+v_k+\beta \left(\nabla f\left(x_{k+1}\right)+\nabla f\left(x_k\right)\right)\rangle \end{array}$

$\begin{array}{c}\le \frac{1}{2}\langle v_{k+1}-v_k,v_k\rangle +\frac{1}{4}{\Vert v_{k+1}-v_k\Vert }^2+\langle \nabla f\left(x_k\right),x_{k+1}-x_k\rangle +\frac{L}{2}{\Vert x_{k+1}-x_k\Vert }^2\\ -\frac{1}{2}\langle \sqrt{s}\nabla f\left(x_k\right),\alpha \left(x_k-x^{*}\right)+v_k+\beta \nabla f\left(x_k\right)\rangle +\frac{1}{4}{\Vert \sqrt{s}\nabla f\left(x_k\right)\Vert }^2\\ =-\frac{\alpha \sqrt{s}}{2}{\Vert v_k\Vert }^2-\frac{\beta }{2\sqrt{s}}\langle \nabla f\left(x_{k+1}\right)-\nabla f\left(x_k\right),x_{k+1}-x_k\rangle +\frac{1}{4}{\Vert \alpha \sqrt{s}{v}_k+\beta \left(\nabla f\left(x_{k+1}\right)-\nabla f\left(x_k\right)\right)+\sqrt{s}\nabla f\left(x_k\right)\Vert }^2\\ +\frac{Ls}{2}{\Vert v_k\Vert }^2-\frac{\alpha \sqrt{s}}{2}\langle \nabla f\left(x_k\right),x_k-x^{*}\rangle -\frac{\beta \sqrt{s}}{2}{\Vert \nabla f\left(x_k\right)\Vert }^2+\frac{s}{4}{\Vert \nabla f\left(x_k\right)\Vert }^2.\end{array}$

由柯西–施瓦茨不等式，

$\begin{array}{l}{\Vert \alpha \sqrt{s}{v}_k+\beta \left(\nabla f\left(x_{k+1}\right)-\nabla f\left(x_k\right)\right)+\sqrt{s}\nabla f\left(x_k\right)\Vert }^2\\ \le 3{\alpha }^{2}s{\Vert v_k\Vert }^2+3{\beta }^2{\Vert \nabla f\left(x_{k+1}\right)-\nabla f\left(x_k\right)\Vert }^2+3s{\Vert \nabla f\left(x_k\right)\Vert }^2.\end{array}$

故

$\begin{array}{c}\epsilon \left(k+1\right)-\epsilon \left(k\right)\le -\frac{\alpha \sqrt{s}}{4}\left({\Vert v_k\Vert }^2+\langle \nabla f\left(x_k\right),x_k-x^{*}\rangle +\frac{\beta }{\alpha }{\Vert \nabla f\left(x_k\right)\Vert }^2\right)\\ -\frac{\beta }{2\sqrt{s}}\langle \nabla f\left(x_{k+1}\right)-\nabla f\left(x_k\right),x_{k+1}-x_k\rangle +\frac{3}{4}{\beta }^2{\Vert \nabla f\left(x_{k+1}\right)-\nabla f\left(x_k\right)\Vert }^2\\ +\left(\frac{3{\alpha }^{2}s}{4}+\frac{Ls}{2}-\frac{\alpha \sqrt{s}}{4}\right){\Vert v_k\Vert }^2+s{\Vert \nabla f\left(x_k\right)\Vert }^2\\ -\frac{\alpha \sqrt{s}}{4}\langle \nabla f\left(x_k\right),x_k-x^{*}\rangle -\frac{\beta \sqrt{s}}{4}{\Vert \nabla f\left(x_k\right)\Vert }^2.\end{array}$

由于$f\in {\mathcal{S}}_{\mu ,L}^1$ ，则有

${\Vert \nabla f\left(x_{k+1}\right)-\nabla f\left(x_k\right)\Vert }^2\le L\langle \nabla f\left(x_{k+1}\right)-\nabla f\left(x_k\right),x_{k+1}-x_k\rangle ,$

${\Vert \nabla f\left(x_k\right)\Vert }^2\le L\langle \nabla f\left(x_k\right),x_k-x^{*}\rangle .$

故

$\begin{array}{c}\epsilon \left(k+1\right)-\epsilon \left(k\right)\le -\frac{\alpha \sqrt{s}}{4}\left({\Vert v_k\Vert }^2+\langle \nabla f\left(x_k\right),x_k-x^{*}\rangle +\frac{\beta }{\alpha }{\Vert \nabla f\left(x_k\right)\Vert }^2\right)\\ -\left(\frac{\beta }{2L\sqrt{s}}-\frac{3}{4}{\beta }^2\right){\Vert \nabla f\left(x_{k+1}\right)-\nabla f\left(x_k\right)\Vert }^2\\ -\left(\frac{\alpha \sqrt{s}}{4}-\frac{3{\alpha }^{2}s}{4}-\frac{Ls}{2}\right){\Vert v_k\Vert }^2\\ -\left(\frac{\alpha \sqrt{s}}{4L}-s\right){\Vert \nabla f\left(x_k\right)\Vert }^2.\end{array}$ (11)

对于式(11)，若步长s满足条件

$\{\begin{array}{l}\frac{\beta }{2L\sqrt{s}}-\frac{3}{4}{\beta }^2\ge 0\hfill \\ \frac{\alpha \sqrt{s}}{4}-\frac{3{\alpha }^{2}s}{4}-\frac{Ls}{2}\ge 0\hfill \\ \frac{\alpha \sqrt{s}}{4L}-s\ge 0\hfill \end{array}$ ,

可得

$\epsilon \left(k+1\right)-\epsilon \left(k\right)\le -\frac{\alpha \sqrt{s}}{4}\left({\Vert v_k\Vert }^2+\langle \nabla f\left(x_k\right),x_k-x^{*}\rangle +\frac{\beta }{\alpha }{\Vert \nabla f\left(x_k\right)\Vert }^2\right),$ (12)

由柯西–施瓦茨不等式，

${\Vert \alpha \left(x_k-x^{*}\right)+v_k+\beta \nabla f\left(x_k\right)\Vert }^2\le 3{\alpha }^2{\Vert x_k-x^{*}\Vert }^2+3{\Vert v_k\Vert }^2+3{\beta }^2{\Vert \nabla f\left(x_k\right)\Vert }^2,$

故

$\begin{array}{c}\epsilon \left(k\right)\le {\Vert v_k\Vert }^2+f\left(x_k\right)-f\left(x^{*}\right)+\frac{3}{4}{\alpha }^2{\Vert x_k-x^{*}\Vert }^2+\frac{3}{4}{\beta }^2{\Vert \nabla f\left(x_k\right)\Vert }^2\\ \le {\Vert v_k\Vert }^2+f\left(x_k\right)-f\left(x^{*}\right)+\frac{\mu }{2}{\Vert x_k-x^{*}\Vert }^2+\frac{2\beta }{\alpha }{\Vert \nabla f\left(x_k\right)\Vert }^2\\ \le {\Vert v_k\Vert }^2+\langle \nabla f\left(x_k\right),x_k-x^{*}\rangle +\frac{2\beta }{\alpha }{\Vert \nabla f\left(x_k\right)\Vert }^2.\end{array}$ (13)

对比式(12)和式(13)中的各项，可得

$\epsilon \left(k+1\right)-\epsilon \left(k\right)\le -\frac{\alpha \sqrt{s}}{8}\epsilon \left(k\right).$

即

$\epsilon \left(k\right)\le {\left(1-\frac{\alpha \sqrt{s}}{8}\right)}^k\epsilon \left(0\right),$

$f\left(x_k\right)-f\left(x^{*}\right)\le \epsilon \left(k\right)\le {\left(1-\frac{\alpha \sqrt{s}}{8}\right)}^k\epsilon \left(0\right).$

设$X\left(0\right)=X_0$ ，$\dot{X}\left(0\right)=\nabla f\left(X_0\right)$ ，由于$f\in {\mathcal{S}}_{\mu ,L}^1$ ，则有

$f\left(X_0\right)-f\left(x^{*}\right)\le \frac{L}{2}{\Vert X_0-x^{*}\Vert }^2,\Vert \nabla f\left(X_0\right)\Vert \le L\Vert X_0-x^{*}\Vert$ .

$\begin{array}{c}\epsilon \left(0\right)=f\left(X_0\right)-f\left(x^{*}\right)+\frac{1}{4}{\Vert \nabla f\left(X_0\right)\Vert }^2+\frac{1}{4}{\Vert \nabla f\left(X_0\right)+\alpha \left(X_0-x^{*}\right)+\beta \nabla f\left(X_0\right)\Vert }^2\\ \le f\left(X_0\right)-f\left(x^{*}\right)+\left(1+\frac{3}{4}{\beta }^2\right){\Vert \nabla f\left(X_0\right)\Vert }^2+\frac{3}{4}{\alpha }^2{\Vert X_0-x^{*}\Vert }^2\\ =\left(\frac{L}{2}+\left(1+\frac{3}{4}{\beta }^2\right)L^2+\frac{3}{4}{\alpha }^2\right){\Vert X_0-x^{*}\Vert }^2.\end{array}$

综上，

$f\left(x_k\right)-f\left(x^{*}\right)\le C{\left(1-\frac{\alpha \sqrt{s}}{8}\right)}^k{\Vert x_0-x^{*}\Vert }^2,$

其中$C=\left(\frac{L}{2}+\left(1+\frac{3}{4}{\beta }^2\right)L^2+\frac{3}{4}{\alpha }^2\right){\Vert X_0-x^{*}\Vert }^2.$

3.2. 隐式欧拉格式

第二种离散格式是隐式欧拉格式，它的近似规则如下：

$x_{k+1}-x_k=\sqrt{s}{v}_{k+1},\sqrt{s}{\nabla }^{2}f\left(x_{k+1}\right)v_{k+1}\approx \nabla f\left(x_{k+1}\right)-\nabla f\left(x_k\right)\$.$

由隐式欧拉格式离散式(9)可得如下优化算法：

$\{\begin{array}{l}{x}_{k+1}-x_k=\sqrt{s}{v}_{k+1}\hfill \\ v_{k+1}-v_k=-\alpha \sqrt{s}{v}_{k+1}-\beta \left(\nabla f\left(x_{k+1}\right)-\nabla f\left(x_k\right)\right)-\sqrt{s}\nabla f\left(x_{k+1}\right)\hfill \end{array}$ (14)

定理3.2. 假设目标函数$f\in {\mathcal{S}}_{\mu ,L}^1$ ，对于隐式欧拉格式产生的迭代点序列${\left\{x_k\right\}}_{k\in N}$ ，当系数$\alpha ,\beta$ 满足$\{\begin{array}{l}\frac{3}{4}{\alpha }^2\le \frac{\mu }{2}\hfill \\ \beta \le \frac{8}{3\alpha }\hfill \\ \alpha \ge 0\hfill \end{array}$ ，步长s满足$0\le s\le \frac{1}{L}$ 时，收敛速率满足

$f\left(x_k\right)-f\left(x^{*}\right)\le {\left(\frac{1}{1+\frac{\alpha \sqrt{s}}{4}}\right)}^{k}C{\Vert x_0-x^{*}\Vert }^2.$

其中$C=\left(\frac{L}{2}+\left(1+\frac{3}{4}{\beta }^2\right)L^2+\frac{3}{4}{\alpha }^2\right){\Vert X_0-x^{*}\Vert }^2.$

证明：设Layapunov函数为：

$\epsilon \left(k\right)=f\left(x_k\right)-f\left(x^{*}\right)+\frac{1}{4}{\Vert v_k\Vert }^2+\frac{1}{4}{\Vert \alpha \left(x_k-x^{*}\right)+v_k+\beta \nabla f\left(x_k\right)\Vert }^2.$

$\begin{array}{c}\epsilon \left(k+1\right)-\epsilon \left(k\right)\\ =\frac{1}{4}\langle v_{k+1}-v_k,v_{k+1}+v_k\rangle +f\left(x_{k+1}\right)-f\left(x_k\right)\\ +\frac{1}{4}\langle \alpha \left(x_{k+1}\text{}-\text{}{x}_k\right))+v_{k+1}-v_k+\beta \left(\nabla f\left(x_{k+1}\right)-\nabla f\left(x_k\right)\right),\alpha \left(x_{k+1}+x_k-2x^{*}\right)+v_{k+1}+v_k+\text{}\beta \left(\nabla f\left(x_{k+1}\right)+\nabla f\left(x_k\right)\right)\rangle \end{array}$

$\begin{array}{c}\le \frac{1}{2}\langle v_{k+1}-v_k,v_{k+1}\rangle -\frac{1}{4}{\Vert v_{k+1}-v_k\Vert }^2+\langle \nabla f\left(x_{k+1}\right),x_{k+1}-x_k\rangle \\ -\frac{1}{2}\langle \sqrt{s}\nabla f\left(x_{k+1}\right),\alpha \left(x_{k+1}-x^{*}\right)+v_{k+1}+\beta \nabla f\left(x_{k+1}\right)\rangle -\frac{1}{4}{\Vert \sqrt{s}\nabla f\left(x_{k+1}\right)\Vert }^2\\ =-\frac{\alpha \sqrt{s}}{2}{\Vert v_{k+1}\Vert }^2-\frac{\beta }{2\sqrt{s}}\langle \nabla f\left(x_{k+1}\right)-\nabla f\left(x_k\right),x_{k+1}-x_k\rangle \\ -\frac{1}{4}{\Vert \alpha \sqrt{s}{v}_{k+1}+\beta \left(\nabla f\left(x_{k+1}\right)-\nabla f\left(x_k\right)\right)+\sqrt{s}\nabla f\left(x_{k+1}\right)\Vert }^2-\frac{\alpha \sqrt{s}}{2}\langle \nabla f\left(x_{k+1}\right),x_{k+1}-x^{*}\rangle \\ -\frac{\beta \sqrt{s}}{2}{\Vert \nabla f\left(x_{k+1}\right)\Vert }^2-\frac{s}{4}{\Vert \nabla f\left(x_{k+1}\right)\Vert }^2.\end{array}$

由柯西–施瓦茨不等式，

$\begin{array}{l}{\Vert \alpha \sqrt{s}{v}_k+\beta \left(\nabla f\left(x_{k+1}\right)-\nabla f\left(x_k\right)\right)+\sqrt{s}\nabla f\left(x_k\right)\Vert }^2\\ \le 3{\alpha }^{2}s{\Vert v_k\Vert }^2+3{\beta }^2{\Vert \nabla f\left(x_{k+1}\right)-\nabla f\left(x_k\right)\Vert }^2+3s{\Vert \nabla f\left(x_k\right)\Vert }^2.\end{array}$

故

$\begin{array}{c}\epsilon \left(k+1\right)-\epsilon \left(k\right)\le -\frac{\alpha \sqrt{s}}{2}\left({\Vert v_{k+1}\Vert }^2+\langle \nabla f\left(x_{k+1}\right),x_{k+1}-x^{*}\rangle +\frac{\beta }{\alpha }{\Vert \nabla f\left(x_{k+1}\right)\Vert }^2\right)\\ -\frac{\beta }{2\sqrt{s}}\langle \nabla f\left(x_{k+1}\right)-\nabla f\left(x_k\right),x_{k+1}-x_k\rangle -\frac{3{\alpha }^{2}s}{4}{\Vert v_{k+1}\Vert }^2\\ -\frac{3{\beta }^2}{4}{\Vert \nabla f\left(x_{k+1}\right)-\nabla f\left(x_k\right)\Vert }^2-s{\Vert \nabla f\left(x_{k+1}\right)\Vert }^2.\end{array}$

由于$f\in {\mathcal{S}}_{\mu ,L}^1$ ，则有

$\langle \nabla f\left(x_{k+1}\right)-\nabla f\left(x_k\right),x_{k+1}-x_k\rangle \ge \mu {\Vert x_{k+1}-x_k\Vert }^2.$

故

$\epsilon \left(k+1\right)-\epsilon \left(k\right)\le -\frac{\alpha \sqrt{s}}{2}\left({\Vert v_{k+1}\Vert }^2+\langle \nabla f\left(x_{k+1}\right),x_{k+1}-x^{*}\rangle +\frac{\beta }{\alpha }{\Vert \nabla f\left(x_{k+1}\right)\Vert }^2\right).$ (15)

由柯西–施瓦茨不等式，

${\Vert \alpha \left(x_k-x^{*}\right)+v_k+\beta \nabla f\left(x_k\right)\Vert }^2\le 3{\alpha }^2{\Vert x_k-x^{*}\Vert }^2+3{\Vert v_k\Vert }^2+3{\beta }^2{\Vert \nabla f\left(x_k\right)\Vert }^2.$

故

$\begin{array}{c}\epsilon \left(k+1\right)\le {\Vert v_{k+1}\Vert }^2+f\left(x_{k+1}\right)-f\left(x^{*}\right)+\frac{3}{4}{\alpha }^2{\Vert x_{k+1}-x^{*}\Vert }^2+\frac{3}{4}{\beta }^2{\Vert \nabla f\left(x_{k+1}\right)\Vert }^2\\ \le {\Vert v_{k+1}\Vert }^2+f\left(x_{k+1}\right)-f\left(x^{*}\right)+\frac{\mu }{2}{\Vert x_{k+1}-x^{*}\Vert }^2+\frac{2\beta }{\alpha }{\Vert \nabla f\left(x_{k+1}\right)\Vert }^2\\ \le {\Vert v_{k+1}\Vert }^2+\langle \nabla f\left(x_{k+1}\right),x_{k+1}-x^{*}\rangle +\frac{2\beta }{\alpha }{\Vert \nabla f\left(x_{k+1}\right)\Vert }^2.\end{array}$ (16)

对比式(15)和式(16)中的各项，可得

$\epsilon \left(k+1\right)-\epsilon \left(k\right)\le -\frac{\alpha \sqrt{s}}{4}\epsilon \left(k+1\right).$

即

$\epsilon \left(k+1\right)\le \frac{1}{1+\frac{\alpha \sqrt{s}}{4}}\epsilon \left(k\right),$

$f\left(x_k\right)-f\left(x^{*}\right)\le \epsilon \left(k\right)\le {\left(\frac{1}{1+\frac{\alpha \sqrt{s}}{4}}\right)}^k\epsilon \left(0\right).$

设$X\left(0\right)=X_0$ ，$\dot{X}\left(0\right)=\nabla f\left(X_0\right)$ ，由于$f\in {\mathcal{S}}_{\mu ,L}^1$ ，则有

$f\left(X_0\right)-f\left(x^{*}\right)\le \frac{L}{2}{\Vert X_0-x^{*}\Vert }^2,\Vert \nabla f\left(X_0\right)\Vert \le L\Vert X_0-x^{*}\Vert$ .

$\begin{array}{c}\epsilon \left(0\right)=f\left(X_0\right)-f\left(x^{*}\right)+\frac{1}{4}{\Vert \nabla f\left(X_0\right)\Vert }^2+\frac{1}{4}{\Vert \nabla f\left(X_0\right)+\alpha \left(X_0-x^{*}\right)+\beta \nabla f\left(X_0\right)\Vert }^2\\ \le f\left(X_0\right)-f\left(x^{*}\right)+\left(1+\frac{3}{4}{\beta }^2\right){\Vert \nabla f\left(X_0\right)\Vert }^2+\frac{3}{4}{\alpha }^2{\Vert X_0-x^{*}\Vert }^2\\ =\left(\frac{L}{2}+\left(1+\frac{3}{4}{\beta }^2\right)L^2+\frac{3}{4}{\alpha }^2\right){\Vert X_0-x^{*}\Vert }^2.\end{array}$

综上，

$f\left(x_k\right)-f\left(x^{*}\right)\le {\left(\frac{1}{1+\frac{\alpha \sqrt{s}}{4}}\right)}^{k}C{\Vert x_0-x^{*}\Vert }^2,$

其中$C=\left(\frac{L}{2}+\left(1+\frac{3}{4}{\beta }^2\right)L^2+\frac{3}{4}{\alpha }^2\right){\Vert X_0-x^{*}\Vert }^2.$

4. 数值实验

在本章中，我们将对第三章中所得的算法进行数值实验，验证算法的性能。同时使用NAG算法与梯度下降法作为对比，证明算法的实用性。

由于本文考虑的目标函数$f\in {\mathcal{S}}_{\mu ,L}^1$ ，为了方便获取函数的$\mu ,L$ 值，我们选取了CUTest数据集中的无约束二次函数问题作为测试函数。由于我们提出的算法中含有不定系数$\alpha ,\beta$ ，且它们往往与目标函数的$\mu ,L$ 值相关，对于每个测试问题，事先将各个系数调整为合适的值。每种算法都使用相同的固定步长。

算法终止条件：$\Vert \nabla f\left(x_k\right)\Vert \le {10}^{-8}$ 或$\Vert \nabla f\left(x_{k+1}\right)-\nabla f\left(x_k\right)\Vert \le {10}^{-16}$ 。

Table 1. Comparison of average number of iterations and computation time of various algorithms when the objective function is a quadratic function

表1. 目标函数为二次函数时，各个算法的平均迭代次数与运算时间对比

	显式欧拉格式	隐式欧拉格式	NAG算法	梯度下降法
平均迭代次数	8941	1507	1836	10,447
平均运行时间(s)	0.007131	0.001376	0.001427	0.007559

由表1可知，隐式欧拉格式在平均迭代次数上表现明显优于其他算法，在平均运行时间上略优于NAG算法，明显优于梯度下降法，这一结果表明隐式欧拉格式为加速梯度算法，且数值表现优于NAG算法。显示欧拉格式由于受到步长的限制，在数值实验中的表现与梯度下降法类似，没有起到加速效果。

5. 结论

本文主要研究的是从ODE中得到新的加速梯度算法。本文考虑的不再是一个固定的ODE，而是一个系数不定的ODE：

$\ddot{X}+\alpha \dot{X}+\beta {\nabla }^{2}f\left(X\right)\dot{X}+\nabla f\left(X\right)=0$ ,

通过构造合适的Layapunov函数，证明了系数$\alpha ,\beta$ 在满足什么条件下，该ODE具有较快的收敛速率。同时，本文使用了两种不同的离散格式：显式欧拉格式、隐式欧拉格式对该ODE进行离散，得到了相应的优化算法，并通过构造合适的Layapunov函数，分别证明了这两种算法的收敛速率。最后，本文对于提出的优化算法进行了初步的数值实验。分别使用CUTest数据集中的无约束二次函数问题作为测试集，验证了算法的性能，并以NAG算法和梯度下降法作为对比。结果表明，当目标函数为二次函数时，隐式欧拉格式算法的数值表现优于NAG算法。