• Previous Article
    Two penalized mixed–integer nonlinear programming approaches to tackle multicollinearity and outliers effects in linear regression models
  • JIMO Home
  • This Issue
  • Next Article
    Hadamard directional differentiability of the optimal value of a linear second-order conic programming problem
doi: 10.3934/jimo.2020016

The dual step size of the alternating direction method can be larger than 1.618 when one function is strongly convex

High-Tech Institute of Xi'an, Xi'an 710025, China

* Corresponding author: Feng Ma

Received  January 2019 Revised  June 2019 Published  January 2020

Fund Project: The first author is supported by NSFC grants 11701564 and 11871029.

The alternating direction method of multipliers (ADMM) is one of the most well-known optimization scheme for solving linearly constrained separable convex problem. In the literature, Fortin and Glowinski proved that the step size for updating the Lagrange multiplier of the ADMM can be chosen in the open interval of zero to the golden ratio. But, it is still unknown whether the dual step size can be larger than the golden ratio. In this paper, for the case where one function term is strongly convex and the associate coefficient matrix is full column rank, we present an affirmative answer to the above question. We then derive an exact relationship between the modulus and the dual step size. Our analysis deepens the understanding of the convergence properties of the ADMM.

Citation: Feng Ma, Jiansheng Shu, Yaxiong Li, Jian Wu. The dual step size of the alternating direction method can be larger than 1.618 when one function is strongly convex. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2020016
References:
[1]

F. BachR. JenattonJ. Mairal and G. Obozinski, Optimization with sparsity-inducing penalties, Found. Trends Mach. Learn., 4 (2012), 1-106.  doi: 10.1561/2200000015.  Google Scholar

[2]

S. BoydN. ParikhE. ChuB. Peleato and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn., 3 (2010), 1-122.  doi: 10.1561/2200000016.  Google Scholar

[3]

X. J. CaiD. 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, Comput. Optim. Appl., 66 (2017), 39-73.  doi: 10.1007/s10589-016-9860-y.  Google Scholar

[4]

C. H. ChenB. S. HeY. Y. Ye and X. M. Yuan, The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent, Math. Program., 155 (2016), 57-79.  doi: 10.1007/s10107-014-0826-5.  Google Scholar

[5]

W. Deng and W. T. Yin, On the global and linear convergence of the generalized alternating direction method of multipliers, J. Sci. Comput., 66 (2016), 889-916.  doi: 10.1007/s10915-015-0048-x.  Google Scholar

[6]

J. Eckstein and D. P. Bertsekas, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55 (1992), 293-318.  doi: 10.1007/BF01581204.  Google Scholar

[7]

J. Eckstein and M. Fukushima, Some reformulation and applications of the alternating direction method of multipliers, Large Scale Optimization, Kluwer Acad. Publ., Dordrecht, (1994), 115–134. doi: 10.1007/978-1-4613-3632-7_7.  Google Scholar

[8]

J. Eckstein and W. Yao, Understanding the convergence of the alternating direction method of multipliers: Theoretical and computational perspectives, Pacific J. Optim., 11 (2015), 619-644.   Google Scholar

[9]

M. Fortin and R. Glowinski, Augmented Lagrangian Methods: Applications to the Numerical Solutions of Boundary Value Problems, Studies in Mathematics and its Applications, 15. North-Holland Publishing Co., Amsterdam, 1983.  Google Scholar

[10]

D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite-element approximations, Comput. Math. Appli., 2 (1976), 17-40.  doi: 10.1016/0898-1221(76)90003-1.  Google Scholar

[11]

R. Glowinski and A. Marrocco, Sur l'approximation par éléments finis d'ordre un et la résolution par pénalisation-dualité d'une classe de problèmes de Dirichlet non linéaires, Revue Fr. Autom. Inform. Rech. Opér., Anal. Numér., 9 (1975), 41-76.  doi: 10.1051/m2an/197509R200411.  Google Scholar

[12]

R. Glowinski, Numerical Methods for Nonlinear Variational Problems, Springer Series in Computational Physics, Springer-Verlag, New York, 1984. doi: 10.1007/978-3-662-12613-4.  Google Scholar

[13]

