Optimization Online


Application of the Strictly Contractive Peaceman-Rachford Splitting Method to Multi-block Separable Convex Programming

Bingsheng He(hebma***at***nju.edu.cn)
Han Liu(hanliu***at***princeton.edu)
Junwei Lu(junweil***at***princeton.edu)
Xiaoming Yuan(xmyuan***at***hkbu.edu.hk)

Abstract: Recently, a strictly contractive Peaceman- Rachford splitting method (SC-PRSM) was proposed to solve a convex minimization model with linear constraints and a separable objective function which is the sum of two functions without coupled variables. We show by an example that the SC-PRSM cannot be directly extended to the case where the objective function is the sum of three or more functions. To solve such a multi-block model, if we treat its variables and functions as two groups and directly apply the SC-PRSM, then at least one of SC-PRSM's subproblems involves more than one function and variable which might not be easy to solve. One way to improve the solvability for this direct application of the SC-PRSM is to further decompose such a subproblem so as to generate easier decomposed subproblems which could potentially be easy enough to have closed-form solutions for some specific applications. The curse accompanying this improvement in solvability is that the SC-PRSM with further decomposed subproblems is not necessarily convergent, either. We will show its divergence by the same example. Our main goal is to show that the convergence can be guaranteed if the further decomposed subproblems of the direct application of the SC-PRSM are regularized by the proximal regularization. As a result, an SC-PRSM-based splitting algorithm with provable convergence and easy implementability is proposed for multi-block convex minimization models. We analyze the convergence for the derived algorithm, including proving its global convergence and establishing its worst-case convergence rate measured by the iteration complexity. The efficiency of the new algorithm is illustrated by testing some applications arising in image processing and statistical learning.

Keywords: Convex Programming, Peaceman-Rachford Splitting Method, Convergence Rate, Contraction Methods, Proximal Point Algorithm, Separable Models

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )


Download: [PDF]

Entry Submitted: 05/18/2014
Entry Accepted: 05/18/2014
Entry Last Modified: 05/18/2014

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