Search

This paper presents an accelerated variant of the hybrid proximal extragradient (HPE) method for convex optimization, referred to as the accelerated HPE (A-HPE) framework. Iteration-complexity results are established for the A-HPE framework, as well as a special version of it, where a large stepsize condition is imposed. Two specific implementations of the A-HPE framework are described in the context of a structured convex optimization problem whose objective function consists of the sum of a smooth convex function and an extended real-valued nonsmooth convex function. In the first implementation, a generalization of a variant of Nesterov's method is obtained for the case where the smooth component of the objective function has Lipschitz continuous gradient. In the second implementation, an accelerated Newton proximal extragradient (A-NPE) method is obtained for the case where the smooth component of the objective function has Lipschitz continuous Hessian. It is shown that the A-NPE method has a O(1/k7/2) convergence rate, which improves upon the O(1/k³) convergence rate bound for another accelerated Newton-type method presented by Nesterov. Finally, while Nesterov's method is based on exact solutions of subproblems with cubic regularization terms, the A-NPE method is based on inexact solutions of subproblems with quadratic regularization terms and hence is potentially more tractable from a computational point of view. [ABSTRACT FROM AUTHOR]

We consider the development of single-timescale schemes for the distributed computation of equilibria associated with Nash games in which each player solves a convex program. Equilibria associated with such games are wholly captured by the solution set of a variational inequality. Our focus is on a class of games, termed monotone Nash games, that lead to monotone variational inequalities. Distributed extensions of standard approaches for solving such variational problems are characterized by two challenges: (1) Unless suitable assumptions (such as strong monotonicity) are imposed on the mapping arising in the specification of the variational inequality, iterative methods often require the solution of a sequence of regularized problems, a naturally two-timescale process that is harder to implement in practice. (2) Additionally, algorithm parameters for all players (such as steplengths and regularization parameters) have to be chosen centrally and communicated to all players; importantly, these parameters cannot be independently chosen by a player. Motivated by these shortcomings, we present two practically implementable distributed regularization schemes that work on a single timescale; specifically, each scheme requires precisely one gradient or projection step at every iteration. Of these, the first is an iterative Tikhonov regularization (ITR) scheme, while the second is an analogously constructed iterative proximal-point (IPP) method. Both schemes are characterized by the property that the regularization/centering parameter are updated after every iteration, rather than when one has approximately solved the regularized problem. To aid in distributed settings requiring limited coordination across players, the schemes allow players to select their parameters independently and do not insist on central prescription of such parameters. We conclude with an application of these schemes on a networked Cournot game with nonlinear prices. [ABSTRACT FROM AUTHOR]