Distributed nonconvex constrained optimization over time-varying digraphs
Distributed nonconvex constrained optimization over time-varying digraphs
复制标题
DOI：
10.1007/s10107-018-01357-w
复制
发表时间：
2018-09
影响因子：
2.7
通讯作者：
G. Scutari;Ying Sun
中科院分区：
文献类型：
--
作者：
G. Scutari;Ying Sun
本文考虑网络上的非凸分布约束优化问题，模型为有向（可能是时变）图。我们介绍了第一个算法框架的总和最小化的光滑非凸（不可分）的功能，代理的总和效用加上一个差异的凸函数（与非光滑凸部分）。这种通用公式出现在许多应用中，从统计机器学习到工程。所提出的分布式方法结合了连续凸逼近技术与明智设计的扰动推和共识机制，旨在跟踪局部的梯度（平滑部分）和效用。次线性收敛速度证明时，一个固定的步长（可能不同的代理），而渐近收敛到固定的解决方案证明使用递减的步长。数值结果表明，我们的算法与目前的计划相比，在凸和非凸问题。
This paper considers nonconvex distributed constrained optimization over networks, modeled as directed (possibly time-varying) graphs. We introduce the first algorithmic framework for the minimization of the sum of a smooth nonconvex (nonseparable) function—the agent’s sum-utility—plus a difference-of-convex function (with nonsmooth convex part). This general formulation arises in many applications, from statistical machine learning to engineering. The proposed distributed method combines successive convex approximation techniques with a judiciously designed perturbed push-sum consensus mechanism that aims to track locally the gradient of the (smooth part of the) sum-utility. Sublinear convergence rate is proved when a fixed step-size (possibly different among the agents) is employed whereas asymptotic convergence to stationary solutions is proved using a diminishing step-size. Numerical results show that our algorithms compare favorably with current schemes on both convex and nonconvex problems.