Primal-dual extrapolation methods for monotone inclusions under local Lipschitz continuity
This work addresses optimization and variational inequality problems for researchers in mathematical optimization, offering significant complexity improvements but is incremental in method development.
The paper tackles monotone inclusion problems with locally Lipschitz operators by proposing primal-dual extrapolation methods, achieving operation complexities of O(log ε⁻¹) for strongly monotone and O(ε⁻¹ log ε⁻¹) for non-strongly monotone cases, improving the previous best of O(ε⁻²).
In this paper we consider a class of monotone inclusion (MI) problems of finding a zero of the sum of two monotone operators, in which one operator is maximal monotone while the other is {\it locally Lipschitz} continuous. We propose primal-dual extrapolation methods to solve them using a point and operator extrapolation technique, whose parameters are chosen by a backtracking line search scheme. The proposed methods enjoy an operation complexity of ${\cal O}(\log ε^{-1})$ and ${\cal O}(ε^{-1}\log ε^{-1})$, measured by the number of fundamental operations consisting only of evaluations of one operator and resolvent of the other operator, for finding an $\varepsilon$-residual solution of strongly and non-strongly MI problems, respectively. The latter complexity significantly improves the previously best operation complexity ${\cal O}(\varepsilon^{-2})$. As a byproduct, complexity results of the primal-dual extrapolation methods are also obtained for finding an $\varepsilon$-KKT or $\varepsilon$-residual solution of convex conic optimization, conic constrained saddle point, and variational inequality problems under {\it local Lipschitz} continuity. We provide preliminary numerical results to demonstrate the performance of the proposed methods.