计算科学 - 众所周知，一些优化问题等价于时间步长吗？ - 吾爱随笔录

众所周知，一些优化问题等价于时间步长吗？

计算科学优化参考请求时间积分

2021-12-18 21:52:07

给定一个期望的状态 $y_0$ 和一个正则化参数 $\beta \in \mathbb R$ ，考虑寻找状态的问题 $y$ 和一个控件 $u$ 尽量减少功能

\frac{1}{2} ‖ y - y_{0} ‖^{2} + \frac{β}{2} ‖ u ‖^{2}

$\begin{equation} \frac{1}{2} \| y - y_0 \|^2 + \frac{\beta}{2} \| u \|^2 \end{equation}$ 受约束

A y = u .

$\begin{equation} Ay = u. \end{equation}$ 为简单起见，我们可以考虑

y, y_{0}, u \in R^{n}

$y, y_0, u \in \mathbb R^n$ 和

A \in R^{n \times n}

$A \in \mathbb R^{n \times n}$ 。

形成拉格朗日，寻找静止点，并消除控制 $u$ 我们得到一阶条件

\begin{aligned} A^{T} λ & = y_{0} - y \\ A y & = \frac{1}{β} λ \end{aligned}

$\begin{align*} A^T \lambda &= y_0 - y \\ Ay &= \frac{1}{\beta} \lambda \end{align*}$ 预乘第一个方程中的

A

$A$ 和第二个方程中的

A^{T}

$A^T$ ，我们可以写出正规方程

\begin{aligned} (I + β A A^{T}) λ & = β A y_{0} \\ (I + β A^{T} A) y & = y_{0} \end{aligned}

$\begin{align} (I + \beta A A^T) \lambda &= \beta A y_0 \\ (I + \beta A^T A) y &= y_0 \end{align}$ 我们可以将这些解释为微分方程的反向欧拉近似的单步

\begin{aligned} \frac{\partial λ}{\partial b} & = - A A^{T} λ + A y_{0}, λ (0) = 0 \\ \frac{\partial y}{\partial b} & = - A^{T} A y, y (0) = y_{0} \end{aligned}

$\begin{align} \frac{\partial \lambda}{\partial b} &= -A A^T \lambda + A y_0, \quad \lambda(0) = 0 \\ \frac{\partial y}{\partial b} &= -A^T A y, \quad y(0) = y_0 \end{align}$ 使用伪时间步

β

$\beta$ 。

我的问题：这种联系众所周知吗？它是否在时间步长或优化的标准处理中进行了讨论？（对我来说，它似乎在它们之间提供了某种直观的联系。）

这个想法似乎很简单，必须众所周知，但是搜索文献或与人交谈都没有给我一个很好的资源来讨论这个问题。我发现的最接近的是 O. Scherzer 和 J. Weichert 的论文（J. Math Imaging Vision 12 (2000) pp. 43-63），它在摘要的第一句话（！）中说明了联系，但没有提供任何参考资料或深入探索联系。

理想情况下，我正在寻找一个不仅说明连接而且探索一些后果的参考（例如，可以想象使用廉价的前向 Euler 步骤对优化问题进行预处理）。

3个回答

正如 Jed Brown 所提到的，非线性优化中的梯度下降和动态系统的时间步长之间的联系以某种频率被重新发现（可以理解，因为它连接了两个看似不同的领域，因此它与数学思维非常令人满意）。但是，它很少被证明是有用的连接，尤其是在您描述的上下文中。

在逆问题中，人们对求解（不适定）算子方程感兴趣，其中不在的范围内。（您的最优控制问题可以看作是和的一个实例。）几种正则化策略（例如 Tikhonov 或 Landweber）可以解释为单个伪时间某一类的步骤。然后想法是使用正则化参数的解释作为步长来获得参数的一些（自适应，后验）选择规则 - 逆问题中的基本问题 - 并可能做出多个伪时间步骤来接近真正的、非正则化的解决方案（类似于 $F(u)=y^\delta$ $y^\delta$ $F$ $F=A^{-1}$ $y^\delta = y_0$ 数值延续）。这有时称为连续正则化，通常在水平集方法的上下文中讨论；例如，参见 Kaltenbacher、Scherzer、Neubauer 的第 6.1 章：非线性病态问题的迭代正则化方法（de Gruyter，2008 年）。

这个想法反复出现的第二个背景是非线性优化：如果你看一下的梯度下降步骤，那么您可以将其解释为动力系统 的正向欧拉步。足够小，乍一看，这只会产生这种方法收敛的不太令人惊讶的观察结果。当你观察动态系统并问自己所谓梯度流 $\min_x f(x)$

x^{k + 1} = x^{k} - γ_{k} \nabla f (x^{k}),

$x^{k+1} = x^k - \gamma_k \nabla f(x^k),$

\dot{x} (t) = - \nabla f (x (t)), x (0) = x^{0} .

$\dot x(t) = -\nabla f(x(t)),\qquad x(0) = x^0.$

γ_{k}

$\gamma_k$

x (t)

$x(t)$ 有（或应该有），独立于梯度下降，以及这是否可能不会导致比标准欧拉更合适的时间步进（并因此优化）方法。我脑海中的一些例子：

