Proximal Algorithms 5 Parallel and Distributed 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\}\)满足:
c_i \cap c_j = \emptyset, i \ne j
\]
时, 称\(\mathcal{P}\)为\([n]\)的一个分割.
函数\(f\)的\(\mathcal{P}-\)分割满足:
\]
其中\(f_i : \mathbb{R}^{|c_i|} \rightarrow \mathbb{R}\).
在这种情况下:
\]
所以,可以并行计算.
考虑下面的问题:
\]
如果假设\(f\)是\(\mathcal{P}-\)分割的, 而\(g\)是\(\mathcal{Q}-\)分割的,那么问题等价于:
于是ADMM可以并行计算:
consensus
考虑下列问题如何进行并行计算:
\]
一个非常巧妙的变化:
可以看到,这样子,函数就是可分了, 只是多了一个附加条件.
将上面的问题转化为:
\]
其中\(\mathcal{C}\)是consensus set:
\]
这样,问题就变成俩个可分函数了, 不过需要注意的是,二者的分割并不相同:
\]
而\(\mathcal{Q}\),即\(I_{\mathcal{C}}\)的分割为:
\]
注: 文中是\(i=1, 2, \ldots, N\)(我认为是作者的笔误).
这个时候的ADMM的第二步,即更新\(z\),可以直接为:
\]
作者贴了一个比较形象的图来表示这种分割:
更为一般的情况
考虑下面的问题:
\]
其中\(c_i \subseteq [n]\), 但是\(c_i \cap c_j, i \ne j\)并不一定为空集.
进行同样的转换:
其中
\]
同样等价于:
\]
相应的有一张比较形象的图:
前一部分的分割是类似的, 后一部分的分割,就是怎么说呢,就像图上的行一样的分.
ADMM为:
其中\(F_i = \{j \in [N] | i \in c_j\}\)
Exchange 问题
Global exchange
交换问题具有如下形式:
可以用一个实际问题来考量,每个\(i\)表示一个客户,\(x_i\)表示每个客户给予或者得到的总量,而\(f_i(x_i)\)表示该客户的效益,\(\sum_{i=1}^Nx_i=0\)这个条件表示,所以客户东西的总量是固定的,即收支平衡.
我们可以将此问题转化为(这个方法太好使了吧):
\]
其中
\]
我们知道,指示函数的proximal为投影算子, 于是:
\]
于是ADMM算法为:
更为一般的情况
有些时候,并不是所有客户都面对同一个市场,所以,每个\(x_i\)的维度什么对的也有区别:
\]
有点和consenus的一般情况比较类似.
Allocation
allocation problem:
其中\(x_i \in \mathbb{R}^n\).
这个问题和交换问题也是相似的,区别在于总量\(b\), 而且要求\(x_i \ge 0\).
类似的,我们可以将上面的问题改写为:
\]
其中:
\]
所以相应的算法是:
如何进行投影,会在下一节提到, 还有更加一般的情况,比如\(\sum_{i=1}^N x_i \le b\).
最新文章
- Spark——共享变量
- Javascript对象的方法赋值
- SPSS数据分析—多维偏好分析(MPA)
- 部署war包后,新增tomcat服务器,启动tomcat服务器报错解决方法
- getaddrinfo function
- 用AXIS2发布WebService的方法
- solr学习之添加文档
- lightoj 1022
- SQL SERVER 高级编程 - 自定义函数 拾忆
- Windows 系统版本判断
- 【项目】git的部署使用
- Beta阶段事后诸葛亮分析
- 《java.util.concurrent 包源码阅读》15 线程池系列之ScheduledThreadPoolExecutor 第二部分
- Project file is incomplete. Expected imports are missing 错误解决方案
- C#断点调试时属性get块逻辑执行多次
- Hexo博客部署-使用github作为保存中转仓库
- Java基础18:Java序列化与反序列化
- Opencv-Python No module named 'cv2.cv2'
- JS 事件循环机制 - 任务队列、web API、JS主线程的相互协同
- [bug] 验证selenium的显式和隐式等待而发现的一个低级错误