The paper proposes a linesearch for the primal-dual method. Each iteration of the linesearch requires to update only the dual (or primal) variable. For many problems, in particular for regularized least squares, the linesearch does not require any additional matrix-vector multiplications. We prove convergence of the proposed method under the standard assumptions. We also show an ergodic $O(1/N)$ rate of convergence for our method. In case when one of the prox-functions is strongly convex, we modify our basic method to get a better convergence rate. Finally, we propose the linesearch for a saddle point problem with an additional smooth term. Numerical experiments approve the efficiency of proposed methods.
Citation
Institute for Computer Graphics and Vision, Graz University of Technology, 2016