优化理论(6): Non-smooth Algorithm
Non-smooth Algorithm优化理论的最后一部分是关于非光滑优化（Non-smooth algorithm），这个问题在许多地方都会出现（频繁出现）。比如很简单的一个例子，在机器学习里考虑 l1-regularitzation的时候，优化目标就是非光滑的。
在这种情形下，可以尝试，之前所介绍的所有基于梯度或者Hessian的方法将失效（Steepest descent mehtod、Newton Method、quasi-Newton Method）。
例子：
梯度下降法失效的例子
通过一定的计算可以发现，优化问题的最优解就是-100。但是，如果采用梯度下降法，通过一些梯度的简单计算，我们可以得到如下结论：如果选取初始点为 https://www.zhihu.com/equation?tex=x%5E1%3D%289%2C-3%29，那么通过steepest descent method生成的迭代点序列为 https://www.zhihu.com/equation?tex=%5C%7Bx%5Ek%3D%283%5E%7B3-k%7D%2C%28-1%29%5Ek3%5E%7B2-k%7D%29%3Ak%3D1%2C2%2C...%5C%7D ，这个序列最终会收敛到 https://www.zhihu.com/equation?tex=%5Cbar%7Bx%7D%3D%280%2C0%29 ，这甚至都不是一个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，因此，等价地，我们实际上是在寻找某个点 https://www.zhihu.com/equation?tex=%5Chat+x ，使得 https://www.zhihu.com/equation?tex=0%5Cin+%5Cpartial+f%28%5Chat+x%29 。
这一部分的motivation主要是从算子的角度来考虑的。一些想法可以从求解非线性方程的迭代法中得到：
假设我们需要求解的非线性方程为：
https://www.zhihu.com/equation?tex=f%28x%29%3D0+%5C%5C+
假如我们能够将该方程重新写成（这点不一定能够做到）：
https://www.zhihu.com/equation?tex=x%3D+%5Chat+f%28x%29+%5C%5C+
那么我们就可以采取以下的迭代格式：
https://www.zhihu.com/equation?tex=x%5Ek%3D%5Chat+f%28x%5E%7Bk-1%7D%29+%5C%5C
回到正题，假如我们能够将 https://www.zhihu.com/equation?tex=0%5Cin+%5Cpartial+f%28%5Chat+x%29+ 转化成某个类似于以上形式的等价条件( https://www.zhihu.com/equation?tex=%5Chat+x%3DP_c%28%5Chat+x%29 )，那么我们也可以从算子迭代的角度来解决这个问题。
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）：
https://www.zhihu.com/equation?tex=%5Cpsi_f%28x%29%3A%3D%5Cpsi_%7Bf%2Ct%7D%28x%29%3Dmin_y%5C+f%28y%29%2B%5Cfrac%7B1%7D%7B2t%7D%7C%7Cy-x%7C%7C%5E2+%5C%5C
相关性质：
[*]https://www.zhihu.com/equation?tex=%5Cphi+%28y%29%3Df%28y%29%2B%5Cfrac%7B1%7D%7B2t%7D%7C%7Cy-x%7C%7C%5E2 是strongly convex；
[*]https://www.zhihu.com/equation?tex=argmin_y%5C+%5Cphi%28y%29 存在且唯一；
[*]定义Proximal mapping： https://www.zhihu.com/equation?tex=P_f%28x%29%3Dargmin_u%5C+f%28u%29%2B%5Cfrac%7B1%7D%7B2%7D%7C%7Cu-x%7C%7C%5E2 （2保证3的定义合理性）；
[*]https://www.zhihu.com/equation?tex=u%3DP_f%28x%29+%5C+%5C+%5C+%5C+i.f.f%5C+%5C+%5C+%5C+x-u%5Cin%5Cpartial+f%28u%29 ；
重要定理（列举）：
[*]
[*]当是convex，non-smooth的(proper、closed)，那么Moreau-Yosida regularization https://www.zhihu.com/equation?tex=%5Cpsi_f%28x%29 是continuously differentiable，并且 https://www.zhihu.com/equation?tex=%5Cnabla%5Cpsi_%7Bf%2Ct%7D%28x%29%3Dt%5E%7B-1%7D%28x-P_%7Btf%7D%28x%29%29%3A%3Dt%5E%7B-1%7DQ_%7Btf%7D%28x%29
[*] 对于closed、proper、convex函数，我们可以得到： https://www.zhihu.com/equation?tex=x%3DP_f%28x%29%2BP_%7Bf%5E%2A%7D%28x%29+%5C%5C
应用（PPA Framework）：（主要定理1、2）
[*]定理1保证（从某种程度上）优化函数和是等价的；
[*]定理2保证对于优化Moreau-Yosida Regularization可以采用之前的梯度下降法框架；
综合以上1、2，于是得到了Proximal Point Algorithm（算法名字得于其主要依靠Proximal mapping https://www.zhihu.com/equation?tex=P_f%28x%29 ）:
https://www.zhihu.com/equation?tex=x%5E%7Bk%2B1%7D%3Dx%5Ek-t%5Cnabla+%5Cpsi_%7Bf%2Ct%7D%28x%5Ek%29%3DP_%7Btf%7D%28x%5Ek%29%3Dargmin_u%5C+f%28u%29%2B%5Cfrac%7B1%7D%7B2t%7D%7C%7Cu-x%5Ek%7C%7C%5E2++%5C%5C+
：该方法完全等价于梯度下降法，因此一些收敛性结果和梯度下降法的收敛性结果一致（linearly-convergence\ global convergence）
难点：由于是non-smooth的，因此该问题很难有闭式解(exact minimizer)。因此，根据不同问题（ 不同的 ），我们可以设计不同的approximate algorithm，因此也就引发了PPA algorithm的很多变体。
变体(Approximate Algorithm)：
[*]Proximal Gradient Algorithm；
[*]Dual Proximal Point Algorithm
1.PGA
model: https://www.zhihu.com/equation?tex=min_x%5C+f%28x%29%3Dg%28x%29%2Bh%28x%29
其中，是可微的；是convex & non-smooth，并且proximal mapping有closed form（比如，）。
对于这种情况，我们可以采取以下的approxiamte algorithm：
https://www.zhihu.com/equation?tex=f%28x%29+%5Capprox+g%28x%5Ek%29%2B%5Cnabla+g%28x%5Ek%29%5ET%28x-x%5Ek%29%2Bh%28x%29%3A%3D%5Chat+f_%7Bx%5Ek%7D%28x%29+%5C%5C+
那么，根据PPA算法，对 函数https://www.zhihu.com/equation?tex=%5Chat+f_%7Bx%5Ek%7D%28x%29+ （ https://www.zhihu.com/equation?tex=f%28x%29 的近似）在点 https://www.zhihu.com/equation?tex=x%3Dx%5Ek 处的迭代即为：
https://www.zhihu.com/equation?tex=x%5E%7Bk%2B1%7D+%5Capprox+P_%7Bt%5Chat+f_%7Bx%5Ek%7D%7D%28x%5Ek%29%3Dargmin_x+%5C+%5Cnabla+g%28x%5Ek%29%5ET%28x-x%5Ek%29%2Bh%28x%29%2B%5Cfrac%7B1%7D%7B2t%7D%7C%7Cx-x%5Ek%7C%7C%5E2%3DP_%7Bth%7D%28x%5Ek-t%5Cnabla+g%28x%5Ek%29%29+%5C%5C
因此，对于这种特殊情况，每一步迭代更新都有closed form的结果。
并且，可以证明：此方法的虽然没有梯度下降法的线性收敛速度，但是也能够保证收敛速度是 https://www.zhihu.com/equation?tex=O%28%5Cfrac%7B1%7D%7Bk%7D%29 的。
2.Dual PPA
model: https://www.zhihu.com/equation?tex=min_x%5C+f%28x%29%3Dg%28x%29%2Bh%28Bx%29
其中，是可微的；是convex & non-smooth，并且proximal mapping有closed form（比如，）。
对于这种情况，我们将会采取完全不同的策略，这是因为尽管的proximal mapping会有闭式解，但是这不能保证 https://www.zhihu.com/equation?tex=h%28B%C2%B7%29 也有闭式解。因此，第一种PGA算法就失效了。
我们考虑把问题转换成一个等价形式：
model：
我们来考虑一个更强（广泛）的模型：
model： https://www.zhihu.com/equation?tex=min_z%5C+f%28z%29+%5C%5C+s.t.+Az%3Db (*)
其对应的Lagrangian function为： https://www.zhihu.com/equation?tex=L%28z%2Cu%29%3Df%28z%29%2Bu%5ET%28Az-b%29
其对应的Augmented Lagrangian function为： https://www.zhihu.com/equation?tex=L_A%28z%2Cu%2Cc%29%3Df%28z%29%2Bu%5ET%28Az-b%29%2B%5Cfrac%7Bc%7D%7B2%7D%7C%7CAz-b%7C%7C%5E2
由于该问题（*）是凸问题，且约束条件均为仿射约束，故满足弱Slater条件，故强对偶性满足。因此，我们可以考虑问题（*）的对偶问题（完全等价）：
https://www.zhihu.com/equation?tex=min_u+%5C+d%28u%29+%5C%5C+
其中 https://www.zhihu.com/equation?tex=d%28u%29%3D-min_x%5C+L%28z%2Cu%29；并且，在优化理论（2）: Duality中关于对偶函数性质的一些讨论结果可以迁移过来： https://www.zhihu.com/equation?tex=%5Cpartial+d%28u%29%3Dconv%5C%7Bb-A%5Cbar%7Bx%7D%3A%5Cbar+x+%5Cin+X%28u%29%5C%7D ，其中， https://www.zhihu.com/equation?tex=X%28u%29%3Dargmin_z%5C+L%28z%2Cu%29 。
因为这类函数（）特殊的subgradient形式，我们可以通过特殊的方式来考虑其Proximal mapping。（这里的逻辑是：原问题 <==> 对偶问题；对偶问题 ==>convex & non-smooth问题 ==> PPA Framework；因此，问题归结于求对偶函数的Proximal mapping；易求解性由对偶函数的次梯度的特殊形式保证！）
相关定理：
对任意 https://www.zhihu.com/equation?tex=x%5E%2B+%5Cin+argmin_z%5C+L_A%28z%2Cu%2Cc%29 ，我们有： https://www.zhihu.com/equation?tex=P_%7Bcd%7D%28u%29%3Du-c%28b-Ax%5E%2B%29 。
: 这个定理是非常美妙的！通过正常的分析，求解Proximal mapping会需要对应的Lagrangian multiplier https://www.zhihu.com/equation?tex=u%5E%2B ；但是该定理说明我们可以考虑Augmented Lagrangian function来寻求我们想要的proximal mapping（多提一句：对偶函数次梯度的特殊形式在其中起着非常重要的作用！将我们的所有条件转化成了Proximal mapping的等价形式）。
根据以上定理，我们也得到了Dual PPA的整体框架：
https://www.zhihu.com/equation?tex=u%5E%7Bk%2B1%7D%3DP_%7Bc_kd%7D%28u%5Ek%29%3Du%5Ek-c_k%28b-Az%5E%7Bk%2B1%7D%29+%5C%5C+
其中， https://www.zhihu.com/equation?tex=z%5E%7Bk%2B1%7D%3Dargmin_z%5C+L_A%28z%2Cu%5Ek%2Cc_k%29 。
： 这个算法(exact minimizer)的收敛行分析与PPA算法（梯度下降法）是一致的。
难点：实际应用中很难去找exact minimizer，因此会去根据具体问题构造一些特别的approximate algorithm（ADMM），以权衡算法收敛性与computational cost。
下针对我们一开始抛出的model，给出一个特别的算法ADMM(Dual PPA的子变体)：
3.ADMM
Recall：
model：
基于这个问题的Augmented Lagrangian function为：
https://www.zhihu.com/equation?tex=L_A%28%28x%2Cy%29%2C%5Clambda%2C%5Cmu%29%3Dg%28x%29%2Bh%28y%29%2B%5Clambda%5ET%28Bx-y%29%2B%5Cfrac%7B1%7D%7B2%5Cmu%7D%7C%7CBx-y%7C%7C%5E2+%5C%5C+
其对应的更新（迭代）过程Dual PPA框架为：
https://www.zhihu.com/equation?tex=%28x%5E%7Bk%2B1%7D%2Cy%5E%7Bk%2B1%7D%29%3Dargmin_%7B%28x%2Cy%29%7D%5C+L_A%28%28x%2Cy%29%2C%5Clambda%5Ek%2C%5Cmu_k%29+%5C%5C+%5Clambda%5E%7Bk%2B1%7D%3D%5Clambda%5Ek%2B%5Cfrac%7B1%7D%7B%5Cmu_k%7D%28Bx%5E%7Bk%2B1%7D-y%5E%7Bk%2B1%7D%29
但是正如我们所说的，寻找exact minimizer非常困难。因此，我们选择退而求其次，根据我们这个特殊形式（分离性很好）的Augmented Lagrangian function去寻找某种closed form的approximate minimizer。
因此，我们根据：
https://www.zhihu.com/equation?tex=%28x%5E%7Bk%2B1%7D%2Cy%5E%7Bk%2B1%7D%29%3Dargmin_%7B%28x%2Cy%29%7D%5C+L_A%28%28x%2Cy%29%2C%5Clambda%5Ek%2C%5Cmu_k%29%3Dargmin_%7B%28x%2Cy%29%7D%5C+g%28x%29%2Bh%28y%29%2B%5Cfrac%7B1%7D%7B2%5Cmu_k%7D%7C%7CBx-y%2B%5Cmu_k%5Clambda%5Ek%7C%7C%5E2+%5C%5C++
其中，当固定了后，整个目标是性质很好的（可微分的）；当固定了后，整个目标虽然不可微（non-smooth），但是由于有closed form的proximal mapping，整个最小化问题也会有closed form的minimizer。
基于此，我们就可以考虑轮流固定（或），然后考虑最优的（或），这种算法就是ADMM。
具体算法流程：
https://www.zhihu.com/equation?tex=x%5E%7Bk%2B1%7D%5Cin+argmin_x%5C+g%28x%29%2B%5Cfrac%7B1%7D%7B2%5Cmu_k%7D%7C%7CBx%2B%5Cmu_k%5Clambda%5Ek-y%5Ek%7C%7C%5E2+%5C%5C+y%5E%7Bk%2B1%7D%3Dargmin_y%5C+h%28y%29%2B%5Cfrac%7B1%7D%7B2%5Cmu_k%7D%7C%7CBx%5E%7Bk%2B1%7D%2B%5Cmu_k%5Clambda%5Ek-y%7C%7C%5E2%3DP_%7B%5Cmu_kh%28%C2%B7%29%7D%28Bx%5E%7Bk%2B1%7D%2B%5Cmu_k%5Clambda%5Ek%29
------------------------------------------------------------------------------------------------------------
最后：
以上是本学期Non-smooth optimization的所有内容（省略了一些收敛性证明；最后提一下PPA算法的收敛性类似于不动点法收敛性的证明，有兴趣可以去了解一下：Proximal mapping虽然是模1 Lipschitz-continuous的，但是有着一些别的好的估计性质）
这一部分内容是非常有应用意义的，主要是指导如何处理convex但是non-smooth的问题，这类问题在regularization方面会很常见；最后这一节内容阐明了一些比较简单的处理方法（对于一般的l1 regularization，考虑PGA算法；对于一些更复杂的regularization，可能需要用Dual Problem来进行转换，在考虑PPA的框架）
这也是整理优化理论的最后一部分。在之后会继续整理一些最简单的随机过程（Markov Chain）的内容。
页:
[1]