2016, 6(1): 45-54. doi: 10.3934/naco.2016.6.45

A new convergence proof of augmented Lagrangian-based method with full Jacobian decomposition for structured variational inequalities

1. 

Higher Education Key Laboratory of Engineering and Scientific Computing, Taiyuan Normal University, Taiyuan 030012, Shanxi Province, China

Received  June 2015 Revised  January 2016 Published  January 2016

In the work, we present a new proof for global convergence of a classical method, augmented Lagrangian-based method with full Jacobian decomposition, for a special class of variational inequality problems with a separable structure. This work can be regarded as an improvement to work [14]. The convergence result of the work is established under more general conditions and proven in a new way.
Citation: Xi-Hong Yan. A new convergence proof of augmented Lagrangian-based method with full Jacobian decomposition for structured variational inequalities. Numerical Algebra, Control and Optimization, 2016, 6 (1) : 45-54. doi: 10.3934/naco.2016.6.45
References:
[1]

S. Dafermos, Traffic Equilibrium and Variational Inequalities, Transportation Science, 14 (1980), 42-54. doi: 10.1287/trsc.14.1.42.

[2]

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

[3]

M. Fukushima, Application of the alternating direction method of multipliers to separable convex programming problems, Computational Optimization and Applications, 1 (1992), 93-111. doi: 10.1007/BF00247655.

[4]

D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximations, Computers and Mathematics with Applications, 2 (1976), 17-40.

[5]

D. Han, H. He and L. Xu, A proximal parallel splitting method for minimizing sum of convex functions with linear constraints, Journal of Computational and Applied Mathematics, 256 (2014), 36-51. doi: 10.1016/j.cam.2013.07.010.

[6]

D. Han and X. Yuan, A Note on the Alternating Direction Method of Multipliers, Journal of Optimization Theory and Applications, 155 (2012), 227-238. doi: 10.1007/s10957-012-0003-z.

[7]

D. Han, X. Yuan and W. Zhang, An augmented Lagrangian based parallel splitting method for separable convex minimization with applications to image processing, Mathematics of Computation, 83 (2014), 2263-2291. doi: 10.1090/S0025-5718-2014-02829-9.

[8]

P. Harker and J. S. Pang, Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications, Mathematical Programming, 48 (1990), 161-220. doi: 10.1007/BF01582255.

[9]

B. He, L. Hou and X. Yuan, On full Jacobian decomposition of the augmented Lagrangian method for separable convex programming, Preprint, 2013. doi: 10.1137/130922793.

[10]

B. He, M. Tao, M. Xu and X. Yuan, An alternating direction-based contraction method for linearly constrained separable convex programming problems, Optimization, 62 (2013), 573-596. doi: 10.1080/02331934.2011.611885.

[11]

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.

[12]

B. He, M. Tao and X. Yuan, A splitting method for separable convex programming, IMA Journal of Numerical Analysis, 35 (2015), 394-426. doi: 10.1093/imanum/drt060.

[13]

A. Nagurney, Network Economics: A Variational Inequality Approach, Kluwer Academic Publishers, Dordrecht, 1993. doi: 10.1007/978-94-011-2178-1.

[14]

K. Wang, J. Desai and H. He, A note on augmented Lagrangian-based parallel splitting method, Optimization Letters, (2014), 1-14. doi: 10.1007/s11590-014-0825-8.

show all references

References:
[1]

S. Dafermos, Traffic Equilibrium and Variational Inequalities, Transportation Science, 14 (1980), 42-54. doi: 10.1287/trsc.14.1.42.

[2]

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

[3]

M. Fukushima, Application of the alternating direction method of multipliers to separable convex programming problems, Computational Optimization and Applications, 1 (1992), 93-111. doi: 10.1007/BF00247655.

[4]

D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximations, Computers and Mathematics with Applications, 2 (1976), 17-40.

[5]

D. Han, H. He and L. Xu, A proximal parallel splitting method for minimizing sum of convex functions with linear constraints, Journal of Computational and Applied Mathematics, 256 (2014), 36-51. doi: 10.1016/j.cam.2013.07.010.

[6]

D. Han and X. Yuan, A Note on the Alternating Direction Method of Multipliers, Journal of Optimization Theory and Applications, 155 (2012), 227-238. doi: 10.1007/s10957-012-0003-z.

[7]

D. Han, X. Yuan and W. Zhang, An augmented Lagrangian based parallel splitting method for separable convex minimization with applications to image processing, Mathematics of Computation, 83 (2014), 2263-2291. doi: 10.1090/S0025-5718-2014-02829-9.

[8]

P. Harker and J. S. Pang, Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications, Mathematical Programming, 48 (1990), 161-220. doi: 10.1007/BF01582255.

[9]

B. He, L. Hou and X. Yuan, On full Jacobian decomposition of the augmented Lagrangian method for separable convex programming, Preprint, 2013. doi: 10.1137/130922793.

[10]

B. He, M. Tao, M. Xu and X. Yuan, An alternating direction-based contraction method for linearly constrained separable convex programming problems, Optimization, 62 (2013), 573-596. doi: 10.1080/02331934.2011.611885.

[11]

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.

[12]

B. He, M. Tao and X. Yuan, A splitting method for separable convex programming, IMA Journal of Numerical Analysis, 35 (2015), 394-426. doi: 10.1093/imanum/drt060.

[13]

A. Nagurney, Network Economics: A Variational Inequality Approach, Kluwer Academic Publishers, Dordrecht, 1993. doi: 10.1007/978-94-011-2178-1.

