常微分方程与优化算法_汇旺-汇旺娱乐农家乐民宿服务中心

常微分方程与优化算法作者：佚名发布时间：2024-04-22

本文介绍某些优化算法可以表示为对应常微分方程的离散形式。最后谈谈个人关于如何利用这一关系进行算法设计的经验。（封面图为网络下载，如有版权问题，请图片原作者及时联系。）

本文分享一下我们对常微分方程（Ordinary Differential Equation，简称ODE）与优化算法的关系的一些理解。概括地说，就是某些优化算法可以表示成对应常微分方程的离散形式。这里，我们不做常微分方程的解的存在性讨论，而只是给出示意性的描述。

我们首先用梯度下降和Nesterov加速算法来举例说明常微分方程与优化算法的关系。最后分享一下我们对如何利用这一关系指导算法设计的经验。

梯度下降是用得最多的优化算法之一。让我们回顾一下这个算法。假设函数 $f$ 是一个凸函数，我们想找到 $f$ 的最小值点，亦即，我们想求解下列问题：

$\\begin{align*}\\min_{x}f(x)\ ag{2.1}。 \\end{align*}$

我们知道 $f$ 在点 $x$ 的梯度 $\ abla f(x)$ 为 $f$ 在 $x$ 处的值增加最快的方向。因此， $-\ abla f(x)$ 为 $f$ 在 $x$ 处减少最快的方向。为求解 $(2.1)$ ，梯度下降法从一个任意的给定点 $x_0$ 开始，沿着 $-\ abla f(x_0)$ 的方向走到点 $x_1$ ，再沿着 $-\ abla f(x_1)$ 的方向前进到点 $x_2$ ，接着用相似的方式前进，直到某个停止条件满足为止。停止条件可以是到达了指定的最大行驶步数，或者是前进过程中两个相邻的点 $x_k$ 和 $x_{k+1}$ （分别表示前进 $k$ 次与 $k+1$ 次到达的点）之间的距离非常的接近（表示在 $x_k$ 处沿着 $-\ abla f(x_k)$ 的方向行进，不再能减少 $f$ 的值，亦即，我们到了 $f$ 的最小值附近）。

下面，我们写出梯度下降的迭代公式。记 $x_k$ 为前进 $k$ 次到达的点，那么我们有

$x_{k+1}=x_k-h\ abla f(x_k)，\ ag{2.2}$

其中， $h$ 为沿 $-\ abla f(x_k)$ 方向行进的步长。接下来，我们推导 $(2.2)$ 所对应的常微分方程。我们将 $(2.2)$ 变形，得到

$\\frac{x_{k+1}-x_k}{h}=-\ abla f(x_k)。\ ag{2.3}$

观察 $(2.3)$ ，我们可知 $(2.3)$ 为下列常微分方程的有限差分下的显式欧拉离散：

$x’(t)=-\ abla f(x(t))。\ ag{2.4}$

这一节，我们介绍算法 $(2.2)$ 的加速算法。一般地，算法 $(2.2)$ 具有一阶收敛性。牛顿法可以达到二阶的收敛性（可以理解为比算法 $(2.2)$ 更快）。因此理论上牛顿法更快速。但牛顿法需要求解函数 $f$ 的二阶导数，在高维度以及 $f$ 不可以求二次导数的情况下，会显得不太适用。

一般地，用 $f$ 的一阶导数，我们能得到一阶收敛性，用 $f$ 的二阶导数，可以得到二阶收敛性，想要得到更高阶收敛性，我们需要 $f$ 更高阶导数的信息。

Nesterov提出了加速的办法，使得我们可以只用函数 $f$ 的梯度的情况下，达到高阶的收敛速度。具体地，Nesterov算法设置起点 $x_0$ ， $y_0=x_0$ ，并使用下列公式生成迭代序列：

$\\begin{align*}x_k=y_{k-1}-s\ abla f(y_{k-1})，\\\\ y_{k}=x_k+\\frac{k-1}{k+2}(x_{k}-x_{k-1})， \\end{align*}\ ag{2.5}$

