Asynchronous parallel algorithms for nonconvex optimization
Asynchronous parallel algorithms for nonconvex optimization
复制标题
DOI：
10.1007/s10107-019-01408-w
复制
发表时间：
2016-07
影响因子：
2.7
通讯作者：
Loris Cannelli;F. Facchinei;V. Kungurtsev;G. Scutari
中科院分区：
文献类型：
--
作者：
Loris Cannelli;F. Facchinei;V. Kungurtsev;G. Scutari
针对光滑非凸函数和非光滑凸函数之和的最小化问题，提出了一种新的非光滑和非光滑约束下的异步并行块下降算法框架。提出的框架依赖于逐次凸近似技术和一种新的概率模型，该模型以比当前最先进的模型更忠实的方式捕捉现代计算体系结构和异步实现的关键元素。该框架的其他关键特征是：(1)它以统一的方式涵盖了几种具体的求解方法；(2)它容纳了各种可能的并行计算体系结构；(3)它可以处理非凸约束。证明了几乎必然收敛于平稳解，并给出了理论上的复杂性结果，当工人人数不太多时，表现出接近理想的线性加速比。
We propose a new asynchronous parallel block-descent algorithmic framework for the minimization of the sum of a smooth nonconvex function and a nonsmooth convex one, subject to both convex and nonconvex constraints. The proposed framework hinges on successive convex approximation techniques and a novel probabilistic model that captures key elements of modern computational architectures and asynchronous implementations in a more faithful way than current state-of-the-art models. Other key features of the framework are: (1) it covers in a unified way several specific solution methods; (2) it accommodates a variety of possible parallel computing architectures; and (3) it can deal with nonconvex constraints. Almost sure convergence to stationary solutions is proved, and theoretical complexity results are provided, showing nearly ideal linear speedup when the number of workers is not too large.