[14]

K. Wang, J. Desai and H. He, A note on augmented Lagrangian-based parallel splitting method, Optimization Letters, (2014), 1-14. doi: 10.1007/s11590-014-0825-8.

[1]

Xihong Yan. An augmented Lagrangian-based parallel splitting method for a one-leader-two-follower game. Journal of Industrial and Management Optimization, 2016, 12 (3) : 879-890. doi: 10.3934/jimo.2016.12.879

[2]

Yuan Shen, Wenxing Zhang, Bingsheng He. Relaxed augmented Lagrangian-based proximal point algorithms for convex optimization with linear constraints. Journal of Industrial and Management Optimization, 2014, 10 (3) : 743-759. doi: 10.3934/jimo.2014.10.743

[3]

Anis Theljani, Ke Chen. An augmented lagrangian method for solving a new variational model based on gradients similarity measures and high order regulariation for multimodality registration. Inverse Problems and Imaging, 2019, 13 (2) : 309-335. doi: 10.3934/ipi.2019016

[4]

Li Jin, Hongying Huang. Differential equation method based on approximate augmented Lagrangian for nonlinear programming. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2267-2281. doi: 10.3934/jimo.2019053

[5]

Wei Zhu, Xue-Cheng Tai, Tony Chan. Augmented Lagrangian method for a mean curvature based image denoising model. Inverse Problems and Imaging, 2013, 7 (4) : 1409-1432. doi: 10.3934/ipi.2013.7.1409

[6]

Yoshifumi Aimoto, Takayasu Matsuo, Yuto Miyatake. A local discontinuous Galerkin method based on variational structure. Discrete and Continuous Dynamical Systems - S, 2015, 8 (5) : 817-832. doi: 10.3934/dcdss.2015.8.817

[7]

Xiantao Xiao, Liwei Zhang, Jianzhong Zhang. On convergence of augmented Lagrangian method for inverse semi-definite quadratic programming problems. Journal of Industrial and Management Optimization, 2009, 5 (2) : 319-339. doi: 10.3934/jimo.2009.5.319

[8]

Egil Bae, Xue-Cheng Tai, Wei Zhu. Augmented Lagrangian method for an Euler's elastica based segmentation model that promotes convex contours. Inverse Problems and Imaging, 2017, 11 (1) : 1-23. doi: 10.3934/ipi.2017001

[9]

Dan Xue, Wenyu Sun, Hongjin He. A structured trust region method for nonconvex programming with separable structure. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 283-293. doi: 10.3934/naco.2013.3.283

[10]

Xin Yang, Nan Wang, Lingling Xu. A parallel Gauss-Seidel method for convex problems with separable structure. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 557-570. doi: 10.3934/naco.2020051

[11]

Xueyong Wang, Yiju Wang, Gang Wang. An accelerated augmented Lagrangian method for multi-criteria optimization problem. Journal of Industrial and Management Optimization, 2020, 16 (1) : 1-9. doi: 10.3934/jimo.2018136

[12]

Chunlin Wu, Juyong Zhang, Xue-Cheng Tai. Augmented Lagrangian method for total variation restoration with non-quadratic fidelity. Inverse Problems and Imaging, 2011, 5 (1) : 237-261. doi: 10.3934/ipi.2011.5.237

[13]

Fatemeh Bazikar, Saeed Ketabchi, Hossein Moosaei. Smooth augmented Lagrangian method for twin bounded support vector machine. Numerical Algebra, Control and Optimization, 2021  doi: 10.3934/naco.2021027

[14]

Suxiang He, Pan Zhang, Xiao Hu, Rong Hu. A sample average approximation method based on a D-gap function for stochastic variational inequality problems. Journal of Industrial and Management Optimization, 2014, 10 (3) : 977-987. doi: 10.3934/jimo.2014.10.977

[15]

Wei Zhu. A numerical study of a mean curvature denoising model using a novel augmented Lagrangian method. Inverse Problems and Imaging, 2017, 11 (6) : 975-996. doi: 10.3934/ipi.2017045

[16]

Qingsong Duan, Mengwei Xu, Yue Lu, Liwei Zhang. A smoothing augmented Lagrangian method for nonconvex, nonsmooth constrained programs and its applications to bilevel problems. Journal of Industrial and Management Optimization, 2019, 15 (3) : 1241-1261. doi: 10.3934/jimo.2018094

[17]

Li Wang, Yang Li, Liwei Zhang. A differential equation method for solving box constrained variational inequality problems. Journal of Industrial and Management Optimization, 2011, 7 (1) : 183-198. doi: 10.3934/jimo.2011.7.183

[18]

Hui-Qiang Ma, Nan-Jing Huang. Neural network smoothing approximation method for stochastic variational inequality problems. Journal of Industrial and Management Optimization, 2015, 11 (2) : 645-660. doi: 10.3934/jimo.2015.11.645

[19]

Ming Chen, Chongchao Huang. A power penalty method for a class of linearly constrained variational inequality. Journal of Industrial and Management Optimization, 2018, 14 (4) : 1381-1396. doi: 10.3934/jimo.2018012

[20]

Walter Allegretto, Yanping Lin, Shuqing Ma. On the box method for a non-local parabolic variational inequality. Discrete and Continuous Dynamical Systems - B, 2001, 1 (1) : 71-88. doi: 10.3934/dcdsb.2001.1.71

 Impact Factor: 

Metrics

  • PDF downloads (141)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]