美文网首页
Proximal Algorithms 4 Algorithms

Proximal Algorithms 4 Algorithms

作者: 馒头and花卷 | 来源:发表于2019-06-09 21:04 被阅读0次

Proximal Algorithms

这一节介绍了一些利用proximal的算法.

Proximal minimization

这个相当的简单, 之前也提过，就是一个依赖不动点的迭代方法:

在这里插入图片描述
有些时候不是固定的:
import numpy as np
import matplotlib.pyplot as plt

以f(x,y) = x^2 + 50y为例

f = lambda x: x[0] ** 2 + 50 * x[1] ** 2
x = np.linspace(-40, 40, 1000)
y = np.linspace(-20, 20, 500)
X, Y = np.meshgrid(x, y) #获取坐标
fig, ax = plt.subplots()
ax.contour(X, Y, f([X, Y]), colors="black")
plt.show()
在这里插入图片描述

求解proximal可得:
x = \frac{v_1}{2\lambda + 1} \\ y = \frac{v_2}{100\lambda + 1}

def prox(v1, v2, lam):
    x = v1 / (2 * lam + 1)
    y = v2 / (100 * lam + 1)
    return x, y

times = 50
x = 30
y = 15
lam = 0.1
process = [(x, y)]
for i in range(times):
    x, y = prox(x, y, 0.1)
    process.append((x, y))

process = np.array(process)
x = np.linspace(-40, 40, 1000)
y = np.linspace(-20, 20, 500)
X, Y = np.meshgrid(x, y) #获取坐标
fig, ax = plt.subplots()
ax.contour(X, Y, f([X, Y]), colors="black")
ax.scatter(process[:, 0], process[:, 1])
ax.plot(process[:, 0], process[:, 1])
plt.show()
在这里插入图片描述

解释

除了之前已经提到过的一些解释：

Gradient flow

考虑下面的微分方程:

在这里插入图片描述
时，其中是最小值.
我们来看其离散的情形:
在这里插入图片描述

于是就有：
x^{k+1} := x^k - h \nabla f(x^k)

还有一种后退的形式:
\frac{x^{k+1}-x^k}{h}=-\nabla f(x^{k+1})
此时，为了找到x^{k+1}, 我们需要求解一个方程:
x^{k+1} + h \nabla f(x^{k+1}) = x^k \\ \Rightarrow x^{k+1} = (I+ h \nabla f)^{-1}x^k = \mathbf{prox}_{hf}(x^k)

还有一种特殊的解释，这里不提了.

f(x) + g(x)

考虑下面的问题:
\mathrm{minimize} \quad f(x) + g(x)
其中f是可微的.
我们可以通过下列proximal gradient method来求解:
x^{k+1} := \mathbf{prox}_{\lambda^k g}(x^k - \lambda^k \nabla f(x^k))
可以证明(虽然我不会)，当\nabla f Lipschitz连续，常数为L，那么，如果\lambda^k = \lambda \in (0, 1/L]，这个方法会以O(1/k)的速度收敛.

还有一些直线搜素算法:

在这里插入图片描述
一般取，是的一个上界，在后面的解释中在具体探讨.

解释1 最大最小算法

最大最小算法， 最小化函数\varphi: \mathbb{R}^n \rightarrow \mathbb{R}:
x^{k+1} := \mathrm{argmin}_x \widehat{\varphi}(x, x^k)
其中\widehat{\varphi}(\cdot, x^k)是\varphi的凸上界:\widehat{\varphi}(x, x^k) \ge \varphi(x), \widehat{\varphi}(x, x)=\varphi(x).
我们可以这么构造一个上界:

在这里插入图片描述
上面的式子很像泰勒二阶展开，首先这个函数符合第二个条件，下面我们证明，当，那么它也符合第一个条件.

其中, 又Lipschitz连续，所以:

考虑关于的二阶泰勒展式:

令:


由当时，左边为, 所以的最大特征值必小于, 所以:

完蛋，好像只能证明在局部成立，能证明在全局成立吗？

x^{k+1} := \mathrm{argmin}_x \widehat{f}_{\lambda}(x, x^k)
再令：
q_{\lambda}(x, y)=\widehat{f}_{\lambda}(x,y) + g(x)
那么:
x^{k+1} := \mathrm{argmin}_x q_{\lambda}(x, x^k)=\mathbf{prox}_{\lambda g}(x^k-\lambda \nabla f(x^k))
上面的等式，可以利用第二节中的性质推出.

不动点解释

最小化f(x)+g(x)的点x^*应当满足:
0 \in \nabla f(x^*)+\partial g(x^*)
更一般地:

在这里插入图片描述
这便说明了一种迭代方式.

Forward-backward 迭代解释

考虑下列微分方程系统:

在这里插入图片描述
离散化后得:
在这里插入图片描述
注意，等式右边和，这正是巧妙之处.
解此方程可得:
在这里插入图片描述
这就是之前的那个迭代方法.

加速 proximal gradient method

其迭代方式为:
y^{k+1} := x^k + w^k(x^k-x^{k-1}) \\ x^{k+1} := \mathbf{prox}_{\lambda^k g}(y^{k+1}-\lambda^k \nabla f(y^{k+1}))
w^k \in [0,1)
这个方法有点类似Momentum的感觉.
一个选择是:
w^k = \frac{k}{k+3}
也有类似的直线搜索算法:

