Preconditioned golden ratio primal-dual algorithm with linesearch

The golden ratio primal-dual algorithm (GRPDA) was proposed for solving the saddle point problems which are being widely used in a variety of areas. Compared to the popular primal-dual algorithm (PDA), GRPDA allows for larger stepsizes by replacing the extrapolation step with a convex combination step for numerical acceleration. In this paper, we incorporate preconditioning techniques into GRPDA, resulting in the preconditioned GRPDA (PreGRPDA). PreGRPDA eliminates the need for calculating the operator norm of the linear operator and allows for larger stepsizes when the operator norm is large, thus accelerating convergence. We further improve the PreGRPDA by implementing a linesearch strategy, leading to the preconditioned GRPDA with linesearch (PreGRPDA-L). In many instances, the linesearch step can adjust the preconditioners in each iteration without incurring additional costly computations, thus improving algorithm performance. Moreover, PreGRPDA-L mitigates the issue of a slower convergence rate of PreGRPDA compared to GRPDA when the operator norm of the linear operator is small. Furthermore, we establish the global convergence of the proposed algorithms under general assumptions. Finally, numerical experiments on the LASSO, CT image reconstruction, and graph cuts are presented to verify the effectiveness of proposed algorithms.