Proximal alternating penalty algorithms for nonsmooth constrained convex optimization
Proximal alternating penalty algorithms for nonsmooth constrained convex optimization
复制标题
DOI：
10.1007/s10589-018-0033-z
复制
发表时间：
2017-11
影响因子：
2.2
通讯作者：
Quoc Tran-Dinh
中科院分区：
文献类型：
--
作者：
Quoc Tran-Dinh
我们开发了两种新的近端交替惩罚算法来解决各种类型的约束凸优化问题。我们的方法主要依赖于经典二次罚分、交替最小化、Nesterov 加速、参数自适应策略的新颖组合。第一个算法旨在解决通用且可能非光滑的约束凸问题，而不需要任何 Lipschitz 梯度连续性或强凸性，同时在非遍历意义上实现最著名的收敛率，其中是迭代计数器。第二种算法也旨在解决非强凸但半强凸的问题。该算法可以在原始约束问题上实现已知的最佳收敛率。在两种情况下获得这样的速率：（1）仅对强凸项的迭代序列进行平均，或者（2）使用该项的两个邻近算子而不进行平均。在这两种算法中，我们允许将第二个子问题线性化以使用相应目标项的近端算子。然后，我们定制我们的方法来解决不同的凸问题，并产生新的变体。作为副产品，这些算法保留了与我们的主要算法相同的收敛保证。我们通过不同的数值例子验证了我们的理论发展，并将我们的方法与一些现有的最先进的算法进行了比较。
We develop two new proximal alternating penalty algorithms to solve a wide range class of constrained convex optimization problems. Our approach mainly relies on a novel combination of the classical quadratic penalty, alternating minimization, Nesterov’s acceleration, adaptive strategy for parameters. The first algorithm is designed to solve generic and possibly nonsmooth constrained convex problems without requiring any Lipschitz gradient continuity or strong convexity, while achieving the best-known-convergence rate in a non-ergodic sense, wherekis the iteration counter. The second algorithm is also designed to solve non-strongly convex, but semi-strongly convex problems. This algorithm can achieve the best-known-convergence rate on the primal constrained problem. Such a rate is obtained in two cases: (1) averaging only on the iterate sequence of the strongly convex term, or (2) using two proximal operators of this term without averaging. In both algorithms, we allow one to linearize the second subproblem to use the proximal operator of the corresponding objective term. Then, we customize our methods to solve different convex problems, and lead to new variants. As a byproduct, these algorithms preserve the same convergence guarantees as in our main algorithms. We verify our theoretical development via different numerical examples and compare our methods with some existing state-of-the-art algorithms.