R. Glowinski, On alternating direction methods of multipliers: A historical perspective, Modeling, Simulation and Optimization for Science and Technology, Computational Methods in Applied Sciences, Springer, Dordrecht, 34 (2014), 59-82.  doi: 10.1007/978-94-017-9054-3_4.  Google Scholar

[14]

R. Glowinski, S. J. Osher and W. T. Yin, Splitting Methods in Communication, Imaging, Science, and Engineering, Scientific Computation. Springer, Cham, 2016. doi: 10.1007/978-3-319-41589-5.  Google Scholar

[15]

D. Han and X. M. Yuan, A note on the alternating direction method of multiplier, J. Optim. Theory Appl, 155 (2012), 227-238.  doi: 10.1007/s10957-012-0003-z.  Google Scholar

[16]

B. S. HeH. LiuZ. R. Wang and X. M. Yuan, A strictly contractive Peaceman-Rachford splitting method for convex programming, SIAM J. Optim., 24 (2014), 1011-1040.  doi: 10.1137/13090849X.  Google Scholar

[17]

B. S. HeF. Ma and X. M. Yuan, Convergence study on the symmetric version of ADMM with larger step sizes, SIAM J. Imaging Sci., 9 (2016), 1467-1501.  doi: 10.1137/15M1044448.  Google Scholar

[18]

B. S. He and X. M. Yuan, On the $O(1/n)$ convergence rate of the Douglas-Rachford alternating direction method, SIAM J. Num. Anal., 50 (2012), 700-709.  doi: 10.1137/110836936.  Google Scholar

[19]

B. S. He and X. M. Yuan, On non-ergodic convergence rate of Douglas-Rachford alternating direction method of multipliers, Numer. Math., 130 (2015), 567-577.  doi: 10.1007/s00211-014-0673-6.  Google Scholar

[20]

M. Y. Hong and Z.-Q. Luo, On the linear convergence of the alternating direction method of multipliers, Math. Program., 162 (2017), 165-199.  doi: 10.1007/s10107-016-1034-2.  Google Scholar

[21]

Y. ShenZ. W. Wen and Y. Zhang, Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization, Optim. Methods Softw., 29 (2014), 239-263.  doi: 10.1080/10556788.2012.700713.  Google Scholar

[22]

M. Tao and X. M. Yuan, On Glowinski's open question on the alternating direction method of multipliers, J. Optim. Theory Appl., 179 (2018), 163-196.  doi: 10.1007/s10957-018-1338-x.  Google Scholar

[23]

Z. W. WenD. Goldfarb and W. T. Yin, Alternating direction augmented Lagrangian methods for semidefinite programming, Math. Program. Comput., 2 (2010), 203-230.  doi: 10.1007/s12532-010-0017-1.  Google Scholar

[24]

J. F. YangY. Zhang and W. T. Yin, A fast alternating direction method for TVL1-L2 signal reconstruction from partial Fourier data, IEEE J. Selec. Topics Signal Proc., 4 (2010), 288-297.  doi: 10.1109/JSTSP.2010.2042333.  Google Scholar

show all references

References:
[1]

F. BachR. JenattonJ. Mairal and G. Obozinski, Optimization with sparsity-inducing penalties, Found. Trends Mach. Learn., 4 (2012), 1-106.  doi: 10.1561/2200000015.  Google Scholar

[2]

S. BoydN. ParikhE. ChuB. Peleato and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn., 3 (2010), 1-122.  doi: 10.1561/2200000016.  Google Scholar

[3]

X. J. CaiD. 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, Comput. Optim. Appl., 66 (2017), 39-73.  doi: 10.1007/s10589-016-9860-y.  Google Scholar

[4]

C. H. ChenB. S. HeY. Y. Ye and X. M. Yuan, The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent, Math. Program., 155 (2016), 57-79.  doi: 10.1007/s10107-014-0826-5.  Google Scholar

[5]

W. Deng and W. T. Yin, On the global and linear convergence of the generalized alternating direction method of multipliers, J. Sci. Comput., 66 (2016), 889-916.  doi: 10.1007/s10915-015-0048-x.  Google Scholar

[6]

J. Eckstein and D. P. Bertsekas, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55 (1992), 293-318.  doi: 10.1007/BF01581204.  Google Scholar

[7]

