ACCELERATING BLOCK-DECOMPOSITION FIRST-ORDER METHODS FOR SOLVING COMPOSITE SADDLE-POINT AND TWO-PLAYER NASH EQUILIBRIUM PROBLEMS

作者：He Yunlong^*; Monteiro Renato D C

来源：SIAM Journal on Optimization, 2015, 25(4): 2182-2211.

DOI：10.1137/130943649

• Nash equilibrium
• monotone variational inequality
• saddle point
• block decomposition
• hybrid proximal-extragradient
• accelerated method
• complexity

This article considers the (two-player) composite Nash equilibrium (CNE) problem with a separable nonsmooth part, which is known to include the composite saddle-point (CSP) problem as a special case. Due to its two-block structure, this problem can be solved by any algorithm belonging to the block-decomposition hybrid proximal-extragradient (BD-HPE) framework proposed in [R. D. C. Monteiro and B. F. Svaiter, SIAM J. Optim., 23 (2013), pp. 475-507]. The framework consists of a family of inexact proximal point methods for solving a more general two-block structured monotone inclusion problem which, at every iteration, solves two prox subinclusions according to a certain relative error criterion. By exploiting the fact that the two prox subinclusions in the context of the CNE problem are equivalent to two composite convex programs, this article proposes a new instance of the BD-HPE framework that approximately solves them using an accelerated gradient method. It is shown that the new instance is able to take significantly larger prox stepsizes than other instances from this framework that perform single composite gradient steps for solving the subinclusions. As a result, it is shown that the first instance has better iteration-complexity than the latter ones. Finally, it is also shown that the new accelerated BD-HPE instance computationally outperforms several state-of-the-art algorithms on many relevant classes of CSP and CNE instances.

• 出版日期2015