优化理论(6): Non-smooth Algorithm

Baste

Non-smooth Algorithm

优化理论的最后一部分是关于非光滑优化（Non-smooth algorithm），这个问题在许多地方都会出现（频繁出现）。比如很简单的一个例子，在机器学习里考虑 l1-regularitzation的时候，优化目标就是非光滑的。
在这种情形下，可以尝试，之前所介绍的所有基于梯度或者Hessian的方法将失效（Steepest descent mehtod、Newton Method、quasi-Newton Method）。
例子：



梯度下降法失效的例子

通过一定的计算可以发现，优化问题的最优解就是-100。但是，如果采用梯度下降法，通过一些梯度的简单计算，我们可以得到如下结论：如果选取初始点为   ，那么通过steepest descent method生成的迭代点序列为 ，这个序列最终会收敛到 ，这甚至都不是一个local minimum。（具体细节需要关于梯度的一些基本性质，故省略）
因此，我们需要新的算法设计来解决这种non-smooth的问题。在这里的讨论中，我们希望我们的问题是convex但是non-smooth的；至于那些non-convex的问题，不是我们考虑的对象。
Proximal Point Algorithm(PPA)

我们介绍的方法是Proximal Point Algorithm（似乎翻译成近端梯度下降法）。
目标：

• 这个算法对于不同类型的目标函数，可以演变出一些不同的近似算法；
  
• 对于PPA，可以有两种不同的理解方式。
  

1.理解方式

这里我们改变一下介绍顺序，首先来讲第二点，即两种不同的Motivation。
第一种Motivation：为了用之前的框架处理Non-smooth的问题，试想，我们能不能做到以下的事情：


其中，  是non-smooth的，  是smooth的。
如果我们能够找到这样一个  ，那么我们就可以用之前的那套方法(Steepest Descent Method或者quasi-Newton Method)来等价的处理我们需要研究的non-smooth的问题。
第二种Motivation：因为我们要研究的问题实际上是在找一个convex函数的global minimum，因此，等价地，我们实际上是在寻找某个点 ，使得 。
这一部分的motivation主要是从算子的角度来考虑的。一些想法可以从求解非线性方程的迭代法中得到：
假设我们需要求解的非线性方程为：


假如我们能够将该方程重新写成（这点不一定能够做到）：


那么我们就可以采取以下的迭代格式：


回到正题，假如我们能够将 转化成某个类似于以上形式的等价条件( )，那么我们也可以从算子迭代的角度来解决这个问题。
Rmk：事实上，这两个motivation最终导致的算法是相同的，只是两种不同的角度。
2.具体细节

核心：Proximal Point Algorithm；
两个变体（Approximation）：Proximal Gradient Algorithm和Dual Proximal Point Algorithm。
核心问题：如何得到PPA框架？（Answer：从第一个Motivation出发（Moreau-Yosida Regularization）；第二个Motivation可以用来得到算法的收敛估计）
Moreau-Yosida regularization of f（   is convex function）：


相关性质：

• 是strongly convex；
  
• 存在且唯一；
  
• 定义Proximal mapping： （2保证3的定义合理性）；
  
• ；
  

重要定理（列举）：

• 
  
• 当  是convex，non-smooth的(proper、closed)，那么Moreau-Yosida regularization 是continuously differentiable，并且
  
• [Moreau-Yosida Decomposition] 对于closed、proper、convex函数  ，我们可以得到：
  

应用（PPA Framework）：（主要定理1、2）

• 定理1保证（从某种程度上）优化函数  和  是等价的；
  
• 定理2保证对于优化Moreau-Yosida Regularization可以采用之前的梯度下降法框架；
  

综合以上1、2，于是得到了Proximal Point Algorithm（算法名字得于其主要依靠Proximal mapping ）:


[Rmk]：该方法完全等价于梯度下降法，因此一些收敛性结果和梯度下降法的收敛性结果一致（linearly-convergence\ global convergence）
难点：由于  是non-smooth的，因此该问题很难有闭式解(exact minimizer)。因此，根据不同问题（ 不同的 ），我们可以设计不同的approximate algorithm，因此也就引发了PPA algorithm的很多变体。
变体(Approximate Algorithm)：

• Proximal Gradient Algorithm；
  
