Optimization Online


Customized proximal point algorithms for linearly constrained convex minimization and saddle-point problems: a uniform approach

Guoyong Gu(ggu***at***nju.edu.cn)
Bingsheng He(hebma***at***nju.edu.cn)
Xiaoming Yuan(xmyuan***at***hkbu.edu.hk)

Abstract: This paper takes a uniform look at the customized applications of proximal point algorithm (PPA) to two classes of problems: the linearly constrained convex minimization problem with a generic or separable objective function and a saddle-point problem. We model these two classes of problems uniformly by a mixed variational inequality, and show how PPA with customized proximal parameters can yield favorable algorithms, which are able to exploit the structure of the models fully. Our customized PPA revisit turns out to be a uniform approach in designing a number of efficient algorithms, which are competitive with, or even more efficient than some benchmark methods in the existing literature such as the augmented Lagrangian method, the alternating direction method, the split inexact Uzawa method, and a class of primal-dual methods, etc. From the PPA perspective, the global convergence and the O(1/t) convergence rate for this series of algorithms are established in a uniform way.

Keywords: Convex minimization, saddle-point problem, proximal point algorithm, O(1/t) convergence rate, customized algorithms, splitting algorithms

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )


Download: [PDF]

Entry Submitted: 10/30/2011
Entry Accepted: 10/30/2011
Entry Last Modified: 10/30/2011

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