A distributed Douglas-Rachford splitting method for multi-block convex minimization problems
- PDF / 1,514,370 Bytes
- 27 Pages / 439.642 x 666.49 pts Page_size
- 50 Downloads / 173 Views
A distributed Douglas-Rachford splitting method for multi-block convex minimization problems Hongjin He · Deren Han
Received: 7 December 2013 / Accepted: 22 January 2015 © Springer Science+Business Media New York 2015
Abstract A customized Douglas-Rachford splitting method (DRSM) was recently proposed to solve two-block separable convex optimization problems with linear constraints and simple abstract constraints. The algorithm has advantage over the well-known alternating direction method of multipliers (ADMM), the dual application of DRSM to the two-block convex minimization problem, in the sense that the subproblems can have larger opportunity of possessing closed-form solutions since they are unconstrained. In this paper, we further study along this way by considering the primal application of DRSM for the general case m ≥ 3, i.e., we consider the multi-block separable convex minimization problem with linear constraints where the objective function is separable into m individual convex functions without coupled variables. The resulting method fully exploits the separable structure and enjoys decoupled subproblems which can be solved simultaneously. Both the exact and inexact versions of the new method are presented in a unified framework. Under mild conditions, we manage to prove the global convergence of the algorithm. Preliminary numerical experiments for extracting the background from corrupted surveillance video verify the encouraging efficiency of the new algorithm.
Communicated by: Zydrunas Gimbutas H. He Department of Mathematics, School of Science, Hangzhou Dianzi University, Hangzhou, 310018, China e-mail: [email protected] D. Han () School of Mathematical Sciences, Jiangsu Key Labratory for NSLSCS, Nanjing Normal University, Nanjing 210023, China e-mail: [email protected]
H. He, D. Han
Keywords Douglas-Rachford splitting method · Multi-block convex minimization problem · Alternating direction method of multipliers · Robust principal component analysis Mathematics Subject Classifications (2010) 90C25 · 65K10 · 94A08
1 Introduction and motivation We consider the multi-block convex minimization problem with linear constraints, where the objective function is the sum of m individual functions but without coupled variables: min
{x1 ,x2 ,··· ,xm }
m
m θi (xi ) Ai xi = b, xi ∈ Xi , i = 1, 2, · · · , m ,
i=1
(1.1)
i=1
where θi : Rni → R are closed proper convex functions (not necessarily smooth); Ai ∈ Rl×ni are given matrices; b ∈ Rl is a given vector; Xi ⊆ Rni are closed and convex nonempty sets, and they are further assumed to be simple enough to compute the projections onto them under the Euclidean norm (e.g., nonnegative orthant, spheroidal or box areas). Throughout this paper, we use the notation x := (x1 , x2 , · · · , xm ) and X := X1 × X2 × · · · × Xm . Moreover, we assume that the solution set of problem (1.1) is nonempty. Note that although we restrict the later discussion to the case of problem (1.1) with vector variables, all of the following results are available
Data Loading...
