American Institute of Mathematical Sciences

Advanced
April  2014, 10(2): 461-476. doi: 10.3934/jimo.2014.10.461

A new parallel splitting descent method for structured variational inequalities

Kai Wang 1, , Lingling Xu 1, and  Deren Han 2,

1. 

School of Mathematical Sciences, Jiangsu Key Laboratory for NSLSCS, Nanjing Normal University, Nanjing 210023, China, China
2. 

School of Mathematical Sciences, Jiangsu Key Labratory for NSLSCS, Nanjing Normal University, Nanjing, 210023

Received  October 2012 Revised  August 2013 Published  October 2013

In this paper, we propose a new parallel splitting descent method for solving a class of variational inequalities with separable structure. The new method can be applied to solve convex optimization problems in which the objective function is separable with three operators and the constraint is linear. In the framework of the new algorithm, we adopt a new descent strategy by combining two descent directions and resolve the descent direction which is different from the methods in He (Comput. Optim. Appl., 2009, 42: 195-212.) and Wang et al. (submitted to J. Optimiz. Theory App.). Theoretically, we establish the global convergence of the new method under mild assumptions. In addition, we apply the new method to solve problems in management science and traffic equilibrium problem. Numerical results indicate that the new method is efficient and reliable.
Keywords: variational inequalities, Alternating direction method, parallel computing, augmented Lagrangian method, separable structure..
Mathematics Subject Classification: Primary: 49M27, 65K15, 93B4.
Citation: Kai Wang, Lingling Xu, Deren Han. A new parallel splitting descent method for structured variational inequalities. Journal of Industrial & Management Optimization, 2014, 10 (2) : 461-476. doi: 10.3934/jimo.2014.10.461
References:
[1]

D. P. Bertsekas and E. M. Gafni, Projection methods for variational inequalities with application to the traffic assignment problem, in Nondifferential and Variational Techniques in Optimization, Math. Program. Stud., 17, Springer, Berlin-Heidelberg, 1982, 139-159.  Google Scholar

[2]

D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Compution, Numerical Methods, Prentice-Hall, Englewood Cliffs, 1989. Google Scholar

[3]

M. D'Apuzzo, M. Marino, A. Migdalas, P. M. Pardalos and G. Toraldo, Parallel computing in global optimization, in Handbook of Parallel Computing and Statistics (eds. E. J. Kontoghiorghes), Stat. Textb. Monogr., 184, Chapman & Hall/CRC, Boca Raton, FL, 2006, 225-258. doi: 10.1201/9781420028683.ch7.  Google Scholar

[4]

J. Eckstein, Some saddle-function splitting methods for convex programming, Optimization Methods Software, 4 (1994), 75-83. doi: 10.1080/10556789408805578.  Google Scholar

[5]

J. Eckstein and M. Fukushima, Some reformulation and applications of the alternating direction method of multipliers, in Large Scale Optimization (Gainesville, FL, 1993), Kluwer Academic Publ., Dordoecht, 1994, 115-134.  Google Scholar

[6]

F. Facchinei and J. S. Pang, Finite-dimensional Variational Inequalities and Complementarity Problems, Springer, New York, 2003. Google Scholar

[7]

M. C. Ferris and J. S. Pang, Engineering and economic applications of comlementarity problems, SIAM Review, 39 (1997), 669-713. doi: 10.1137/S0036144595285963.  Google Scholar

[8]

M. Fukushima, Application of the alternating direction method of multipliers to separable convex programming problems, Comput. Optim. Appl., 1 (1992), 93-111. doi: 10.1007/BF00247655.  Google Scholar

[9]

D. Gabay, Applications of the method of multipliers to variational inequalities, in Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Valued Problems (eds. M. Fortin and R. Glowinski), Studies in Mathematics and Its Applications, 15, Amsterdam, The Netherlands, 1983, 299-331. doi: 10.1016/S0168-2024(08)70034-1.  Google Scholar

[10]

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

[11]

R. Glowinski, Numerical Methods for Nonlinear Variational Problems, Springer-Verlag, New York, 1984.  Google Scholar

[12]

R. Glowinski and P. Le Tallec, Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics, SIAM Studies in Applied Mathematics, 9, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1989. doi: 10.1137/1.9781611970838.  Google Scholar

[13]

