A Partially Parallel Prediction-Correction Splitting Method for Convex Optimization Problems with Separable Structure
- PDF / 471,219 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 14 Downloads / 205 Views
A Partially Parallel Prediction-Correction Splitting Method for Convex Optimization Problems with Separable Structure Fu-Sheng Bai1 · Ling Xu1
Received: 6 October 2016 / Revised: 31 December 2016 / Accepted: 5 April 2017 © Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press, and Springer-Verlag Berlin Heidelberg 2017
Abstract In this paper, we propose a partially parallel prediction-correction splitting method for solving block-separable linearly constrained convex optimization problems with three blocks. Unlike the extended alternating direction method of multipliers, the last two subproblems in the prediction step are solved parallelly, and a correction step is employed in the method to correct the dual variable and two blocks of the primal variables. The step size adapted in the correction step allows for major contribution from the latest solution point to the iteration point. Some numerical results are reported to show the effectiveness of the presented method. Keywords Block-separable convex optimization · Extended alternating direction method of multipliers · Prediction–correction splitting method Mathematics Subject Classification 90C25 · 90C30
1 Introduction We consider a separable convex optimization problem with linear constraints min{ f (x) + g(y) + h(z)|Ax + By + C z = b, x ∈ X, y ∈ Y, z ∈ Z },
(1.1)
This paper is dedicated to Professor Lian-Sheng Zhang in celebration of his 80th birthday.
B
Fu-Sheng Bai [email protected] Ling Xu [email protected]
1
School of Mathematical Sciences, Chongqing Normal University, Chongqing 401331, China
123
F.-S. Bai, L. Xu
where f : Rn 1 → R, g : Rn 2 → R, h : Rn 3 → R are closed proper convex function; A ∈ Rl×n 1 , B ∈ Rl×n 2 , C ∈ Rl×n 3 are full-column-rank matrices; b ∈ Rl ; X ⊆ Rn 1 , Y ⊆ Rn 2 , Z ⊆ Rn 3 are nonempty closed convex sets, and n 1 +n 2 +n 3 = n. This type of problems appears in various fields, such as image decomposition, network economics and traffic assignment, quite often; see [1–5] and the references therein. To solve problem (1.1), we introduce a Lagrange multiplier vector λ ∈ Rl corresponding to the linear constraints Ax + By + C z = b, and assume that there is a saddle point in problem (1.1), denoted by u ∗ = (x ∗ , y ∗ , z ∗ , λ∗ ). Obviously, u ∗ is a saddle point of problem (1.1) if and only if it is a solution of the following variational inequality problem: Find u ∗ = (x ∗ , y ∗ , z ∗ , λ∗ ) such that θ (w) − θ (w ∗ ) + (u − u ∗ )T P(u ∗ ) 0,
∀ u ∈ U := X × Y × Z × Rl , (1.2)
where θ (w) = f (x) + g(y) + h(z),
u=
w λ
⎞ ⎛ ⎞ ⎛ −AT λ x ⎟ ⎜y⎟ ⎜ −B T λ ⎟. ⎟ ⎜ =⎜ T ⎠ ⎝ z ⎠ , P(u) = ⎝ −C λ λ Ax + By + C z − b
(1.3)
Let L β (x, y, z, λ) := θ1 (x) + θ2 (y) + θ3 (z) − λT (Ax + By + C z − b) β + Ax + By + C z − b2 2 be the augmented Lagrangian function of problem (1.1), where β > 0 is the penalty parameter; · denotes the Euclidean norm. Problem (1.1) can be solved by the classical augmented Lagrangian method (ALM), see, e.g., [3] and [6] via the following iterative scheme:
∈
Data Loading...
