A modified strictly contractive peaceman-rachford splitting method for multi-block separable convex programming

Previous Article
Optimal dividend and capital injection strategy with excess-of-loss reinsurance and transaction costs
JIMO Home
This Issue
Next Article
An iterative algorithm for periodic sylvester matrix equations

January 2018, 14(1): 397-412. doi: 10.3934/jimo.2017052

A modified strictly contractive peaceman-rachford splitting method for multi-block separable convex programming

Su-Hong Jiang and Min Li ^,

School of Management and Engineering, Nanjing University, Nanjing 210093, China

_* Corresponding author: MIN LI

Received June 2016 Revised December 2016 Published June 2017

Fund Project: This research was supported by National Science Foundation of China (Grant No. 11401300,71602083,71671085 and 11001053) and Program for New Century Excellent Talents in University (Grant No. NCET-12-0111)

We propose a modified splitting method for a linearly constrained minimization model whose objective function is the sum of three convex functions without coupled variables. Our work is mainly inspired by the recently proposed strictly contractive Peaceman-Rachford splitting method (SC-PRSM) for a two-block separable convex minimization model. For the new method, we prove its convergence and estimate its convergence rates measured by iteration complexity in the nonergodic sense. We also test the SC-PRSM on the continuous resource allocation problem, and the numerical results show that our method has a competitive performance with the direct extension of ADMM which usually works well in practice but may fail to converge in theory.

Keywords: Convex programming, multi-block, Peaceman-Rachford splitting method, convergence rate, resource allocation.

Mathematics Subject Classification: Primary: 90C25; Secondary: 90B50.

Citation: Su-Hong Jiang, Min Li. A modified strictly contractive peaceman-rachford splitting method for multi-block separable convex programming. Journal of Industrial & Management Optimization, 2018, 14 (1) : 397-412. doi: 10.3934/jimo.2017052

References:

