Golden Ratio Primal-Dual Algorithm with Linesearch
Golden Ratio Primal-Dual Algorithm with Linesearch
复制标题
DOI：
10.1137/21m1420319
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
Xiaokai Chang;Junfeng Yang;Hongchao Zhang
中科院分区：
文献类型：
--
作者：
Xiaokai Chang;Junfeng Yang;Hongchao Zhang
黄金比例原对偶算法（GRPDA）是求解结构化凸优化问题的经典Arrow-Hurwicz方法的一个新版本，该算法的目标函数由两个封闭固有凸函数和组成，其中一个包含线性变换的复合。在本文中，我们提出了一种GRPDA的线性研究策略，该策略不仅不需要线性变换的谱范数，而且允许自适应和可能更大的步长。在每个线研究步骤中，只需要更新对偶变量，因此它非常便宜，并且对于许多特殊但重要的应用（例如正则化最小二乘问题）不需要任何额外的矩阵向量乘法。建立了用原对偶间隙函数测量的全局收敛性和${\cal O}(1/N)$遍历收敛率结果，其中$N$为迭代计数器。当其中一个分量函数是强凸时，通过自适应选择算法参数，建立了更快的${\cal O}(1/N^2)$遍历收敛速率结果。此外，当两个分量函数都是强凸时，建立了非遍历的线性收敛结果。对矩阵博弈和LASSO问题的数值实验表明了所提出的路线研究策略的有效性。
Golden ratio primal-dual algorithm (GRPDA) is a new variant of the classical Arrow-Hurwicz method for solving structured convex optimization problem, in which the objective function consists of the sum of two closed proper convex functions, one of which involves a composition with a linear transform. In this paper, we propose a linesearch strategy for GRPDA, which not only does not require the spectral norm of the linear transform but also allows adaptive and potentially much larger stepsizes. Within each linesearch step, only the dual variable needs to be updated, and it is thus quite cheap and does not require any extra matrix-vector multiplications for many special yet important applications, e.g., regularized least squares problem. Global convergence and ${\cal O}(1/N)$ ergodic convergence rate results measured by the primal-dual gap function are established, where $N$ denotes the iteration counter. When one of the component functions is strongly convex, faster ${\cal O}(1/N^2)$ ergodic convergence rate results are established by adaptively choosing some algorithmic parameters. Moreover, when both component functions are strongly convex, nonergodic linear converge results are established. Numerical experiments on matrix game and LASSO problems illustrate the effectiveness of the proposed linesearch strategy.