New Primal-Dual Algorithms for a Class of Nonsmooth and Nonlinear Convex-Concave Minimax Problems
本文针对一类非光滑非线性凸凹极小极大问题，提出结合广义增广拉格朗日函数、Nesterov加速和自适应参数更新的单循环原始对偶算法，在一般凸凹和凸线性情形下达到O(1/k)收敛率，并在凸线性问题中首次实现原始末次迭代最优率。
In this paper, we develop new primal-dual algorithms to solve a class of nonsmooth and nonlinear convex-concave minimax problems, which covers many existing and brand-new models as special cases. Our approach relies on a combination of a generalized augmented Lagrangian function, Nesterov's accelerated scheme, and adaptive parameter updating strategies. Our algorithmic framework is single-loop and unifies two important settings: general convex-concave and convex-linear cases. Under mild assumptions, our algorithms achieve $\mathcal{O}(1/k)$ convergence rates through three different criteria: primal-dual gap, primal objective residual, and dual objective residual, where $k$ is the iteration counter. Our rates are both ergodic (i.e., on a weighted averaging sequence) and nonergodic (i.e., on the last-iterate sequence). These convergence rates can be boosted up to $\mathcal{O}(1/k^2)$ if only one objective term is strongly convex (or, equivalently, its conjugate is $L$-smooth). To the best of our knowledge, this is the first algorithm achieving optimal rates on the primal last-iterate sequence for convex-linear minimax problems. As a byproduct, we specify our algorithms to solve a general convex cone constrained program with both ergodic and nonergodic rate guarantees. We test our algorithms and compare them with two recent methods on two numerical examples.