[1]	S. Boyd, N. Parikh, E. Chu, B. Peleato and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends in Machine Learning, 3 (2010), 1-122.
[2]	X. J. Cai, D. R. Han and X. M. Yuan, On the convergence of the direct extension of ADMM for three-block separable convex minimization models with one strongly convex function, Computational Optimization and Applications, 66 (2017), 39-73. doi: 10.1007/s10589-016-9860-y.
[3]	C. H. Chen, B. S. He, Y. Y. Ye and X. M. Yuan, The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent, Mathematical Programming Ser. A, 155 (2016), 57-79. doi: 10.1007/s10107-014-0826-5.
[4]	C. H. Chen, Y. Shen and Y. F. You, On the convergence analysis of the alternating direction method of multipliers with three blocks. Abstract and Applied Analysis, (2013), Article ID 183961, 7 pages.
[5]	E. Corman and X. M. Yuan, A generalized proximal point algorithm and its convergence rate, SIAM Journal on Optimization, 24 (2014), 1614-1638. doi: 10.1137/130940402.
[6]	Y. H. Dai, D. R. Han, X. M. Yuan and W. X. Zhang, A sequential updating scheme of the Lagrange multiplier for separable convex programming, Mathematics of Computation, 86 (2017), 315-343. doi: 10.1090/mcom/3104.
[7]	W. Deng, M.-J. Lai, Z. M. Peng and W. T. Yin, Parallel multi-block ADMM with o(1/k) convergence, Journal of Scientific Computing, 71 (2017), 712-736. doi: 10.1007/s10915-016-0318-2.
[8]	J. Douglas and H. H. Rachford, On the numerical solution of the heat conduction problem in $2$ and $3$ space variables, Transactions of the American Mathematical Society, 82 (1956), 421-439. doi: 10.1090/S0002-9947-1956-0084194-4.
[9]	D. Gabay, Applications of the method of multipliers to variational inequalities, in Augmented Lagrange Methods: Applications to the Solution of Boundary-valued Problems (eds. M. Fortin and R. Glowinski), North Holland, Amsterdam, The Netherlands, (1983), 299-331.
[10]	R. Glowinski, T. Kärkkäinen and K. Majava, On the convergence of operator-splitting methods, in Numerical Methods for Scientific Computing, Variational Problems and Applications (eds. Y. Kuznetsov, P. Neittanmaki and O. Pironneau), Barcelona, (2003).
[11]	R. Glowinski and A. Marrocco, Approximation par $\acute{e}$l$\acute{e}$ments finis d'ordre un et r$\acute{e}$solution par p$\acute{e}$nalisation-dualit$\acute{e}$ d'une classe de probl$\grave{e}$mes non lin$\acute{e}$aires, R.A.I.R.O., 9 (1975), 41-76.
[12]	D. R. Han, X. M Yuan, W. X. Zhang and X. J. Cai, An ADM-based splitting method for separable convex programming, Computational Optimization and Applications, 54 (2013), 343-369. doi: 10.1007/s10589-012-9510-y.
[13]	B. S. He, H. Liu, J. W. Lu and X. M. Yuan, Application of the strictly contractive PeacemanRachford splitting method to multi-block seperable convex programming, manuscript, in Splitting Methods in Communication and Imaging, Science, and Engineering (eds. R. Glowinski, S. Osher and W. Yin), Springer, Switzerland, (2016), 195-235.
[14]	B. S. He, H. Liu, Z. R. Wang and X. M. Yuan, A strictly contractive Peaceman-Rachford splitting method for convex programming, SIAM Journal on Optimization, 24 (2014), 1101-1140. doi: 10.1137/13090849X.
[15]	B. S. He, M. Tao and X. M. Yuan, A splitting method for separable convex programming, IMA Journal of Numerical Analysis, 35 (2015), 394-426. doi: 10.1093/imanum/drt060.
[16]	B. S. He, M. Tao and X. M. Yuan, Alternating direction method with Gaussian back substitution for separable convex programming, SIAM Journal on Optimization, 22 (2012), 313-340. doi: 10.1137/110822347.
[17]	B. S. He and X. M. Yuan, On the O(1/n) convergence rate of Douglas-Rachford alternating direction method, SIAM Journal on Numerical Analysis, 50 (2012), 700-709. doi: 10.1137/110836936.
[18]	B. S. He and X. M. Yuan, On nonergodic convergence rate of Douglas-Rachford alternating direction method of multipliers, Numerische Mathematik, 30 (2015), 567-577. doi: 10.1007/s00211-014-0673-6.
[19]	M. Li, D. F. Sun and K. -C. Toh, A convergent 3-block semi-proximal ADMM for convex minimization problems with one strongly convex block, Asia Pacific Journal of Operational Research, 32 (2015), 1550024, 19 pp. doi: 10.1142/S0217595915500244.
[20]	X. D. Li, D. F. Sun and K.-C. Toh, A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions, Mathematical Programming Ser. A, 155 (2016), 333-373. doi: 10.1007/s10107-014-0850-5.
[21]	T. Y. Lin, S. Q. Ma and S. Z. Zhang, On the global linear convergence of the ADMM with multi-block variables, SIAM Journal on Optimization, 25 (2015), 1478-1497. doi: 10.1137/140971178.
[22]	T. Y. Lin, S. Q. Ma and S. Z. Zhang, On the sublinear convergence rate of multi-block {ADMM}, Journal of the Operations Research Society of China, 3 (2015), 251-274. doi: 10.1007/s40305-015-0092-0.
[23]	P. L. Lions and B. Mercier, Splitting algorithms for the sum of two nonlinear operators, SIAM Journal on Numerical Analysis, 16 (1979), 964-979. doi: 10.1137/0716071.
[24]	S. Q. Ma, Alternating proximal gradient method for convex minimization, Journal of Scientific Computing, 68 (2016), 546-572. doi: 10.1007/s10915-015-0150-0.
[25]	Y. E. Nesterov, Gradient methods for minimizing composite objective function, Mathematical Programming Ser. B, 140 (2013), 125-161. doi: 10.1007/s10107-012-0629-5.
[26]	M. Patriksson, A survey on the continuous nonlinear resource allocation Problem, European Journal of Operations Research, 185 (2008), 1-46. doi: 10.1016/j.ejor.2006.12.006.
[27]	D. H. Peaceman and H. H. Rachford, The numerical solution of parabolic elliptic differential equations, SIAM Journal on Applied Mathematics, 3 (1955), 28-41. doi: 10.1137/0103003.
[28]	Y. G. Peng, A. Ganesh, J. Wright, W. L. Xu and Y. Ma, Robust alignment by sparse and low-rank decomposition for linearly correlated images, IEEE Transactions on Pattern Analysis and Machine Intelligence, 34 (2012), 2233-2246. doi: 10.1109/CVPR.2010.5540138.
[29]	M. Tao and X. M. Yuan, Recovering low-rank and sparse components of matrices from incomplete and noisy observations, SIAM Journal on Optimization, 21 (2011), 57-81. doi: 10.1137/100781894.
[30]	H. Uzawa, Market mechanisms and mathematical programming, Econometrica, 28 (1960), 872-881. doi: 10.2307/1907569.

