A First-Order Primal-Dual Algorithm with Linesearch
提出一种用于原始对偶方法的线搜索技术，每次迭代只需更新对偶或原始变量，在正则化最小二乘等问题上无需额外矩阵向量乘法，证明了标准假设下的收敛性和O(1/N)遍历收敛率，并针对强凸情形和含光滑项的鞍点问题进行了改进。
The paper proposes a linesearch for a primal-dual method. Each iteration of the linesearch requires an update of 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 the case when 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.