在这里插入图片描述

交替方向方法 ADMM

alternating direction method of multipliers (ADMM), 怎么说呢，久闻大名，不过还没看过类似的文章.
同样是考虑这个问题:
\mathrm{minimize} \quad f(x) + g(x)
但是呢，这时f,g都不一定是可微的, ADMM采取的策略是:
x^{k+1} := \mathbf{prox}_{\lambda f} (z^k - u^k) \\ z^{k+1} := \mathbf{prox}_{\lambda g} (x^{k+1} + u^k)\\ u^{k+1} := u^k + x^{k+1} -z^{k+1}

特殊的情况是, f或g是指示函数，不妨设f是闭凸集\mathcal{C}的指示函数，而g是闭凸集\mathcal{D}的指示函数, 即:
I_{\mathcal{C}}(x)=0, if \: x\in \mathcal{C}, else \: + \infty
这个时候，更新公式变为:
x^{k+1} := \Pi_{\mathcal{C}} (z^k - u^k)\\ z^{k+1} := \Pi_{\mathcal{C}} (x^{k+1} + u^k) \\ u^{k+1} := u^k + x^{k+1} -z^{k+1}

解释1 自动控制

可以这么理解，z为状态，而u为控制，前俩步时离散时间动态系统(不懂啊...)， 第三步的目标是选择u使得x=z，所以x^{k+1}-z^{k+1}可以认为是一个信号误差，所以第三步就会把这些误差累计起来.

解释2 Augmented Largranians

我们可以将问题转化为:

在这里插入图片描述
augmented Largranian:
在这里插入图片描述
其中为对偶变量.
在已知的条件下，最小化, 即:

在已知的条件下，最小化, 即:

最后一步:

如果依照对偶问题的知识，关于应该是取最大，但是呢，关于是一个仿射函数，所以没有最值，所以就简单地取那个？
注意到：
在这里插入图片描述
在这里插入图片描述
让, 就是最开始的结果.

解释3 Flow interpretation

问题(4.9)的最优条件(KKT条件):

在这里插入图片描述
其中是对偶变量.考虑微分方程：
在这里插入图片描述
(4.11)取得稳定点的条件即为(4.10)((这部分没怎么弄明白).
离散化情形为:
在这里插入图片描述
取即可得ADMM.

解释4 不动点

原问题的最优条件为:
0 \in \partial f(x^*) + \partial g(x^*)

ADMM的不动点满足：
x = \mathbf{prox}_{\lambda f} (x-u), \quad z = \mathbf{prox}_{\lambda g}(x+u), \quad u = u + x - z
从最后一个等式，我们可以知道:
x = z, 于是
x = \mathbf{prox}_{\lambda f}(x - u), \quad x = \mathbf{prox}_{\lambda g}(x + u)
等价于:
x = (I + \partial f)^{-1}(x - u), x = (I + \lambda \partial g)^{-1}(x + u)
等价于:
x - u \in x + \lambda \partial f(x), \quad x + u \in x + \lambda \partial g(x)
俩个式子相加，说明x即为最优解.
再来说明一下，为什么可以相加，根据次梯度的定义:
\lambda f(z) \ge \lambda f(x) + (-u)^T(z-x), \quad \forall z\in \mathbf{dom}f \\ \lambda g(z) \ge \lambda g(x) + (+u)^T(z-x), \quad \forall z\in \mathbf{dom}g \\
相加可得:
\lambda f(z) + \lambda g(z) \ge 2x + \lambda f(x) +\lambda g(x) + 0
需要注意的是，我证明的时候也困扰了，
x - u \in x + \lambda \partial f(x)
并不是指(x-u)是函数x^2/2 + \lambda f(x)的次梯度, 而是x-u在\lambda f(x)的次梯度集合加上x的集合内，也就是-u是其次梯度.

对不起！又想当然了，其实没问题, 如果
g \in \partial f_1(x) + h(x)
而\partial f_2(x)=h(x)则:
g \in \partial (f_1+f_2)(x)
证:
已知:
f_1(z) \ge f_1(x)+\partial f_1(x)^T(z-x) \\ f_2(z) \ge f_2(x)+h(x)^T(z-x) \\
俩式相加可得:
(f_1+f_2)(z)\ge (f_1+f_2)(x) +(\partial f_1(x) + h(x))^T(z-x)=(f_1+f_2)(x) +g^T(z-x)
所以g \in \partial (f_1+f_2)(x), 注意g=g(x)也是无妨的.

特别的情况 f(x) + g(Ax)

考虑下面的问题：
\mathrm{minimize} \quad f(x) + g(Ax)
上面的求解，也可以让\widetilde{g}(x) = g(Ax)，这样子就可以用普通的ADMM来求解了, 但是有更加简便的方法.

在这里插入图片描述

这个的来源为：

在这里插入图片描述
再利用和之前一样的推导，不过，我要存疑的一点是最后的替代，我觉得应该是:

否则推不出来啊.

相关文章

网友评论

      本文标题：Proximal Algorithms 4 Algorithms

      本文链接：https://www.haomeiwen.com/subject/qsqoxctx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|Proximal Algorithms 4 Algorithms|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！