Primal-Dual Accelerated Mirror-Descent Method for Constrained Bilinear Saddle-Point Problems

We develop a first-order accelerated algorithm for a class of constrained bilinear saddle-point problems with applications to network systems. The algorithm is a modified time-varying primal-dual version of an accelerated mirror-descent dynamics. It deals with constraints such as simplices and convex set constraints effectively, and converges with a rate of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathcal {O}(1/t^{2})$</tex-math></inline-formula>. Furthermore, we employ the acceleration scheme for constrained distributed optimization and bilinear zero-sum games, and obtain two variants of distributed accelerated algorithms.