J. Eckstein and M. Fukushima, Some reformulation and applications of the alternating direction method of multipliers, Large Scale Optimization, Kluwer Acad. Publ., Dordrecht, (1994), 115–134. doi: 10.1007/978-1-4613-3632-7_7.  Google Scholar

[8]

J. Eckstein and W. Yao, Understanding the convergence of the alternating direction method of multipliers: Theoretical and computational perspectives, Pacific J. Optim., 11 (2015), 619-644.   Google Scholar

[9]

M. Fortin and R. Glowinski, Augmented Lagrangian Methods: Applications to the Numerical Solutions of Boundary Value Problems, Studies in Mathematics and its Applications, 15. North-Holland Publishing Co., Amsterdam, 1983.  Google Scholar

[10]

D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite-element approximations, Comput. Math. Appli., 2 (1976), 17-40.  doi: 10.1016/0898-1221(76)90003-1.  Google Scholar

[11]

R. Glowinski and A. Marrocco, Sur l'approximation par éléments finis d'ordre un et la résolution par pénalisation-dualité d'une classe de problèmes de Dirichlet non linéaires, Revue Fr. Autom. Inform. Rech. Opér., Anal. Numér., 9 (1975), 41-76.  doi: 10.1051/m2an/197509R200411.  Google Scholar

[12]

R. Glowinski, Numerical Methods for Nonlinear Variational Problems, Springer Series in Computational Physics, Springer-Verlag, New York, 1984. doi: 10.1007/978-3-662-12613-4.  Google Scholar

[13]

R. Glowinski, On alternating direction methods of multipliers: A historical perspective, Modeling, Simulation and Optimization for Science and Technology, Computational Methods in Applied Sciences, Springer, Dordrecht, 34 (2014), 59-82.  doi: 10.1007/978-94-017-9054-3_4.  Google Scholar

[14]

R. Glowinski, S. J. Osher and W. T. Yin, Splitting Methods in Communication, Imaging, Science, and Engineering, Scientific Computation. Springer, Cham, 2016. doi: 10.1007/978-3-319-41589-5.  Google Scholar

[15]

D. Han and X. M. Yuan, A note on the alternating direction method of multiplier, J. Optim. Theory Appl, 155 (2012), 227-238.  doi: 10.1007/s10957-012-0003-z.  Google Scholar

[16]

B. S. HeH. LiuZ. R. Wang and X. M. Yuan, A strictly contractive Peaceman-Rachford splitting method for convex programming, SIAM J. Optim., 24 (2014), 1011-1040.  doi: 10.1137/13090849X.  Google Scholar

[17]

B. S. HeF. Ma and X. M. Yuan, Convergence study on the symmetric version of ADMM with larger step sizes, SIAM J. Imaging Sci., 9 (2016), 1467-1501.  doi: 10.1137/15M1044448.  Google Scholar

[18]

B. S. He and X. M. Yuan, On the $O(1/n)$ convergence rate of the Douglas-Rachford alternating direction method, SIAM J. Num. Anal., 50 (2012), 700-709.  doi: 10.1137/110836936.  Google Scholar

[19]

B. S. He and X. M. Yuan, On non-ergodic convergence rate of Douglas-Rachford alternating direction method of multipliers, Numer. Math., 130 (2015), 567-577.  doi: 10.1007/s00211-014-0673-6.  Google Scholar

[20]

M. Y. Hong and Z.-Q. Luo, On the linear convergence of the alternating direction method of multipliers, Math. Program., 162 (2017), 165-199.  doi: 10.1007/s10107-016-1034-2.  Google Scholar

[21]

Y. ShenZ. W. Wen and Y. Zhang, Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization, Optim. Methods Softw., 29 (2014), 239-263.  doi: 10.1080/10556788.2012.700713.  Google Scholar

[22]

M. Tao and X. M. Yuan, On Glowinski's open question on the alternating direction method of multipliers, J. Optim. Theory Appl., 179 (2018), 163-196.  doi: 10.1007/s10957-018-1338-x.  Google Scholar

[23]

Z. W. WenD. Goldfarb and W. T. Yin, Alternating direction augmented Lagrangian methods for semidefinite programming, Math. Program. Comput., 2 (2010), 203-230.  doi: 10.1007/s12532-010-0017-1.  Google Scholar

