American Institute of Mathematical Sciences

Advanced
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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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). Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[30]

H. Uzawa, Market mechanisms and mathematical programming, Econometrica, 28 (1960), 872-881.  doi: 10.2307/1907569.  Google Scholar

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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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). Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[30]

H. Uzawa, Market mechanisms and mathematical programming, Econometrica, 28 (1960), 872-881.  doi: 10.2307/1907569.  Google Scholar

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]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077
[2]

Shengxin Zhu, Tongxiang Gu, Xingping Liu. AIMS: Average information matrix splitting. Mathematical Foundations of Computing, 2020, 3 (4) : 301-308. doi: 10.3934/mfc.2020012
[3]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054
[4]

Thierry Horsin, Mohamed Ali Jendoubi. On the convergence to equilibria of a sequence defined by an implicit scheme. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020465
[5]

Hirokazu Ninomiya. Entire solutions of the Allen–Cahn–Nagumo equation in a multi-dimensional space. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 395-412. doi: 10.3934/dcds.2020364
[6]

Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018
[7]

Reza Lotfi, Zahra Yadegari, Seyed Hossein Hosseini, Amir Hossein Khameneh, Erfan Babaee Tirkolaee, Gerhard-Wilhelm Weber. A robust time-cost-quality-energy-environment trade-off with resource-constrained in project management: A case study for a bridge construction project. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020158
[8]

A. M. Elaiw, N. H. AlShamrani, A. Abdel-Aty, H. Dutta. Stability analysis of a general HIV dynamics model with multi-stages of infected cells and two routes of infection. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020441
[9]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013
[10]

Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020076
[11]

Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070
[12]

Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019
[13]

Lei Liu, Li Wu. Multiplicity of closed characteristics on $ P $-symmetric compact convex hypersurfaces in $ \mathbb{R}^{2n} $. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020378
[14]

Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao. A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28 (4) : 1439-1457. doi: 10.3934/era.2020076
[15]

Zexuan Liu, Zhiyuan Sun, Jerry Zhijian Yang. A numerical study of superconvergence of the discontinuous Galerkin method by patch reconstruction. Electronic Research Archive, 2020, 28 (4) : 1487-1501. doi: 10.3934/era.2020078
[16]

Yuxia Guo, Shaolong Peng. A direct method of moving planes for fully nonlinear nonlocal operators and applications. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020462
[17]

Noah Stevenson, Ian Tice. A truncated real interpolation method and characterizations of screened Sobolev spaces. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5509-5566. doi: 10.3934/cpaa.2020250
[18]

Yue Feng, Yujie Liu, Ruishu Wang, Shangyou Zhang. A conforming discontinuous Galerkin finite element method on rectangular partitions. Electronic Research Archive, , () : -. doi: 10.3934/era.2020120
[19]

Leilei Wei, Yinnian He. A fully discrete local discontinuous Galerkin method with the generalized numerical flux to solve the tempered fractional reaction-diffusion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020319
[20]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (107)
  • HTML views (785)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences