Optimization Online


Optimal Primal-Dual Methods for a Class of Saddle Point Problems

Yunmei Chen(yun***at***math.ufl.edu)
Guanghui Lan(glan***at***ise.ufl.edu)
Yuyuan Ouyang(ouyang***at***ufl.edu)

Abstract: We present a novel accelerated primal-dual (APD) method for solving a class of deterministic and stochastic saddle point problems (SPP). The basic idea of this algorithm is to incorporate a multi-step acceleration scheme into the primal-dual method without smoothing the objective function. For deterministic SPP, the APD method achieves the same optimal rate of convergence as Nesterov's smoothing technique. Our stochastic APD method exhibits an optimal rate of convergence for stochastic SPP not only in terms of its dependence on the number of the iteration, but also on a variety of problem parameters. To the best of our knowledge, this is the first time that such an optimal algorithm has been developed for stochastic SPP in the literature. Furthermore, for both deterministic and stochastic SPP, the developed APD algorithms can deal with the situation when the feasible region is unbounded, as long as a saddle point exists. In the unbounded case, we incorporate the modified termination criterion introduced by Monteiro and Svaiter in solving SPP problem posed as monotone inclusion, and demonstrate that the rate of convergence of the APD method depends on the distance from the initial point to the set of optimal solutions.


Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Stochastic Programming

Citation: Technical Report, Department of Industrial and Systems Engineering, University of Florida.

Download: [PDF]

Entry Submitted: 04/30/2013
Entry Accepted: 04/30/2013
Entry Last Modified: 04/30/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society