  


A relaxed customized proximal point algorithm for separable convex programming
Cai Xingju(caixingjunju.edu.cn) 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 DouglasRachford 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 overrelaxation 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 overrelaxation 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, overrelaxation Category 1: Convex and Nonsmooth Optimization (Convex Optimization ) Citation: Download: [PDF] Entry Submitted: 08/30/2011 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  