Diagonal preconditioning for first order primal-dual algorithms in convex optimization

TLDR

The paper investigates diagonal preconditioners for the first‑order primal‑dual algorithm that guarantee convergence without step‑size tuning. The authors design simple diagonal preconditioners and demonstrate their effectiveness on linear programming and computer‑vision tasks, also showing equivalence to an older alternating‑step method for monotropic programming. In all tested cases, the preconditioned algorithm outperforms the original method and matches the performance of the legacy alternating‑step approach.

Abstract

In this paper we study preconditioning techniques for the first-order primal-dual algorithm proposed in [5]. In particular, we propose simple and easy to compute diagonal preconditioners for which convergence of the algorithm is guaranteed without the need to compute any step size parameters. As a by-product, we show that for a certain instance of the preconditioning, the proposed algorithm is equivalent to the old and widely unknown alternating step method for monotropic programming [7]. We show numerical results on general linear programming problems and a few standard computer vision problems. In all examples, the preconditioned algorithm significantly outperforms the algorithm of [5].