A relaxed primal–dual hybrid gradient method with line search

Abstract The primal–dual hybrid gradient method (PDHG) is a versatile optimization method commonly used for large optimization problems, including image reconstruction. With standard PDHG, there are three user-set parameters and performance of the algorithm is highly sensitive to their values. Toward a parameter-free algorithm, we combine two existing line search methods. The first, by Malitsky et al. 1, is over two of the step sizes in the PDHG iterations. We then use the connection between PDHG and the primal–dual form of Douglas–Rachford splitting to construct a line search over PDHG’s relaxation parameter. We demonstrate the efficacy of the combined line search on multiple problems, including a novel inverse problem in magnetic resonance image reconstruction. The method presented in this manuscript is the first parameter-free variant of PDHG. Across all numerical experiments, there were no changes to line search hyperparameters.