D. R. Han, X. M. Yuan and W. X. Zhang, An augmented-Lagrangian-based parallel splitting method for separable convex programming with applications to image processing,, manuscript., ().   Google Scholar

[14]

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

[15]

B.-S. He, Parallel splitting augmented Lagrangian methods for monotone structured variational inequalities, Comput. Optim. Appl., 42 (2009), 195-212. doi: 10.1007/s10589-007-9109-x.  Google Scholar

[16]

B.-S. He, L. Z. Liao, H. Yang and D. R. Han, A new inexact alternating directions method for monotone variational inequalities, Math. Program., 92 (2002), 103-118. doi: 10.1007/s101070100280.  Google Scholar

[17]

B.-S. He and L. Z. Liao, Improvements of some projection methods for monotone nonlinear variational inequalities, J. Optim. Theory Appl., 112 (2002), 111-128. doi: 10.1023/A:1013096613105.  Google Scholar

[18]

B.-S. He, Y. Xu and X.-M. Yuan, A logarithmic-quadratic proximal prediction-correction method for structured monotone variational inequalities, Comput. Optim. Appl., 35 (2006), 19-46. doi: 10.1007/s10589-006-6442-4.  Google Scholar

[19]

B.-S. He, H. Yang and S. L. Wang, Altermating direction method with self-adaptive penalty parameters for monotone variational inequalities, J. Optim. Theory Appl., 106 (2000), 337-356. doi: 10.1023/A:1004603514434.  Google Scholar

[20]

B.-S. He, M. Tao and X.-M. Yuan, Alternating direction method with Gaussian back substitution for separable convex programming, SIAM J. Optim., 22 (2012), 313-340. doi: 10.1137/110822347.  Google Scholar

[21]

B.-S. He, M. Tao, M. H. Xu and X.-M. Yuan, Alternating directions based contraction method for generally separable linearly constrained convex programming problems, manuscript, 2009. Available from: http://www.optimization-online.org/DB_HTML/2009/11/2465.html. Google Scholar

[22]

Z. K. Jiang and X. M. Yuan, New parallel descent-like method for sloving a class of variational inequalities, J. Optim. Theory Appl., 145 (2010), 311-323. doi: 10.1007/s10957-009-9619-z.  Google Scholar

[23]

D. Kinderlehrer and G. Stampacchia, An Introduction to Variational Inequalities and Their Application, Pure and Applied Mathematics, 88, Academic Press, Inc., New York-London, 1980.  Google Scholar

[24]

A. Migdalas, P. M. Pardalos and S. Storøy, eds., Parallel Computing in Optimization, Applied Optimization, 7, Kluwer Academic Publishers, Dordrecht, 1997.  Google Scholar

[25]

A. Migdalas, G. Toraldo and V. Kumar, Nonlinear optimization and parallel computing, Parallel Computing, 29 (2003), 375-391. doi: 10.1016/S0167-8191(03)00013-9.  Google Scholar

[26]

A. Nagurney and D. Zhang, Projected Dynamical Systems and Variational Inequalities with Applications, International Series in Operations Research & Management Science, Vol. 2, Kluwer Academic Publishers, 1996. doi: 10.1007/978-1-4615-2301-7.  Google Scholar

[27]

P. M. Pardalos and S. Rajasekaran, eds., Advances in Randomized Parallel Computing, Kluwer Academic Publishers, Dordrecht, 1999. doi: 10.1007/978-1-4613-3282-4.  Google Scholar

[28]

J. Sun and S. Zhang, A modified alternating direction method for convex quadratically constrained quadratic semidefinite programs, European J. Oper. Res., 207 (2010), 1210-1220. doi: 10.1016/j.ejor.2010.07.020.  Google Scholar

[29]

K. Wang, D. R. Han and L. L. Xu, A parallel splitting method for separable convex programming, J. Optim. Theory Appl., 159 (2013), 138-158. doi: 10.1007/s10957-013-0277-9.  Google Scholar

show all references

References:
[1]

D. P. Bertsekas and E. M. Gafni, Projection methods for variational inequalities with application to the traffic assignment problem, in Nondifferential and Variational Techniques in Optimization, Math. Program. Stud., 17, Springer, Berlin-Heidelberg, 1982, 139-159.  Google Scholar

[2]