show all references

References:

[1]	S. Boyd, N. Parikh, E. Chu, B. Peleato and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends in Machine Learning, 3 (2010), 1-122.
[2]	X. J. Cai, D. R. Han and X. M. Yuan, On the convergence of the direct extension of ADMM for three-block separable convex minimization models with one strongly convex function, Computational Optimization and Applications, 66 (2017), 39-73. doi: 10.1007/s10589-016-9860-y.
[3]	C. H. Chen, B. S. He, Y. Y. Ye and X. M. Yuan, The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent, Mathematical Programming Ser. A, 155 (2016), 57-79. doi: 10.1007/s10107-014-0826-5.
[4]	C. H. Chen, Y. Shen and Y. F. You, On the convergence analysis of the alternating direction method of multipliers with three blocks. Abstract and Applied Analysis, (2013), Article ID 183961, 7 pages.
[5]	E. Corman and X. M. Yuan, A generalized proximal point algorithm and its convergence rate, SIAM Journal on Optimization, 24 (2014), 1614-1638. doi: 10.1137/130940402.
[6]	Y. H. Dai, D. R. Han, X. M. Yuan and W. X. Zhang, A sequential updating scheme of the Lagrange multiplier for separable convex programming, Mathematics of Computation, 86 (2017), 315-343. doi: 10.1090/mcom/3104.
[7]	W. Deng, M.-J. Lai, Z. M. Peng and W. T. Yin, Parallel multi-block ADMM with o(1/k) convergence, Journal of Scientific Computing, 71 (2017), 712-736. doi: 10.1007/s10915-016-0318-2.
[8]	J. Douglas and H. H. Rachford, On the numerical solution of the heat conduction problem in $2$ and $3$ space variables, Transactions of the American Mathematical Society, 82 (1956), 421-439. doi: 10.1090/S0002-9947-1956-0084194-4.
[9]	D. Gabay, Applications of the method of multipliers to variational inequalities, in Augmented Lagrange Methods: Applications to the Solution of Boundary-valued Problems (eds. M. Fortin and R. Glowinski), North Holland, Amsterdam, The Netherlands, (1983), 299-331.
[10]	R. Glowinski, T. Kärkkäinen and K. Majava, On the convergence of operator-splitting methods, in Numerical Methods for Scientific Computing, Variational Problems and Applications (eds. Y. Kuznetsov, P. Neittanmaki and O. Pironneau), Barcelona, (2003).
[11]	R. Glowinski and A. Marrocco, Approximation par $\acute{e}$l$\acute{e}$ments finis d'ordre un et r$\acute{e}$solution par p$\acute{e}$nalisation-dualit$\acute{e}$ d'une classe de probl$\grave{e}$mes non lin$\acute{e}$aires, R.A.I.R.O., 9 (1975), 41-76.
[12]	D. R. Han, X. M Yuan, W. X. Zhang and X. J. Cai, An ADM-based splitting method for separable convex programming, Computational Optimization and Applications, 54 (2013), 343-369. doi: 10.1007/s10589-012-9510-y.
[13]	B. S. He, H. Liu, J. W. Lu and X. M. Yuan, Application of the strictly contractive PeacemanRachford splitting method to multi-block seperable convex programming, manuscript, in Splitting Methods in Communication and Imaging, Science, and Engineering (eds. R. Glowinski, S. Osher and W. Yin), Springer, Switzerland, (2016), 195-235.
[14]	B. S. He, H. Liu, Z. R. Wang and X. M. Yuan, A strictly contractive Peaceman-Rachford splitting method for convex programming, SIAM Journal on Optimization, 24 (2014), 1101-1140. doi: 10.1137/13090849X.
[15]	B. S. He, M. Tao and X. M. Yuan, A splitting method for separable convex programming, IMA Journal of Numerical Analysis, 35 (2015), 394-426. doi: 10.1093/imanum/drt060.
[16]	B. S. He, M. Tao and X. M. Yuan, Alternating direction method with Gaussian back substitution for separable convex programming, SIAM Journal on Optimization, 22 (2012), 313-340. doi: 10.1137/110822347.
[17]	B. S. He and X. M. Yuan, On the O(1/n) convergence rate of Douglas-Rachford alternating direction method, SIAM Journal on Numerical Analysis, 50 (2012), 700-709. doi: 10.1137/110836936.
[18]	B. S. He and X. M. Yuan, On nonergodic convergence rate of Douglas-Rachford alternating direction method of multipliers, Numerische Mathematik, 30 (2015), 567-577. doi: 10.1007/s00211-014-0673-6.
[19]	M. Li, D. F. Sun and K. -C. Toh, A convergent 3-block semi-proximal ADMM for convex minimization problems with one strongly convex block, Asia Pacific Journal of Operational Research, 32 (2015), 1550024, 19 pp. doi: 10.1142/S0217595915500244.
[20]	X. D. Li, D. F. Sun and K.-C. Toh, A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions, Mathematical Programming Ser. A, 155 (2016), 333-373. doi: 10.1007/s10107-014-0850-5.
[21]	T. Y. Lin, S. Q. Ma and S. Z. Zhang, On the global linear convergence of the ADMM with multi-block variables, SIAM Journal on Optimization, 25 (2015), 1478-1497. doi: 10.1137/140971178.
[22]	T. Y. Lin, S. Q. Ma and S. Z. Zhang, On the sublinear convergence rate of multi-block {ADMM}, Journal of the Operations Research Society of China, 3 (2015), 251-274. doi: 10.1007/s40305-015-0092-0.
[23]	P. L. Lions and B. Mercier, Splitting algorithms for the sum of two nonlinear operators, SIAM Journal on Numerical Analysis, 16 (1979), 964-979. doi: 10.1137/0716071.
[24]	S. Q. Ma, Alternating proximal gradient method for convex minimization, Journal of Scientific Computing, 68 (2016), 546-572. doi: 10.1007/s10915-015-0150-0.
[25]	Y. E. Nesterov, Gradient methods for minimizing composite objective function, Mathematical Programming Ser. B, 140 (2013), 125-161. doi: 10.1007/s10107-012-0629-5.
[26]	M. Patriksson, A survey on the continuous nonlinear resource allocation Problem, European Journal of Operations Research, 185 (2008), 1-46. doi: 10.1016/j.ejor.2006.12.006.
[27]	D. H. Peaceman and H. H. Rachford, The numerical solution of parabolic elliptic differential equations, SIAM Journal on Applied Mathematics, 3 (1955), 28-41. doi: 10.1137/0103003.
[28]	Y. G. Peng, A. Ganesh, J. Wright, W. L. Xu and Y. Ma, Robust alignment by sparse and low-rank decomposition for linearly correlated images, IEEE Transactions on Pattern Analysis and Machine Intelligence, 34 (2012), 2233-2246. doi: 10.1109/CVPR.2010.5540138.
[29]	M. Tao and X. M. Yuan, Recovering low-rank and sparse components of matrices from incomplete and noisy observations, SIAM Journal on Optimization, 21 (2011), 57-81. doi: 10.1137/100781894.
[30]	H. Uzawa, Market mechanisms and mathematical programming, Econometrica, 28 (1960), 872-881. doi: 10.2307/1907569.

