×

New convergence results of the golden ratio primal-dual algorithm. (English) Zbl 1505.65223

Summary: Recently, we proposed a golden ratio primal-dual algorithm (GRPDA) for solving bilinear saddle point problem. It is full-splitting and can be viewed as a new variant of the classical Arrow-Hurwicz method. Moreover, compared with the famous primal-dual algorithm of Chambolle and Pock, it converges under a much relaxed stepsize condition. However, ergodic convergence rate results have been established for GRPDA only in terms of the so-called “primal-dual gap function”, which could vanish at nonstationary points, making existing results less informative. In this work, based on some equivalent reformulations of the bilinear saddle point problem as constrained/unconstrained optimization problems, we establish new convergence rate results measured by the conventional measures of function value residual and constraint violation. We establish in the general convex case \(\mathcal{O}(1/N)\) ergodic sublinear convergence rate result, where \(N\) denotes the iteration counter. When either one of the component functions is strongly convex, an accelerated GRPDA is constructed, which achieves the faster \(\mathcal{O}(1/N^2)\) ergodic convergence rate. These new results enrich the convergence theory of GRPDA. Furthermore, we demonstrate the superior performance of the accelerated GRPDA via preliminary numerical results on the least absolute deviation and the LASSO problems.

MSC:

65K10 Numerical optimization and variational techniques
65Y20 Complexity and performance of numerical algorithms
90C25 Convex programming