其中 $s$ 为选取的步长。Nesterov证明了当 $f$ 的梯度 $\ abla f$ 是 $L$ —Lipschitz连续且 $s\\leq \\frac{1}{L}$ 时，Nesterov算法具有二阶收敛性。

下面，我们来推导算法 $(2.5)$ 所对应的ODE。下面的推导来自于论文：A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights[1]。由公式 $(2.5)$ ，我们可以得到

$\\frac{x_{k+1}-x_k}{\\sqrt{s}}=\\frac{k-1}{k+2}\\frac{(x_k-x_{k-1})}{\\sqrt{s}}-\\sqrt{s}\ abla f(y_{k})。\ ag{2.6}$

我们假设序列 $\\{x_k\\}$ 是由函数 $x(t)$ 离散取值得到的，并且有关系 $x_k\\approx x(k\\sqrt{s})$ ，即 $x_k$ 为函数 $x(t)$ 在点 $k\\sqrt{s}$ 的近似值。因此，使用泰勒公式，我们有

$\\frac{x_{k+1}-x_k}{\\sqrt{s}}\\approx \\dot{x}(k\\sqrt{s})+\\frac{1}{2}\\ddot{x}(k\\sqrt{s})\\sqrt{s}+o(\\sqrt{s})。 \ ag{2.7}$

类似地，我们有

$\\frac{x_{k}-x_{k-1}}{\\sqrt{s}}\\approx \\dot{x}(k\\sqrt{s})-\\frac{1}{2}\\ddot{x}(k\\sqrt{s})\\sqrt{s}+o(\\sqrt{s}) \ ag{2.8}$

以及

$\\sqrt{s}\ abla f(y_k)\\approx \\sqrt{s}\ abla f(x_k)+o(\\sqrt{s})。\ ag{2.9}$

因此，我们从 $(2.7)-(2.9)$ 中得到

$\\dot{x}(t)+\\frac{1}{2}\\ddot{x}(t)\\sqrt{s}=\\frac{\\frac{t}{\\sqrt{s}}-1}{\\frac{t}{\\sqrt{s}}+2}\\big(\\dot{x}(t)-\\frac{1}{2}\\ddot{x}(t)\\sqrt{s}\\big)-\\sqrt{s}\ abla f(x_k)+o(\\sqrt{s})。\ ag{2.10}$

整理 $(2.10)$ ，我们得到

$\\frac{t+\\frac{1}{2}\\sqrt{s}}{t+2\\sqrt{s}}\\ddot{x}+\\frac{3}{t+2\\sqrt{s}}\\dot{x}+\ abla f(x)+o(\\sqrt{s})=0。\ ag{2.11}$

我们让 $s$ 趋近于 $0$ ，得到

$\\ddot{x}+\\frac{3}{t}\\dot{x}+\ abla f(x)=0。\ ag{2.12}$

等式 $(2.12)$ 即为算法 $(2.5)$ 对应的常微分方程。

我们需要注意是，算法的ODE形式与离散形式并不完全等价，这是因为对ODE进行离散后，离散算法较ODE有了误差。这些误差累积导致最后离散的算法不收敛。因此，我们需要根据每个ODE的具体形式，设计适合的离散算法。

在很多时候，我们初始想出来的优化算法并不收敛，编程实现的时候总不能得到满意的结果，这个时候，找到算法的ODE形式，再用其他方式重新离散ODE，能让我们得到更多的备选算法方案。例如，论文A Variational Perspective on Accelerated Methods[2]中，针对类似 $(2.12)$ 的ODE用不同的方法离散，能得到不同的加速算法。

[1]

A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: https://jmlr.org/papers/volume17/15-084/15-084.pdf

[2]

A Variational Perspective on Accelerated Methods: https://arxiv.org/abs/1603.04245

> 上一篇：抖音做直播卖货需要办什么手续吗？下一篇：探索提升城乡基层治理效能有效路径