A first-order primal-dual algorithm with linesearch

Abstract

The paper proposes a linesearch for a 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 standard assumptions. We also show an ergodic $O(1/N)$ rate of convergence for our method. In case one or both of the prox-functions are strongly convex, we modify our basic method to get a better convergence rate. Finally, we propose a linesearch for a saddle point problem with an additional smooth term. Several numerical experiments confirm the efficiency of our proposed methods.

25 pages, 12 figures

References in corpus (1)

• Proximal extrapolated gradient methods for variational inequalities

Cited by in corpus (22)

• Bregman three-operator splitting methods
• Projective Splitting with Forward Steps: Asynchronous and Block-Iterative Operator Splitting
• Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient
• Adaptive Similar Triangles Method: a Stable Alternative to Sinkhorn's Algorithm for Regularized Optimal Transport
• Exploiting Strong Convexity from Data with Primal-Dual First-Order Algorithms
• Block-coordinate primal-dual method for the nonsmooth minimization over linear constraints
• Non-linear fitting with joint spatial regularization in Arterial Spin Labeling
• Compressed MRI Reconstruction Exploiting a Rotation-Invariant Total Variation Discretization
• Smoothing technique for nonsmooth composite minimization with linear operator
• The primal-dual hybrid gradient method reduces to a primal method for linearly constrained optimization problems
• Non-Stationary First-Order Primal-Dual Algorithms with Faster Convergence Rates
• Three Operator Splitting with Subgradients, Stochastic Gradients, and Adaptive Learning Rates
• A golden ratio primal-dual algorithm for structured convex optimization
• A Preconditioned Version of a Nested Primal-Dual Algorithm for Image Deblurring
• Semi-Anchored Multi-Step Gradient Descent Ascent Method for Structured Nonconvex-Nonconcave Composite Minimax Problems
• Augmented Lagrangian-Based Decomposition Methods with Non-Ergodic Optimal Rates
• Motion Compensated Dynamic MRI Reconstruction with Local Affine Optical Flow Estimation
• A Relaxed Primal-Dual Hybrid Gradient Method with Line Search
• Best-first Search Algorithm for Non-convex Sparse Minimization
• A Weighted Difference of Anisotropic and Isotropic Total Variation for Relaxed Mumford-Shah Color and Multiphase Image Segmentation
• First-order primal-dual algorithm with correction
• A generalized primal-dual algorithm with improved convergence condition for saddle point problems