• Dual Proximal Point Algorithm
  

1.PGA

model:
其中，  是可微的；  是convex & non-smooth，并且proximal mapping有closed form（比如，  ）。
对于这种情况，我们可以采取以下的approxiamte algorithm：


那么，根据PPA算法，对 函数 （ 的近似）在点 处的迭代即为：


因此，对于这种特殊情况，每一步迭代更新都有closed form的结果。
并且，可以证明：此方法的虽然没有梯度下降法的线性收敛速度，但是也能够保证收敛速度是 的。
2.Dual PPA

model:
其中，  是可微的；  是convex & non-smooth，并且proximal mapping有closed form（比如，  ）。
对于这种情况，我们将会采取完全不同的策略，这是因为尽管  的proximal mapping会有闭式解，但是这不能保证 也有闭式解。因此，第一种PGA算法就失效了。
我们考虑把问题转换成一个等价形式：
model：
我们来考虑一个更强（广泛）的模型：
model： (*)
其对应的Lagrangian function为：
其对应的Augmented Lagrangian function为：
由于该问题（*）是凸问题，且约束条件均为仿射约束，故满足弱Slater条件，故强对偶性满足。因此，我们可以考虑问题（*）的对偶问题（完全等价）：


其中 ；并且，在优化理论（2）: Duality中关于对偶函数  性质的一些讨论结果可以迁移过来： ，其中， 。
因为这类函数（  ）特殊的subgradient形式，我们可以通过特殊的方式来考虑其Proximal mapping。（这里的逻辑是：原问题 <==> 对偶问题；对偶问题 ==>convex & non-smooth问题 ==> PPA Framework；因此，问题归结于求对偶函数  的Proximal mapping；易求解性由对偶函数  的次梯度的特殊形式保证！）
相关定理：
对任意 ，我们有： 。
[Rmk]: 这个定理是非常美妙的！通过正常的分析，求解Proximal mapping会需要对应的Lagrangian multiplier ；但是该定理说明我们可以考虑Augmented Lagrangian function来寻求我们想要的proximal mapping（多提一句：对偶函数次梯度的特殊形式在其中起着非常重要的作用！将我们的所有条件转化成了Proximal mapping的等价形式）。
根据以上定理，我们也得到了Dual PPA的整体框架：


其中， 。
[Rmk]： 这个算法(exact minimizer)的收敛行分析与PPA算法（梯度下降法）是一致的。
难点：实际应用中很难去找exact minimizer，因此会去根据具体问题构造一些特别的approximate algorithm（ADMM），以权衡算法收敛性与computational cost。
下针对我们一开始抛出的model，给出一个特别的算法ADMM(Dual PPA的子变体)：
3.ADMM

Recall：
model：
基于这个问题的Augmented Lagrangian function为：


其对应的更新（迭代）过程Dual PPA框架为：


但是正如我们所说的，寻找exact minimizer非常困难。因此，我们选择退而求其次，根据我们这个特殊形式（分离性很好）的Augmented Lagrangian function去寻找某种closed form的approximate minimizer。
因此，我们根据：


其中，当固定了  后，整个目标是性质很好的（可微分的）；当固定了  后，整个目标虽然不可微（  non-smooth），但是由于  有closed form的proximal mapping，整个最小化问题也会有closed form的minimizer。
基于此，我们就可以考虑轮流固定  （或  ），然后考虑最优的  （或  ），这种算法就是ADMM。
具体算法流程：


------------------------------------------------------------------------------------------------------------
最后：
以上是本学期Non-smooth optimization的所有内容（省略了一些收敛性证明；最后提一下PPA算法的收敛性类似于不动点法收敛性的证明，有兴趣可以去了解一下：Proximal mapping虽然是模1 Lipschitz-continuous的，但是有着一些别的好的估计性质）
这一部分内容是非常有应用意义的，主要是指导如何处理convex但是non-smooth的问题，这类问题在regularization方面会很常见；最后这一节内容阐明了一些比较简单的处理方法（对于一般的l1 regularization，考虑PGA算法；对于一些更复杂的regularization，可能需要用Dual Problem来进行转换，在考虑PPA的框架）
这也是整理优化理论的最后一部分。在之后会继续整理一些最简单的随机过程（Markov Chain）的内容。