D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Compution, Numerical Methods, Prentice-Hall, Englewood Cliffs, 1989. Google Scholar

[3]

M. D'Apuzzo, M. Marino, A. Migdalas, P. M. Pardalos and G. Toraldo, Parallel computing in global optimization, in Handbook of Parallel Computing and Statistics (eds. E. J. Kontoghiorghes), Stat. Textb. Monogr., 184, Chapman & Hall/CRC, Boca Raton, FL, 2006, 225-258. doi: 10.1201/9781420028683.ch7.  Google Scholar

[4]

J. Eckstein, Some saddle-function splitting methods for convex programming, Optimization Methods Software, 4 (1994), 75-83. doi: 10.1080/10556789408805578.  Google Scholar

[5]

J. Eckstein and M. Fukushima, Some reformulation and applications of the alternating direction method of multipliers, in Large Scale Optimization (Gainesville, FL, 1993), Kluwer Academic Publ., Dordoecht, 1994, 115-134.  Google Scholar

[6]

F. Facchinei and J. S. Pang, Finite-dimensional Variational Inequalities and Complementarity Problems, Springer, New York, 2003. Google Scholar

[7]

M. C. Ferris and J. S. Pang, Engineering and economic applications of comlementarity problems, SIAM Review, 39 (1997), 669-713. doi: 10.1137/S0036144595285963.  Google Scholar

[8]

M. Fukushima, Application of the alternating direction method of multipliers to separable convex programming problems, Comput. Optim. Appl., 1 (1992), 93-111. doi: 10.1007/BF00247655.  Google Scholar

[9]

D. Gabay, Applications of the method of multipliers to variational inequalities, in Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Valued Problems (eds. M. Fortin and R. Glowinski), Studies in Mathematics and Its Applications, 15, Amsterdam, The Netherlands, 1983, 299-331. doi: 10.1016/S0168-2024(08)70034-1.  Google Scholar

[10]

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

[11]

R. Glowinski, Numerical Methods for Nonlinear Variational Problems, Springer-Verlag, New York, 1984.  Google Scholar

[12]

R. Glowinski and P. Le Tallec, Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics, SIAM Studies in Applied Mathematics, 9, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1989. doi: 10.1137/1.9781611970838.  Google Scholar

[13]

D. R. Han, X. M. Yuan and W. X. Zhang, An augmented-Lagrangian-based parallel splitting method for separable convex programming with applications to image processing,, manuscript., ().   Google Scholar

[14]

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

[15]

B.-S. He, Parallel splitting augmented Lagrangian methods for monotone structured variational inequalities, Comput. Optim. Appl., 42 (2009), 195-212. doi: 10.1007/s10589-007-9109-x.  Google Scholar

[16]

B.-S. He, L. Z. Liao, H. Yang and D. R. Han, A new inexact alternating directions method for monotone variational inequalities, Math. Program., 92 (2002), 103-118. doi: 10.1007/s101070100280.  Google Scholar

[17]

B.-S. He and L. Z. Liao, Improvements of some projection methods for monotone nonlinear variational inequalities, J. Optim. Theory Appl., 112 (2002), 111-128. doi: 10.1023/A:1013096613105.  Google Scholar

[18]

B.-S. He, Y. Xu and X.-M. Yuan, A logarithmic-quadratic proximal prediction-correction method for structured monotone variational inequalities, Comput. Optim. Appl., 35 (2006), 19-46. doi: 10.1007/s10589-006-6442-4.  Google Scholar

[19]

B.-S. He, H. Yang and S. L. Wang, Altermating direction method with self-adaptive penalty parameters for monotone variational inequalities, J. Optim. Theory Appl., 106 (2000), 337-356. doi: 10.1023/A:1004603514434.  Google Scholar

[20]

B.-S. He, M. Tao and X.-M. Yuan, Alternating direction method with Gaussian back substitution for separable convex programming, SIAM J. Optim., 22 (2012), 313-340. doi: 10.1137/110822347.  Google Scholar

[21]

B.-S. He, M. Tao, M. H. Xu and X.-M. Yuan, Alternating directions based contraction method for generally separable linearly constrained convex programming problems, manuscript, 2009. Available from: http://www.optimization-online.org/DB_HTML/2009/11/2465.html. Google Scholar

[22]

