Running Primal-Dual Gradient Method for Time-Varying Nonconvex Problems
Running Primal-Dual Gradient Method for Time-Varying Nonconvex Problems
复制标题
DOI：
10.1137/20m1371063
复制
发表时间：
2018-12
期刊：
影响因子：
--
通讯作者：
Yujie Tang;E. Dall’Anese;A. Bernstein;S. Low
中科院分区：
文献类型：
--
作者：
Yujie Tang;E. Dall’Anese;A. Bernstein;S. Low
本文考虑了随时间演变的非凸优化问题，并解决了正则化原始对偶梯度方法的综合和分析，以跟踪 Karush-Kuhn-Tucker (KKT) 轨迹。所提出的正则化原始对偶梯度方法以运行方式实现，即底层优化问题在算法迭代期间发生变化。对于具有两次连续可微的成本和约束的问题，在 Mangasarian-Fromovitz 约束资格的推广下，导出了运行算法跟踪 KKT 轨迹的充分条件。此外，还获得了跟踪误差的渐近界限（作为 KKT 轨迹的时变性的函数）。还考虑了该算法的连续时间版本，该算法被构建为微分包含的系统，并得出了分析收敛结果。对于连续时间设置，提出了一组 KKT 轨迹不分叉或合并的充分条件。提供了受实际应用启发的说明性数值结果。
This paper considers a nonconvex optimization problem that evolves over time, and addresses the synthesis and analysis of regularized primal-dual gradient methods to track a Karush-Kuhn-Tucker (KKT) trajectory. The proposed regularized primal-dual gradient methods are implemented in a running fashion, in the sense that the underlying optimization problem changes during the iterations of the algorithms. For a problem with twice continuously differentiable cost and constraints, and under a generalization of the Mangasarian-Fromovitz constraint qualification, sufficient conditions are derived for the running algorithm to track a KKT trajectory. Further, asymptotic bounds for the tracking error (as a function of the time-variability of a KKT trajectory) are obtained. A continuous-time version of the algorithm, framed as a system of differential inclusions, is also considered and analytical convergence results are derived. For the continuous-time setting, a set of sufficient conditions for the KKT trajectories not to bifurcate or merge is proposed. Illustrative numerical results inspired by a real-world application are provided.