Proximal Alternating Penalty Algorithms for Constrained Convex Optimization

Abstract

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, and 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 $O(\frac{1}{k})$-convergence rate in a non-ergodic sense, where $k$ is 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 $O(\frac{1}{k^2})$-convergence rate on the primal constrained problem. Such a rate is obtained in two cases: (i)~averaging only on the iterate sequence of the strongly convex term, or (ii) 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.

35 pages, 6 figures and 1 table. The code is available at: https://github.com/quoctd/PAPA-s1.0

References in corpus (4)

• Tight Complexity Bounds for Optimizing Composite Objectives
• Smoothing technique for nonsmooth composite minimization with linear operator
• A Primal-Dual Algorithmic Framework for Constrained Convex Minimization
• Construction and Iteration-Complexity of Primal Sequences in Alternating Minimization Algorithms

Cited by in corpus (5)

• A unified differential equation solver approach for separable convex optimization: splitting, acceleration and nonergodic rate
• Stochastic Gauss-Newton Algorithms for Nonconvex Compositional Optimization
• Non-Stationary First-Order Primal-Dual Algorithms with Faster Convergence Rates
• Augmented Lagrangian-Based Decomposition Methods with Non-Ergodic Optimal Rates
• A New Randomized Primal-Dual Algorithm for Convex Optimization with Optimal Last Iterate Rates