Parallel and Distributed Methods for Constrained Nonconvex Optimization—Part I: Theory
Parallel and Distributed Methods for Constrained Nonconvex Optimization—Part I: Theory
复制标题
DOI：
10.1109/tsp.2016.2637317
复制
发表时间：
2016-01
影响因子：
5.4
通讯作者：
G. Scutari;F. Facchinei;Lorenzo Lampariello
中科院分区：
文献类型：
--
作者：
G. Scutari;F. Facchinei;Lorenzo Lampariello
在这篇由两部分组成的文章中，我们提出了一个非凸光滑约束下非凸光滑函数极小化的通用算法框架，并考虑了一些结构化、非光滑问题的推广。该算法求解一系列(可分的)强凸问题，并在每次迭代中保持可行性。建立了原非凸优化问题的定常解的收敛性。我们的框架是非常通用和灵活的，并统一了现有的几种基于逐次凸逼近(SCA)的算法。更重要的是，与当前的SCA方法不同，它自然会为一大类非凸问题带来分布式和可并行的实现。第一部分是对该框架的概括性描述。在第二部分，我们定制了我们的通用方法来解决通信、网络和机器学习中的几个(多代理)优化问题；结果是一类新的集中式和分布式算法，与现有的ad-hoc(集中式)方案相比具有更好的优势。
In this two-part paper, we propose a general algorithmic framework for the minimization of a nonconvex smooth function subject to nonconvex smooth constraints, and also consider extensions to some structured, nonsmooth problems. The algorithm solves a sequence of (separable) strongly convex problems and maintains feasibility at each iteration. Convergence to a stationary solution of the original nonconvex optimization is established. Our framework is very general and flexible and unifies several existing successive convex approximation (SCA)-based algorithms. More importantly, and differently from current SCA approaches, it naturally leads to distributed and parallelizable implementations for a large class of nonconvex problems. This Part I is devoted to the description of the framework in its generality. In Part II, we customize our general methods to several (multiagent) optimization problems in communications, networking, and machine learning; the result is a new class of centralized and distributed algorithms that compare favorably to existing ad-hoc (centralized) schemes.