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

Baste · 发表于 2021-12-30 07:15

Non-smooth Algorithm

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

梯度下降法失效的例子

通过一定的计算可以发现，优化问题的最优解就是-100。但是，如果采用梯度下降法，通过一些梯度的简单计算，我们可以得到如下结论：如果选取初始点为 $x^1=(9,-3)$ ，那么通过steepest descent method生成的迭代点序列为 $\{x^k=(3^{3-k},(-1)^k3^{2-k}):k=1,2,...\}$ ，这个序列最终会收敛到 $\bar{x}=(0,0)$ ，这甚至都不是一个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，因此，等价地，我们实际上是在寻找某个点 $\hat x$ ，使得 $0\in \partial f(\hat x)$ 。
这一部分的motivation主要是从算子的角度来考虑的。一些想法可以从求解非线性方程的迭代法中得到：
假设我们需要求解的非线性方程为：

$f(x)=0 \\$
假如我们能够将该方程重新写成（这点不一定能够做到）：

$x= \hat f(x) \\$
那么我们就可以采取以下的迭代格式：

$x^k=\hat f(x^{k-1}) \\$
回到正题，假如我们能够将 $0\in \partial f(\hat x)$ 转化成某个类似于以上形式的等价条件( $\hat x=P_c(\hat x)$ )，那么我们也可以从算子迭代的角度来解决这个问题。
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）：

$\psi_f(x):=\psi_{f,t}(x)=min_y\ f(y)+\frac{1}{2t}||y-x||^2 \\$
相关性质：

$\phi (y)=f(y)+\frac{1}{2t}||y-x||^2$ 是strongly convex；
$argmin_y\ \phi(y)$ 存在且唯一；
定义Proximal mapping： $P_f(x)=argmin_u\ f(u)+\frac{1}{2}||u-x||^2$ （2保证3的定义合理性）；
$u=P_f(x) \ \ \ \ i.f.f\ \ \ \ x-u\in\partial f(u)$ ；

重要定理（列举）：

当是convex，non-smooth的(proper、closed)，那么Moreau-Yosida regularization $\psi_f(x)$ 是continuously differentiable，并且 $\nabla\psi_{f,t}(x)=t^{-1}(x-P_{tf}(x)):=t^{-1}Q_{tf}(x)$
[Moreau-Yosida Decomposition] 对于closed、proper、convex函数，我们可以得到： $x=P_f(x)+P_{f^*}(x) \\$

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

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

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

$x^{k+1}=x^k-t\nabla \psi_{f,t}(x^k)=P_{tf}(x^k)=argmin_u\ f(u)+\frac{1}{2t}||u-x^k||^2 \\$
[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: $min_x\ f(x)=g(x)+h(x)$
其中，  是可微的；  是convex & non-smooth，并且proximal mapping有closed form（比如，  ）。
对于这种情况，我们可以采取以下的approxiamte algorithm：

$f(x) \approx g(x^k)+\nabla g(x^k)^T(x-x^k)+h(x):=\hat f_{x^k}(x) \\$
那么，根据PPA算法，对函数 $\hat f_{x^k}(x)$ （ $f(x)$ 的近似）在点 $x=x^k$ 处的迭代即为：

$x^{k+1} \approx P_{t\hat f_{x^k}}(x^k)=argmin_x \ \nabla g(x^k)^T(x-x^k)+h(x)+\frac{1}{2t}||x-x^k||^2=P_{th}(x^k-t\nabla g(x^k)) \\$
因此，对于这种特殊情况，每一步迭代更新都有closed form的结果。
并且，可以证明：此方法的虽然没有梯度下降法的线性收敛速度，但是也能够保证收敛速度是 $O(\frac{1}{k})$ 的。
2.Dual PPA

model: $min_x\ f(x)=g(x)+h(Bx)$
其中，  是可微的；  是convex & non-smooth，并且proximal mapping有closed form（比如，  ）。
对于这种情况，我们将会采取完全不同的策略，这是因为尽管  的proximal mapping会有闭式解，但是这不能保证 $h(B·)$ 也有闭式解。因此，第一种PGA算法就失效了。
我们考虑把问题转换成一个等价形式：
model：
我们来考虑一个更强（广泛）的模型：
model： $min_z\ f(z) \\ s.t. Az=b$ (*)
其对应的Lagrangian function为： $L(z,u)=f(z)+u^T(Az-b)$
其对应的Augmented Lagrangian function为： $L_A(z,u,c)=f(z)+u^T(Az-b)+\frac{c}{2}||Az-b||^2$
由于该问题（*）是凸问题，且约束条件均为仿射约束，故满足弱Slater条件，故强对偶性满足。因此，我们可以考虑问题（*）的对偶问题（完全等价）：

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

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

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

$L_A((x,y),\lambda,\mu)=g(x)+h(y)+\lambda^T(Bx-y)+\frac{1}{2\mu}||Bx-y||^2 \\$
其对应的更新（迭代）过程Dual PPA框架为：

$(x^{k+1},y^{k+1})=argmin_{(x,y)}\ L_A((x,y),\lambda^k,\mu_k) \\ \lambda^{k+1}=\lambda^k+\frac{1}{\mu_k}(Bx^{k+1}-y^{k+1})$
但是正如我们所说的，寻找exact minimizer非常困难。因此，我们选择退而求其次，根据我们这个特殊形式（分离性很好）的Augmented Lagrangian function去寻找某种closed form的approximate minimizer。
因此，我们根据：

$(x^{k+1},y^{k+1})=argmin_{(x,y)}\ L_A((x,y),\lambda^k,\mu_k)=argmin_{(x,y)}\ g(x)+h(y)+\frac{1}{2\mu_k}||Bx-y+\mu_k\lambda^k||^2 \\$
其中，当固定了  后，整个目标是性质很好的（可微分的）；当固定了  后，整个目标虽然不可微（  non-smooth），但是由于  有closed form的proximal mapping，整个最小化问题也会有closed form的minimizer。
基于此，我们就可以考虑轮流固定  （或  ），然后考虑最优的  （或  ），这种算法就是ADMM。
具体算法流程：

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

		自动登录	找回密码
密码			立即注册

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

本帖子中包含更多资源