美文网首页
Proximal Algorithms 5 Parallel a

Proximal Algorithms 5 Parallel a

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

Proximal Algorithms

这一节，介绍并行算法的实现.

问题的结构

令[n] = \{1, \ldots, n\}. 给定c \subseteq [n], 让x_c \in \mathbb{R}^{|c|}表示向量x\in \mathbb{R}^n的一个子向量(以c为指标的对应部分).当\mathcal{P}=\{c_1, \ldots, c_N\}满足:
\cup \mathcal{P} = [n] \\ c_i \cap c_j = \emptyset, i \ne j
时， 称\mathcal{P}为[n]的一个分割.
函数f的\mathcal{P}-分割满足:
f(x) = \sum_{i=1}^N f_i (x_{c_i})
其中f_i : \mathbb{R}^{|c_i|} \rightarrow \mathbb{R}.
在这种情况下:
(\mathbf{prox}_f(v))_i = \mathbf{prox}_{f_i}(v_i)
所以，可以并行计算.

考虑下面的问题：
\mathrm{minimize} \quad f(x) + g(x)
如果假设f是\mathcal{P}-分割的, 而g是\mathcal{Q}-分割的，那么问题等价于:

在这里插入图片描述
于是ADMM可以并行计算:
在这里插入图片描述

consensus

考虑下列问题如何进行并行计算:
\mathrm{minimize} \quad f(x) = \sum_{i=1}^N f_i (x)

一个非常巧妙的变化:

在这里插入图片描述
可以看到，这样子，函数就是可分了, 只是多了一个附加条件.
将上面的问题转化为:

其中是consensus set:

这样，问题就变成俩个可分函数了, 不过需要注意的是，二者的分割并不相同:

而，即的分割为:

注: 文中是(我认为是作者的笔误).
这个时候的ADMM的第二步，即更新，可以直接为:

在这里插入图片描述
作者贴了一个比较形象的图来表示这种分割:
在这里插入图片描述

更为一般的情况

考虑下面的问题:
\mathrm{minimize} \quad f(x) = \sum_{i=1}^N f_i (x_{c_i})
其中c_i \subseteq [n]， 但是c_i \cap c_j, i \ne j并不一定为空集.
进行同样的转换:

在这里插入图片描述
其中

同样等价于:

相应的有一张比较形象的图：
在这里插入图片描述
前一部分的分割是类似的, 后一部分的分割，就是怎么说呢，就像图上的行一样的分.

ADMM为:

在这里插入图片描述
其中

Exchange 问题

Global exchange

交换问题具有如下形式:

在这里插入图片描述
可以用一个实际问题来考量，每个表示一个客户，表示每个客户给予或者得到的总量，而表示该客户的效益，这个条件表示，所以客户东西的总量是固定的，即收支平衡.

我们可以将此问题转化为(这个方法太好使了吧):
\mathrm{minimize} \quad \sum_{i=1}^N f_i(x_i) + I_{\mathcal{C}}(x_1, \ldots, x_N)
其中
\mathcal{C} = \{(x_1, \ldots, x_N)\in \mathbb{R}^{nN} | x_1 + x_2 + \ldots + x_N=0\}
我们知道，指示函数的proximal为投影算子, 于是:
(\Pi_{\mathcal{C}}(v_1, \ldots, v_N))_i = v_i - \bar{v}
于是ADMM算法为:

在这里插入图片描述

更为一般的情况

有些时候，并不是所有客户都面对同一个市场，所以，每个x_i的维度什么对的也有区别:
\mathcal{C} = \Big \{ (z_1, \ldots, z_N) \Big| \sum_{i : k \in c_i} (z_i)_k =0 \Big \}
有点和consenus的一般情况比较类似.

Allocation

allocation problem:

在这里插入图片描述
其中.

这个问题和交换问题也是相似的，区别在于总量b， 而且要求x_i \ge 0.
类似的，我们可以将上面的问题改写为:
\mathrm{minimize} \quad \sum_{i=1}^N f_i(x_i) + I_{\mathcal{C}} (x_1, \ldots, x_N)
其中:
\mathcal{C} = \{(x_1, \ldots, x_N)| x_i \ge 0, x_1 + \ldots + x_N = b\}
所以相应的算法是:

在这里插入图片描述
如何进行投影，会在下一节提到， 还有更加一般的情况，比如.

相关文章

网友评论

      本文标题：Proximal Algorithms 5 Parallel a

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

      延伸阅读

      深度阅读

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

      栏目导航

      热点阅读

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

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

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

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

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

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