Figure 1. Evolutions of objective function values w.r.t. CPU 20:20:30

Figure Options

Download full-size image

Download as PowerPoint slide

Table 1. The function $\phi(s)$ for generating the cost function

Name	$\phi(s_i):\Re_+\rightarrow [0, \, \infty)$	Parameters
Linear cost	$w_i s_i$	$w_i \in U(1, \, 5)\\ k_i \in U(1, \, 5)$
Power cost	$k_i s_i^{q_i}$
Piecewise quadratic cost	$\displaystyle \left\{ \begin{array}{ll} k_is_i^2, ~~~~~~~~~~~~~~~~~~~{\rm {if}}\, s_i \leq w_i/\sqrt{2k_i}\\ w_i\sqrt{2k}s- {w_i^2/2}, ~~~~{\rm{otherwise}}. \end{array} \right. $

Table Options

Download as excel

Name	$\phi(s_i):\Re_+\rightarrow [0, \, \infty)$	Parameters
Linear cost	$w_i s_i$	$w_i \in U(1, \, 5)\\ k_i \in U(1, \, 5)$
Power cost	$k_i s_i^{q_i}$
Piecewise quadratic cost	$\displaystyle \left\{ \begin{array}{ll} k_is_i^2, ~~~~~~~~~~~~~~~~~~~{\rm {if}}\, s_i \leq w_i/\sqrt{2k_i}\\ w_i\sqrt{2k}s- {w_i^2/2}, ~~~~{\rm{otherwise}}. \end{array} \right. $

[1]	Foxiang Liu, Lingling Xu, Yuehong Sun, Deren Han. A proximal alternating direction method for multi-block coupled convex optimization. Journal of Industrial & Management Optimization, 2019, 15 (2) : 723-737. doi: 10.3934/jimo.2018067
[2]	Zhongming Wu, Xingju Cai, Deren Han. Linearized block-wise alternating direction method of multipliers for multiple-block convex programming. Journal of Industrial & Management Optimization, 2018, 14 (3) : 833-855. doi: 10.3934/jimo.2017078
[3]	Qiying Hu, Wuyi Yue. Optimal control for resource allocation in discrete event systems. Journal of Industrial & Management Optimization, 2006, 2 (1) : 63-80. doi: 10.3934/jimo.2006.2.63
[4]	Irina Kareva, Faina Berezovkaya, Georgy Karev. Mixed strategies and natural selection in resource allocation. Mathematical Biosciences & Engineering, 2013, 10 (5&6) : 1561-1586. doi: 10.3934/mbe.2013.10.1561
[5]	Jinyan Fan, Jianyu Pan. On the convergence rate of the inexact Levenberg-Marquardt method. Journal of Industrial & Management Optimization, 2011, 7 (1) : 199-210. doi: 10.3934/jimo.2011.7.199
[6]	Yves Bourgault, Damien Broizat, Pierre-Emmanuel Jabin. Convergence rate for the method of moments with linear closure relations. Kinetic & Related Models, 2015, 8 (1) : 1-27. doi: 10.3934/krm.2015.8.1
[7]	Zhili Ge, Gang Qian, Deren Han. Global convergence of an inexact operator splitting method for monotone variational inequalities. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1013-1026. doi: 10.3934/jimo.2011.7.1013
[8]	Jian Gu, Xiantao Xiao, Liwei Zhang. A subgradient-based convex approximations method for DC programming and its applications. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1349-1366. doi: 10.3934/jimo.2016.12.1349
[9]	Ali Gharouni, Lin Wang. Modeling the spread of bed bug infestation and optimal resource allocation for disinfestation. Mathematical Biosciences & Engineering, 2016, 13 (5) : 969-980. doi: 10.3934/mbe.2016025
[10]	Tong Li, Hui Yin. Convergence rate to strong boundary layer solutions for generalized BBM-Burgers equations with non-convex flux. Communications on Pure & Applied Analysis, 2014, 13 (2) : 835-858. doi: 10.3934/cpaa.2014.13.835
[11]	Grigor Nika, Bogdan Vernescu. Rate of convergence for a multi-scale model of dilute emulsions with non-uniform surface tension. Discrete & Continuous Dynamical Systems - S, 2016, 9 (5) : 1553-1564. doi: 10.3934/dcdss.2016062
[12]	Bingsheng He, Xiaoming Yuan. Linearized alternating direction method of multipliers with Gaussian back substitution for separable convex programming. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 247-260. doi: 10.3934/naco.2013.3.247
[13]	Semu Mitiku Kassa. Three-level global resource allocation model for HIV control: A hierarchical decision system approach. Mathematical Biosciences & Engineering, 2018, 15 (1) : 255-273. doi: 10.3934/mbe.2018011
[14]	Yang Li, Yonghong Ren, Yun Wang, Jian Gu. Convergence analysis of a nonlinear Lagrangian method for nonconvex semidefinite programming with subproblem inexactly solved. Journal of Industrial & Management Optimization, 2015, 11 (1) : 65-81. doi: 10.3934/jimo.2015.11.65
[15]	Xiantao Xiao, Liwei Zhang, Jianzhong Zhang. On convergence of augmented Lagrangian method for inverse semi-definite quadratic programming problems. Journal of Industrial & Management Optimization, 2009, 5 (2) : 319-339. doi: 10.3934/jimo.2009.5.319
[16]	Tien-Fu Liang, Hung-Wen Cheng. Multi-objective aggregate production planning decisions using two-phase fuzzy goal programming method. Journal of Industrial & Management Optimization, 2011, 7 (2) : 365-383. doi: 10.3934/jimo.2011.7.365
[17]	Yulan Lu, Minghui Song, Mingzhu Liu. Convergence rate and stability of the split-step theta method for stochastic differential equations with piecewise continuous arguments. Discrete & Continuous Dynamical Systems - B, 2019, 24 (2) : 695-717. doi: 10.3934/dcdsb.2018203
[18]	Xiaoxiao Yuan, Jing Liu, Xingxing Hao. A moving block sequence-based evolutionary algorithm for resource investment project scheduling problems. Big Data & Information Analytics, 2017, 2 (1) : 39-58. doi: 10.3934/bdia.2017007
[19]	Haixiang Yao, Zhongfei Li, Yongzeng Lai. Dynamic mean-variance asset allocation with stochastic interest rate and inflation rate. Journal of Industrial & Management Optimization, 2016, 12 (1) : 187-209. doi: 10.3934/jimo.2016.12.187
[20]	Samuel T. Blake, Andrew Z. Tirkel. A multi-dimensional block-circulant perfect array construction. Advances in Mathematics of Communications, 2017, 11 (2) : 367-371. doi: 10.3934/amc.2017030

2017 Impact Factor: 0.994

Tools

Metrics

Tools

Article outline

Figures and Tables

2017 Impact Factor: 0.994

Tools

Figures and Tables

2017 Impact Factor: 0.994

American Institute of Mathematical Sciences