Primal-dual extrapolation methods for monotone inclusions under local Lipschitz continuity

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(ε-1log ε-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.