A new parallel splitting descent method for structured variational inequalities

Kai Wang; Lingling Xu; Deren Han

doi:10.3934/jimo.2014.10.461

Article Contents

2014, Volume 10, Issue 2: 461-476. Doi: 10.3934/jimo.2014.10.461

This issue Previous Article Computation of bang-bang and singular controls in collision avoidance Next Article Designing rendezvous missions with mini-moons using geometric optimal control

A new parallel splitting descent method for structured variational inequalities

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

Received: September 30, 2012

Revised: July 31, 2013

Published: March 2014

Abstract Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 49M27, 65K15, 93B40.

Citation:

Related Papers

Cited by

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.
[2]	D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Compution, Numerical Methods, Prentice-Hall, Englewood Cliffs, 1989.
[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.
[4]	J. Eckstein, Some saddle-function splitting methods for convex programming, Optimization Methods Software, 4 (1994), 75-83.doi: 10.1080/10556789408805578.
[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.
[6]	F. Facchinei and J. S. Pang, Finite-dimensional Variational Inequalities and Complementarity Problems, Springer, New York, 2003.
[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.
[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.
[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.
[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.
[11]	R. Glowinski, Numerical Methods for Nonlinear Variational Problems, Springer-Verlag, New York, 1984.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[24]	A. Migdalas, P. M. Pardalos and S. Storøy, eds., Parallel Computing in Optimization, Applied Optimization, 7, Kluwer Academic Publishers, Dordrecht, 1997.
[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.
[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.
[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.
[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.
[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.