是否存在梯度流存在的自然函数空间？如果是这样，您的梯度步骤应该取自相同的空间（即，离散化应该是一致的）。例如，这导致计算梯度关于不同内积（有时称为Sobolev 梯度）的 Riesz 表示，并且在实践中导致收敛速度更快的预条件迭代。
也许不应该属于向量空间，而是属于流形（例如，对称正定矩阵），或者梯度流应该保持的某个范数。在这种情况下，您可以尝试应用结构保持时间步长方案（例如，涉及相对于适当的李群或几何积分器的回拉）。 $x$ $x$
如果不可微而是凸的，则前向 Euler 步骤对应于次梯度下降方法，由于步长限制，该方法可能非常慢。另一方面，隐式欧拉步骤对应于近点方法，没有此类限制适用（并且因此在例如图像处理中变得非常流行）。 $f$
同样，通过外推步骤可以显着加速此类方法。激励这些的一种方法是观察标准一阶方法不得不使许多小步骤接近最小化，因为梯度方向“振荡”（想想为什么共轭梯度优于最速下降的标准说明）。为了解决这个问题，可以通过不求解一阶动力系统，而是求解阻尼二阶系统来“抑制”迭代： for suitably chosen . 通过适当的离散化，这将导致形式的迭代（称为Polyak 的重球方法）
$a_{1} \ddot{x} (t) + a_{2} \dot{x} (t) = - \nabla f (x (t))$ $a_1 \ddot x(t) + a_2 \dot x(t) = -\nabla f(x(t))$ $a_1,a_2$ $x^{k + 1} = x^{k} - γ_{k} \nabla f (x^{k}) + α_{k} (x^{k} - x^{k - 1})$ $x^{k+1} = x^k - \gamma_k \nabla f(x^k) + \alpha_k (x^k - x^{k-1})$ (其中取决于）。近点方法也存在类似的想法，例如，参见 Dirk Lorenz 和 Thomas Pock 的论文http://arxiv.org/pdf/1403.3522.pdf。 $\gamma_k,\alpha_k$ $a_1,a_2$

（我应该补充一点，据我所知，在大多数情况下，对于算法的推导或收敛证明来说，作为一个动态系统的解释并不是绝对必要的；有人可能会争辩说，像“隐式与显式”或李导数这样的想法实际上比动态系统或梯度下降方法更基础。不过，从另一个角度看待问题永远不会有坏处。）

编辑：我刚刚从第二个上下文中偶然发现了一个很好的例子，其中 ODE 解释用于推断 Nesterov 的外梯度方法的属性并提出改进建议： http://arxiv.org/pdf/1503.01243.pdf （请注意，这也是Jed Brown 观点的一个例子，作者基本上重新发现了上面的第 4 点，但显然没有意识到 Polyak 的算法。）

编辑 2：作为一个指示，你可以走多远，请参阅http://arxiv.org/pdf/1509.03616v1.pdf的第 5 页。

虽然我还没有看到你在这里写下的确切公式，但我一直看到人们“重新发现”与集成一些瞬态系统的联系，并继续写下一种代数等价于一种形式的算法或另一种现有的梯度下降或类似牛顿的方法，并且没有引用其他任何人。我认为它不是很有用，因为结论基本上是“只要你采取足够小的步骤，该方法最终会收敛到局部最小值”。嗯，2014 年是 Philip Wolfe 的论文发表 45 周年，该论文展示了如何以有原则的方式做到这一点。从伪瞬态延拓和相关方法（如 Levenberg-Marquardt）中获得 q-二次或 q-超线性收敛也有很好的理论。

如果您想要使用类似牛顿的公式从一位拥有 600 多篇论文的数学家那里求解代数方程（即经典伪瞬态延拓）来重新发现这种重新发现的实例（所以也许他会证明您觉得有趣的事情），请查看“ AG Ramm [1] 的动态系统方法。

如果通过考虑瞬态系统获得的直觉导致更快或更可靠的实用算法，我认为我们会看到关于该主题的高引用文章。我认为 Nocedal 和 Wright 的引用超过 13000 次，而 Ramm 的书大约有 80 次（大部分是自引用），这并不神秘。

[1] 我可以建议您不要告诉 Ramm 教授，他的 DSM 在代数上等同于数十年来无数工程包中的东西，否则您可能会被喊出房间。#研究生记忆

如果 ODE 方法有助于优化，是否有一个非常简单的示例问题可以证明这一点？
稻草人：有没有一个 ODE 求解器在或正如 Christian Clason 为建议的那样，说 Rosenbrock 函数，在 2d 还是 10d 中？如果这很愚蠢，有人有更好的稻草人吗？（注意“合理”，而不是“与最先进的优化器竞争”。我想需要减小步长/容差，也许需要一个僵硬的求解器。）
$\qquad \dot{ x } = - \nabla f( x )$
$\quad \ddot{ x } = \beta \dot{ x } - \alpha \nabla f( x ) \ \$
$f$

在实践中，“太大”的步骤比“太小”更成问题——振荡是混乱的。
我天真地认为控制理论会有所帮助。数字食谱 p。915描述了ODE的
PI自适应步长控制，但我不知道这是否在实践中使用。

其它你可能感兴趣的问题

上一篇对数并行缩放/效率图下一篇处理科学代码中许多常量、变量的 C++ 最佳实践