从建模的角度说，对一个确定性的问题（如果有随机在里面，就值得另外讲一讲），有两种很常用的建模思路。一种是解方程，包括线性方程、ODE、PDE，另一种是解优化问题，应用非常广泛，比如最优运输、最优控制、图像处理、神经网络。这两个思路息息相关，简单来说，“一阶导数为零”将优化问题转化为等式问题。利用这个思路，PDE的分析有一种方法是构造energy function，通过energy递减来分析存在唯一性。（这种分析方法在ODE领域被称作Lyapunov稳定性分析，最早是用来研究动力系统稳定性的，广泛用于控制论中。知乎有很多从控制的角度理解Lyapunov的文章，比如枕月：(7)基于Lyapunov直接法的非线性系统V(x)构造与分析。后来用于证明优化算法的收敛性和收敛速度。对不同算法如何设计Lyapunov函数依然是我无法理解的玄学（艺术）领域。）应用的层面，用来解方程的一些算法可以自然的用来解对应的优化问题，比如牛顿法。
先来介绍一些常见的优化算法。大多数算法都是迭代法，每一步可由等式定义，或由优化问题定义（proximal point）。之所以有用优化问题定义的迭代方法，是因为有些函数的某种特定类型的优化问题（如proximal point）容易计算，例如 的proximal point有analytical solution，其他如
、
、
及对应的Legendre transform函数的proximal point都有简单算法计算。
1. 求解单个函数问题 的一阶gradient descent (gd) 系列算法。(explicit) gradient descent的优点在于容易计算，只需要gradient信息，缺点是stepsize不能太大，
是L-Lip时最大步长是
，收敛速度是
（额外有strongly convexity时，即dual fn也有Lip导数时，有线性收敛速度）。（implicit）proximal point优点在于步长不影响收敛，缺点是难以计算，除非prox map有explicit formula，否则每一步要解一个优化问题。这一系列算法包括以下四种代表算法（一些带projection的算法可把projection看成proximal step）。
2. Nesterov 加速算法，收敛速度为只用一阶导数信息的最快速度 。另外还有引入momentum的算法，和NN里常用的Adam。
3. 不可导函数用subgradient代替gradient。
4. 两个（或多个）函数的和。这两个函数可以有不同的性质，比如一个可导一个不可导，这就相当于把不同的算法粘合在一起。例如ADMM、primal-dual、forward-backward等。
5. 利用二阶导数。牛顿法： ，
代表f 的Hessian。收敛速度快（quadratic），缺点在于有时候二阶导数无法得到，或者inverse算起来太慢，因此就有很多模拟方法，比如NN里常用的L-BFGS。另一个缺点是对初值有要求。把 f 的Hessian换成另一个函数 h 的Hessian可得到natural gradient descent。有一些研究将二阶算法和一阶结合来加速收敛。
6. 引入随机性。 比如解 代替
，或像NN一样在gradient上加随机项，或作splitting的时候随机选择需要优化的部分。
=================================================
通过算法与ODE和优化问题的关系，我们可以从有几种不同角度可以理解离散的优化算法。这些角度一方面可以指导设计优化算法，另一方面可以当作工具分析收敛性和收敛速度。
考虑迭代算法，大部分算法是靠等式定义的，比如gradient descent，有小部分是每一步要解优化问题比如ADMM，这种算法可能会很慢因为有内循环。一种理解前一种算法的思路是把每一步的等式写成对应的优化问题。以下给出几个例子。
Gradient descent，每一步相当于解。把二次项看成拉格朗日项或者penalty，意义是在上一步的周围对 f 的线性模拟求最小值。另外，如果f 的gradient是L-Lip，常取
，这时上面那个优化问题是f 的一个上界模拟，从approximation的角度可以看作每次优化一个上界估计。
Proximal method，本身的定义方法就是 。如果把二次项看成拉格朗日项，那么就是在上一步的附近找 f 的最小值。这里有一些变种，比如把norm换成其他norm（当
时，凑一个特别的norm可以让每一步变成对g 求proximal point，抵消掉K的影响，而且这样得出的算法和forward-backward算法一样，应该是quadratic的特殊性导致）。
Mirror descent可写成 ，和gd一样可以看成在上一步的附近找f 的线性模拟的最小值，但是这个“附近”是用Bregman div 定义的，而不是欧氏距离。
Bregman proximal的定义是 ，即，在上一步的附近（Bregman意义下）找 f 的最小值。
Newton method可写成 ，也就是把“附近的概念”用Hessian-induced metric来定义。Natural gradient descent类似，是用h的Hessian构造距离。
综上，常用的表示距离的函数是Bregman div和 。把
用二次多项式代替时，Bregman div可近似成
。
Forward-backward方法，等式是 ，可以写成FB方法原本的形式：
，变形可得
，即线性模拟
并求proximal。也可以变形成Bregman div的形式：
，后面那两项一个加一个减，意义就有点迷了。
Nesterov算法的这种理解也有人做[1]，只不过感觉还是没有触及本质，依然是代数计算。
在抽象空间上，这种思路可以方便地定义算法（只需要有“距离”的定义）。比如Wasserstein-2空间，下降算法的定义 ，是类比proximal point method（不需要导数的定义，虽然W-space有“导数”的定义）。【取其他“距离”会如何？比如KL。KL可以看成一个Bregman div。Fisher metric呢？】
同一种格式可以对应不同的优化问题（等式对优化问题是一对多的）。比如Mirror descent也对应 （或者把
换成
），这个问题直观理解起来没有上面的那种interpretation容易，但加一些参数可以推广成Dual averaging method。
这种理解角度可以用来设计算法或作算法分析。做分析就是用每一步的优化问题给出不等式，再利用不等式分析误差变化。设计算法的思路是，每一步在neighbor上“尽量”优化原始问题，加上penalty term为了控制每一步不要走得太远。Penalty term的选择有时为了更好的收敛速度（quadratic 提升convexity），有时为了简化计算，当然如果设计的penalty同时结合这两种优点是最好的。其实设计优化算法有很多思路都和control的思路很接近，比如这种每一步解一个优化问题的思路就很像这种控制的设计思路（Picnicraft：CLF-CBF Controller）。
上节提到，优化算法的每一步有时以等式定义，有时以优化问题定义。靠等式定义的算法可以看成是某个ODE的离散，用优化问题定义的算法可以通过optimality condition转换成等式，从而也看成是ODE的离散。通过ODE理解/分析优化算法是近些年兴起的思路。同样的给出一些例子。
Gradient descent是gradient flow 的forward Euler离散。
Proximal method是 f 的gradient flow的backward Euler离散，同时也是 的gradient flow 的 forward Euler离散，这里
表示inf-convolution。因此，不同的ODE在不同的离散格式下可以导出同一种算法。
相应的，Mirror descent和Bregman proximal 分别是 的forward Euler和backward Euler离散。【todo】
Natural gradient descent对应的ODE是 ，和上一句里Mirror descent对应的ODE是一样的，只不过换了一个考虑的变量，这里是直接考虑
的，上面是考虑
（相当于做了个换元）。因此，同一个ODE对不同变量的离散可以导出不同的优化算法。
ADMM的ODE形式见此文章 初级优化师：机器学习与控制：ADMM的ODE模型与基于Lyapunov的收敛分析。
Nesterov加速算法有几篇很火的文章也是用ODE去理解，但我认为依然没有理解透彻，因为没有解释“为什么是这种ODE/ Bregman Lagrangian”。
抽象空间中也有这种思路，比如JKO（KL div在Wasserstein-2空间的梯度下降是gradient flow的离散，它的gradient flow是Fokker Planck equation），类似的还有其他PDE在W-2空间中的gradient flow理解，这就是相反的思路：用energy函数帮助理解PDE。
如同第一种理解方法，这种ODE和优化算法的联系可以帮助设计和分析优化算法。设计方面暂时比较少见，比如Nesterov加速虽然对应一些ODE，但对这些ODE的直接离散是无法反过来得到Nesterov算法的，必须引入另一个变量，这种奇怪变量的引入令我对于Nesterov是否能从这些ODE出发来设计存疑。
但ODE的思路对分析收敛性和速度很有用。具体方式是Lyapunov分析法。Lyapunov分析直观理解是构造一个非负函数V使得在需要的那条轨迹上递减，如此可证那条轨迹会被控制在V的level set里。优化上用它证明收敛速度的方法是，构造函数 （
是minimizer），函数 g 是我们希望估计的量的函数，比如可以取
，Breg div等，这里的norm也不一定是Euclidean norm，所以构造g是个很“艺术”的事。证明V是Lyapunov函数后，得到V的有界性，因此得到我们需要的量（
）的误差估计：
。Lyapunov在我看来和前一节的每一步的优化问题有一定的相似性，这种相似性的原因还未知。它一般是按照导数里希望有的量凑出来的，如果希望有
就加入
项，希望有
就加入
项，希望有
就加入
项。对于我这种对误差分析手生的人来说，构造Lyapunov函数完全是magic。。。
对偶空间是用 做change of variable之后的空间，这里
的选择给了一定的自由度，需要是凸函数加一些性质，选择一个合适的
可以令到算法在新的空间里变得容易理解。从information geometry的角度看，原空间和新空间都是更根本的manifold的两个坐标系。这也给出了设计新算法的一个思路：在某个空间上设计算法，然后再做坐标变换（但是注意这样得出的算法需要容易计算才有实用性）。下面给出几个例子。
Newton method，用 作变量代换（
），对应的ODE
变成
，即在对偶空间里直线朝着0点运动（在原空间做优化相当于在
给出的对偶空间到达0点）。
Interior point method求解 ，转换成一个关于以 t 为参数的系列问题
，这里
是barrier function。对每个 t 求 minimizer
，然后让t 趋向于正无穷，得到原问题的解。这里用
做change of variable，得到
满足的ODE是
，是一条直线，是
的gradient descent。
更复杂的结构 ，写成鞍点问题
，对偶问题
。满足一定条件时这三个问题等价。这是优化里面常用的对偶思想，设计算法时在这三个问题里面找一个最简单的问题解。有时对偶问题的性质比原问题好（强凸之类的），或者对偶问题有explicit formula，那么应当求解对偶问题。有些算法是在鞍点问题上设计的，比如primal-dual，ADMM等。
到目前为止，算法的提出靠的是对之前已有算法的理解，而不是在某个大的框架下的构造。每提出一个算法，依然要重新证明收敛性、不同条件下的收敛速度，而不是由一个大的框架直接导出收敛速度（即使是Lyapunov分析也要构造Lyapunov函数，而且离散的情况要做误差估计，这些分析需要对于不等式的“熟悉”）。比如Nesterov加速之所以加速是因为某些代数计算的结果，因此为什么想出这种算法、如何迁移到其他的优化setup（如非凸、随机）依然是具体问题具体分析的。不同的算法虽然有最低要求、不同假设下的收敛速度分析，但任给一个函数，如何选择“最好的”算法、当这个函数不满足假设时如何调整或“粘合”算法设计出适合此函数的算法，依然是让人费解的问题。因此，我认为优化算法需要一个大框架，我也很好奇这个大框架是什么，可惜没有思路，感觉自己手头上的是trick而不是framework / theory。
=================================================
除了以上的三种理解思路，优化里面还有一些tricks。
一些n维最小值问题可以变成更高维的min-min问题。比如 可以变成
用ADMM求解。【todo】
【todo】
有一些tricks可以加速算法，或者提升实际应用中的效果，比如用over-relaxation steps和restarting。Restarting顾名思义，进行到某一步之后重启算法。Over-relaxation是指每一步算法之后，顺着它的方向再走一点，有点加个momentum的感觉，只不过要小心设计往前走多少（步长）。proximal step可以用这种方法，因为proximal相当于对 走了
步长的gradient descent，理论上gd可以走
步长，因此proximal step可以再顺着相同的方向往前走一段。著名的FISTA就是在forward-backward后加了这一步。另外，Nesterov算法也有这一步。只是这些算法的步长都是从误差分析里计算得出，像Nesterov的神秘步长
完全无法理解。。
有时候也怀疑优化这个领域到底需不需要 / 存不存在一个大的框架。不同的函数不同的性质需要不同的算法是很自然的事情。以上各个角度也是well-known的事情，“每一步解一个优化问题”算是加了一个penalty项，常常被用来构造不等式分析每一步的下降，从而从离散的角度证明收敛及速度；ODE角度用来从连续的角度证明收敛及速度；对偶关系用来选择一个简单的等价问题。很多优化方法是“粘合”这些角度做成的，比如primal-dual是用对偶思路转换到鞍点问题，然后加penalty term设计出来的；ADMM也是差不多的思路（对偶+penalty+splitting）。根据不同的函数性质，人们构造出不同的“距离函数”以简化计算、提高速度。因此构造这些函数 / metric是problem-dependent的，也许试图构造框架才是走偏了。谁知道呢。
本文只总结了连续优化问题比较出名的简单算法，这些算法在上波图像处理的热潮当中逐渐发展起来，每个算法都有很多变种，literature实在太多，难以总结。其他领域也有很多著名的优化算法，比如linear programming的simplex method、图问题里的max-flow和min-cut、近期神经网络热潮火起来的带随机的各种算法、处理约束条件的barrier method和interior point method等等，这些特定的算法是为了特定的问题设计的优秀算法，很难放在一个大框架下整理，因此本文没有涉及，之后有机会再开新文吧。给出一些参考资料[2][3]。最近优化有点看腻了，被细节缠住，可能要抽离一段时间再随缘更新。
在线客服
客服咨询
官方微信
返回顶部
