Optimization Online


A relaxed customized proximal point algorithm for separable convex programming

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

Abstract: The alternating direction method (ADM) is classical for solving a linearly constrained separable convex programming problem (primal problem), and it is well known that ADM is essentially the application of a concrete form of the proximal point algorithm (PPA) (more precisely, the Douglas-Rachford splitting method) to the corresponding dual problem. This paper shows that an efficient method competitive to ADM can be easily derived by applying PPA directly to the primal problem. More specifically, if the proximal parameters are chosen judiciously according to the separable structure of the primal problem, the resulting customized PPA takes a similar decomposition algorithmic framework as that of ADM. The customized PPA and ADM are equally effective to exploit the separable structure of the primal problem, equally efficient in numerical senses and equally easy to implement. Moreover, the customized PPA is ready to be accelerated by an over-relaxation step, yielding a relaxed customized PPA for the primal problem. We verify numerically the competitive efficiency of the customized PPA to ADM, and the effectiveness of the over-relaxation step. Furthermore, we provide a simple proof for the O(1/t) convergence rate of the relaxed customized PPA.

Keywords: Proximal point algorithm, convex programming, separable structure, alternating direction method, convergence rate, over-relaxation

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )


Download: [PDF]

Entry Submitted: 08/30/2011
Entry Accepted: 08/30/2011
Entry Last Modified: 08/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