An adaptive proximal point algorithm framework and application to large-scale optimization

Abstract

We investigate the proximal point algorithm (PPA) and its inexact extensions under an error bound condition, which guarantees a global linear convergence if the proximal regularization parameter is larger than the error bound condition parameter. We propose an adaptive generalized proximal point algorithm (AGPPA), which adaptively updates the proximal regularization parameters based on some implementable criteria. We show that AGPPA achieves linear convergence without any knowledge of the error bound condition parameter, and the rate only differs from the optimal one by a logarithm term. We apply AGPPA on convex minimization problem and analyze the iteration complexity bound of the resulting algorithm. Our framework and the complexity results apply to arbitrary linearly convergent inner solver and allows a hybrid with any locally fast convergent method. We illustrate the performance of AGPPA by applying it to solve large-scale linear programming (LP) problem. The resulting complexity bound has a weaker dependence on the Hoffman constant and scales with the dimension better than linearized ADMM. In numerical experiments, our algorithm demonstrates improved performance in obtaining solution of medium accuracy on large-scale LP problem.

References in corpus (5)

• Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
• Complexity and performance of an Augmented Lagrangian algorithm
• Optimal Black-Box Reductions Between Optimization Objectives
• Adaptive restart of accelerated gradient methods under local quadratic growth condition
• An asymptotically superlinearly convergent semismooth Newton augmented Lagrangian method for Linear Programming