Self-adaptive proximal point methods and applications to large-scale optimization : algorithm design and complexity analysis

Abstract

In this thesis, efforts are devoted to design efficient algorithms for large-scale optimization.

The proximal point algorithm (PPA) and its inexact extensions are known to converge linearly in an asymptotic way if the metric subregularity condition holds for the maximal monotone operator $T$. Under a slightly stronger condition, named bounded metric subregularity, the global linear convergence holds while addressing many relevant problems in application. However, such global linear convergence requires the knowledge of the bounded metric subregularity parameter, which is an unrealistic assumption. We propose an adaptive generalized proximal point algorithm (AGPPA), which adaptively updates the proximal regularization parameters based on a sequence of implementable checking criteria. We show that AGPPA achieves a linear convergence without any knowledge of the bounded metric subregularity parameter, and that the rate only differs from the optimal one by a logarithmic term.

We apply AGPPA to convex programming. The applications of AGPPA with different termination rules for the inner problems lead to different adaptive proximal augmented Lagrangian methods (APALM). We apply two frequently used termination rules, one of which controls the inexactness of the subgradient value while the other controls the inexactness of the function value. We analyze the iteration complexity bounds of the corresponding APALMs under the bounded metric subregularity condition. Our framework and the complexity results apply to linearly convergent inner solvers, and allows for a hybrid with any locally fast convergent method.

We illustrate the performance of AGPPA by applying it to solve large-scale linear programming (LP) problems. The resulting complexity bound has weaker dependence on the Hoffman constant and scales with the dimension better than linearized ADMM. For numerical acceleration, we design a globally convergent inexact projected semismooth Newton method for the inner problems, and the method has a local super linear convergence under the strict complementarity assumption. Using a hybrid inner solver, our algorithm demonstrates improved performance in obtaining solutions of medium accuracy on large-scale LP data sets. Furthermore, we numerically study the error parameters in AGPPA for the LP problem, which inspires us to relax the inexactness criteria in AGPPA and leads to a more implementable framework, namely relaxed AGPPA (RAGPPA). We also apply AGPPA to solve the large-scale least absolute shrinkage and selection operator (LASSO) problem and, as with the LP problem, we show the advantages of AGPPA from both a theoretical and a numerical perspective.