Abstract
In this paper we consider a class of structured monotone inclusion (MI)problems that consist of finding a zero in the sum of two monotone operators,in which one is maximal monotone while another is locally Lipschitz continuous.In particular, we first propose a primal-dual extrapolation (PDE) method forsolving a structured strongly MI problem by modifying the classicalforward-backward splitting method by using a point and operator extrapolationtechnique, in which the parameters are adaptively updated by a backtrackingline search scheme. The proposed PDE method is almost parameter-free, equippedwith a verifiable termination criterion, and enjoys an operation complexity of${\cal O}(\log \epsilon^{-1})$, measured by the amount of fundamentaloperations consisting only of evaluations of one operator and resolvent ofanother operator, for finding an $\epsilon$-residual solution of the structuredstrongly MI problem. We then propose another PDE method for solving astructured non-strongly MI problem by applying the above PDE method toapproximately solve a sequence of structured strongly MI problems. Theresulting PDE method is parameter-free, equipped with a verifiable terminationcriterion, and enjoys an operation complexity of ${\cal O}(\epsilon^{-1}\log\epsilon^{-1})$ for finding an $\epsilon$-residual solution of the structurednon-strongly MI problem. As a consequence, we apply the latter PDE method toconvex conic optimization, conic constrained saddle point, and variationalinequality problems, and obtain complexity results for finding an$\epsilon$-KKT or $\epsilon$-residual solution of them under local Lipschitzcontinuity. To the best of our knowledge, no prior studies were conducted toinvestigate methods with complexity guarantees for solving the aforementionedproblems under local Lipschitz continuity. All the complexity results obtainedin this paper are entirely new.