[24]

J. F. YangY. Zhang and W. T. Yin, A fast alternating direction method for TVL1-L2 signal reconstruction from partial Fourier data, IEEE J. Selec. Topics Signal Proc., 4 (2010), 288-297.  doi: 10.1109/JSTSP.2010.2042333.  Google Scholar

[1]

Hui Gao, Jian Lv, Xiaoliang Wang, Liping Pang. An alternating linearization bundle method for a class of nonconvex optimization problem with inexact information. Journal of Industrial & Management Optimization, 2021, 17 (2) : 805-825. doi: 10.3934/jimo.2019135

[2]

George W. Patrick. The geometry of convergence in numerical analysis. Journal of Computational Dynamics, 2021, 8 (1) : 33-58. doi: 10.3934/jcd.2021003

[3]

Peter Frolkovič, Viera Kleinová. A new numerical method for level set motion in normal direction used in optical flow estimation. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 851-863. doi: 10.3934/dcdss.2020347

[4]

Ke Su, Yumeng Lin, Chun Xu. A new adaptive method to nonlinear semi-infinite programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021012

[5]

Tengfei Yan, Qunying Liu, Bowen Dou, Qing Li, Bowen Li. An adaptive dynamic programming method for torque ripple minimization of PMSM. Journal of Industrial & Management Optimization, 2021, 17 (2) : 827-839. doi: 10.3934/jimo.2019136

[6]

Matúš Tibenský, Angela Handlovičová. Convergence analysis of the discrete duality finite volume scheme for the regularised Heston model. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1181-1195. doi: 10.3934/dcdss.2020226

[7]

Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial & Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115

[8]

Hassan Mohammad. A diagonal PRP-type projection method for convex constrained nonlinear monotone equations. Journal of Industrial & Management Optimization, 2021, 17 (1) : 101-116. doi: 10.3934/jimo.2019101

[9]

Wei Ouyang, Li Li. Hölder strong metric subregularity and its applications to convergence analysis of inexact Newton methods. Journal of Industrial & Management Optimization, 2021, 17 (1) : 169-184. doi: 10.3934/jimo.2019105

[10]

Editorial Office. Retraction: Xiao-Qian Jiang and Lun-Chuan Zhang, Stock price fluctuation prediction method based on time series analysis. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 915-915. doi: 10.3934/dcdss.2019061

[11]

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

[12]

Wenrui Hao, King-Yeung Lam, Yuan Lou. Ecological and evolutionary dynamics in advective environments: Critical domain size and boundary conditions. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 367-400. doi: 10.3934/dcdsb.2020283

[13]

Matania Ben–Artzi, Joseph Falcovitz, Jiequan Li. The convergence of the GRP scheme. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 1-27. doi: 10.3934/dcds.2009.23.1

[14]

Cheng Peng, Zhaohui Tang, Weihua Gui, Qing Chen, Jing He. A bidirectional weighted boundary distance algorithm for time series similarity computation based on optimized sliding window size. Journal of Industrial & Management Optimization, 2021, 17 (1) : 205-220. doi: 10.3934/jimo.2019107

[15]

Tien-Yu Lin, Bhaba R. Sarker, Chien-Jui Lin. An optimal setup cost reduction and lot size for economic production quantity model with imperfect quality and quantity discounts. Journal of Industrial & Management Optimization, 2021, 17 (1) : 467-484. doi: 10.3934/jimo.2020043

[16]

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

[17]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102

[18]

Pablo Neme, Jorge Oviedo. A note on the lattice structure for matching markets via linear programming. Journal of Dynamics & Games, 2020  doi: 10.3934/jdg.2021001

[19]

Martin Heida, Stefan Neukamm, Mario Varga. Stochastic homogenization of $ \Lambda $-convex gradient flows. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 427-453. doi: 10.3934/dcdss.2020328

[20]

Haodong Yu, Jie Sun. Robust stochastic optimization with convex risk measures: A discretized subgradient scheme. Journal of Industrial & Management Optimization, 2021, 17 (1) : 81-99. doi: 10.3934/jimo.2019100

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (83)
  • HTML views (381)
  • Cited by (0)

Other articles
by authors

[Back to Top]