Z. K. Jiang and X. M. Yuan, New parallel descent-like method for sloving a class of variational inequalities, J. Optim. Theory Appl., 145 (2010), 311-323. doi: 10.1007/s10957-009-9619-z.  Google Scholar

[23]

D. Kinderlehrer and G. Stampacchia, An Introduction to Variational Inequalities and Their Application, Pure and Applied Mathematics, 88, Academic Press, Inc., New York-London, 1980.  Google Scholar

[24]

A. Migdalas, P. M. Pardalos and S. Storøy, eds., Parallel Computing in Optimization, Applied Optimization, 7, Kluwer Academic Publishers, Dordrecht, 1997.  Google Scholar

[25]

A. Migdalas, G. Toraldo and V. Kumar, Nonlinear optimization and parallel computing, Parallel Computing, 29 (2003), 375-391. doi: 10.1016/S0167-8191(03)00013-9.  Google Scholar

[26]

A. Nagurney and D. Zhang, Projected Dynamical Systems and Variational Inequalities with Applications, International Series in Operations Research & Management Science, Vol. 2, Kluwer Academic Publishers, 1996. doi: 10.1007/978-1-4615-2301-7.  Google Scholar

[27]

P. M. Pardalos and S. Rajasekaran, eds., Advances in Randomized Parallel Computing, Kluwer Academic Publishers, Dordrecht, 1999. doi: 10.1007/978-1-4613-3282-4.  Google Scholar

[28]

J. Sun and S. Zhang, A modified alternating direction method for convex quadratically constrained quadratic semidefinite programs, European J. Oper. Res., 207 (2010), 1210-1220. doi: 10.1016/j.ejor.2010.07.020.  Google Scholar

[29]

K. Wang, D. R. Han and L. L. Xu, A parallel splitting method for separable convex programming, J. Optim. Theory Appl., 159 (2013), 138-158. doi: 10.1007/s10957-013-0277-9.  Google Scholar

[1]

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

Xi-Hong Yan. A new convergence proof of augmented Lagrangian-based method with full Jacobian decomposition for structured variational inequalities. Numerical Algebra, Control & Optimization, 2016, 6 (1) : 45-54. doi: 10.3934/naco.2016.6.45
[3]

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
[4]

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

Russell E. Warren, Stanley J. Osher. Hyperspectral unmixing by the alternating direction method of multipliers. Inverse Problems & Imaging, 2015, 9 (3) : 917-933. doi: 10.3934/ipi.2015.9.917
[6]

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 & Imaging, 2019, 13 (2) : 309-335. doi: 10.3934/ipi.2019016
[7]

Sohana Jahan. Supervised distance preserving projection using alternating direction method of multipliers. Journal of Industrial & Management Optimization, 2020, 16 (4) : 1783-1799. doi: 10.3934/jimo.2019029
[8]

Jie-Wen He, Chi-Chon Lei, Chen-Yang Shi, Seak-Weng Vong. An inexact alternating direction method of multipliers for a kind of nonlinear complementarity problems. Numerical Algebra, Control & Optimization, 2021, 11 (3) : 353-362. doi: 10.3934/naco.2020030
[9]

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
[10]

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

Hongxia Yin. An iterative method for general variational inequalities. Journal of Industrial & Management Optimization, 2005, 1 (2) : 201-209. doi: 10.3934/jimo.2005.1.201
[12]

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

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

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

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

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

Yuan Shen, Lei Ji. Partial convolution for total variation deblurring and denoising by new linearized alternating direction method of multipliers with extension step. Journal of Industrial & Management Optimization, 2019, 15 (1) : 159-175. doi: 10.3934/jimo.2018037
[18]

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, 2021, 17 (3) : 1173-1185. doi: 10.3934/jimo.2020016
[19]

Yue Lu, Ying-En Ge, Li-Wei Zhang. An alternating direction method for solving a class of inverse semi-definite quadratic programming problems. Journal of Industrial & Management Optimization, 2016, 12 (1) : 317-336. doi: 10.3934/jimo.2016.12.317
[20]

Yan Gu, Nobuo Yamashita. Alternating direction method of multipliers with variable metric indefinite proximal terms for convex optimization. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 487-510. doi: 10.3934/naco.2020047

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (54)
  • HTML views (0)
  • Cited by (7)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy