A nonmonotone smoothing Newton algorithm for solving box constrained variational inequalitieswith a $P_0$ function

Na Zhao; Zheng-Hai Huang

doi:10.3934/jimo.2011.7.467

Article Contents

2011, Volume 7, Issue 2: 467-482. Doi: 10.3934/jimo.2011.7.467

This issue Previous Article Overbooking with transference option for flights Next Article Optimality conditions for approximate solutions of vector optimization problems

A nonmonotone smoothing Newton algorithm for solving box constrained variational inequalities with a $P_0$ function

Na Zhao^1, and
Zheng-Hai Huang^2,

1.
College of Science, Civil Aviation University of China, Tianjin 300300
2.
Department of Mathematics, School of Science, Tianjin University, Tianjin 300072

Received: February 28, 2010

Revised: January 31, 2011

Published: March 2011

Abstract Related Papers Cited by

Abstract

In this paper, we propose a new class of smoothing functions which uniformly approximates the median function of three scalars. The proposed functions are the generalization of the smoothing function proposed by Li and Fukushima. Some favorable properties of the functions are investigated. By using the proposed functions, we reformulate the box constrained variational inequality problem (VIP) as a system of parameterized smooth equations, and then propose a smoothing Newton algorithm with a nonmonotone line search to solve the VIP. The proposed algorithm is proved to be globally and locally superlinearly convergent under suitable assumptions. Some numerical results for test problems from MCPLIB are also reported, which demonstrate that the proposed smoothing functions are valuable and the proposed algorithm is effective.

Keywords:

Box constrained variational inequality problem,
smoothing Newton method,
smoothing function,
nonmonotone line search.

Mathematics Subject Classification: Primary: 90C33; Secondary: 65K10.

Citation:

Related Papers

Cited by

References

[1]	S. C. Billups, S. P. Dirkse and M. C. Soares, A comparison of algorithms for large scale mixed complementarity problems, Comput. Optim. Appl., 7 (1997), 3-25.doi: 10.1023/A:1008632215341.
[2]	B. Chen and X. Chen, A global linear and local quadratic continuation smoothing method for variational inequalities with box constraints, Comput. Optim. Appl., 13 (2000), 131-158.doi: 10.1023/A:1026546230851.
[3]	C. Chen and O. L. Mangasarian, A class of smoothing functions for nonlinear and mixed complementarity problems, Comput. Optim. Appl., 5 (1996), 97-138.doi: 10.1007/BF00249052.
[4]	J.-S. Chen, The semismooth-related properties of a merit function and a descent method for the nonlinear complementarity problem, J. Global Optim., 36 (2006), 565-580.doi: 10.1007/s10898-006-9027-y.
[5]	J.-S. Chen and P. H. Pan, A family of NCP functions and a descent method for the nonlinear complementarity problem, Comput. Optim. Appl., 40 (2008), 389-404.doi: 10.1007/s10589-007-9086-0.
[6]	J.-S. Chen, S. H. Pan and T. C. Lin, A smoothing Newton method based on the generalized Fischer-Burmeister function for MCPs, Nonlinear Anal.: TMA, 72 (2010), 3739-3758.doi: 10.1016/j.na.2010.01.012.
[7]	J.-S. Chen, S. H. Pan and C. Y. Yang, Numerical comparisons of two effective method for mixed complementarity problems, J. Comput. Appl. Math., 234 (2010), 667-683.doi: 10.1016/j.cam.2010.01.004.
[8]	X. Chen, L. Qi and D. Sun, Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities, Math. Comput., 67 (1998), 519-540.doi: 10.1090/S0025-5718-98-00932-6.
[9]	X. Chen and Y. Ye, On homotopy-smoothing methods for box-constrained variational inequalities, SIAM J. Control Optim., 37 (1999), 589-616.doi: 10.1137/S0363012997315907.
[10]	F. Facchinei, A. Fischer and C. Kanzow, A semismooth Newton method for variational inequalities: The case of box constraints, in "Complementarity and Variational Problems: State of the Art" (eds. M. C. Ferris and J. S. Pang), SIAM: Philadelphia, (1997), 76-90.
[11]	M. Ferris, C. Kanzow and T. S. Munson, Feasible descent algorithms for mixed complentarity problems, Math. Program., 86 (1999), 475-497.doi: 10.1007/s101070050101.
[12]	A. Fischer, Solution of monotone complementarity problems with Lipschitzian functions, Math. Program., 76 (1997), 513-532.doi: 10.1007/BF02614396.
[13]	M. S. Gowda and J. J. Sznajder, Weak univalence and connectedness of inverse images of continuous functions, Math. Oper. Res., 24 (1999), 255-261.doi: 10.1287/moor.24.1.255.
[14]	M. S. Gowda and M. A. Tawhid, Existence and limiting behavior of trajectories associated with $P_0$-equations, Comput. Optim. Appl., 12 (1999), 229-251.doi: 10.1023/A:1008688302346.
[15]	S. L. Hu and Z. H. Huang, Smoothness of a class of generalized merit functions for the second-order cone complementarity problem, Pacific J. Optim., 6 (2010), 551-571.
[16]	S. L. Hu, Z. H. Huang and J.-S. Chen, Properties of a family of generalized NCP-functions and a derivative free algorithm for complementarity problems, J. Comput. Appl. Math., 230 (2009), 69-82.doi: 10.1016/j.cam.2008.10.056.
[17]	S. L. Hu, Z. H. Huang and N. Lu, A non-monotone line search algorithm for unconstrained optimization, J. Sci. Comput., 42 (2010), 38-53.doi: 10.1007/s10915-009-9314-0.
[18]	S. L. Hu, Z.H. Huang and P. Wang, A nonmonotone smoothing Newton algorithm for solving nonlinear complementarity problems, Optim. Methods Softw., 24 (2009), 447-460.doi: 10.1080/10556780902769862.
[19]	Z. H. Huang, L. Qi and D. Sun, Sub-quadratic convergence of a smoothing Newton algorithm for the $P_0$- and monotone LCP, Math. Program., 99 (2004), 423-441.doi: 10.1007/s10107-003-0457-8.
[20]	C. Kanzow and M. Fukushima, Theoretical and numerical investigation of the D-gap function for box constrained variational inequalities, Math. Program., 83 (1998), 55-87.doi: 10.1007/BF02680550.
[21]	C. Kanzow and S. Petra, Projected filter trust region methods for a semismooth least squares formulation of mixed complementarity problems, Optim. Methods Softw., 22 (2007), 713-735.doi: 10.1080/10556780701296455.
[22]	D. Li and M. Fukushima, Smoothing Newton and quasi-Newton methods for mixed complementarity problems, Comput. Optim. Appl., 17 (2000), 203-230.doi: 10.1023/A:1026502415830.
[23]	J. M. Peng, C. Kanzow and M. Fukushima, A hybrid Josephy-Newton method for solving box constrained variational inequality problems via the D-gap function, Optim. Methods Softw., 10 (1999), 687-710.doi: 10.1080/10556789908805734.
[24]	H. D. Qi, A regularized smoothing Newton method for box constrained variational inequality problems with $P_0$-functions, SIAM J. Optim., 10 (2000), 315-330.doi: 10.1137/S1052623497324047.
[25]	L. Qi, D. Sun and G. Zhou, A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequality problems, Math. Program., 87 (2000), 1-35.
[26]	L. Qi and J. Sun, A nonsmooth version of Newton's method, Math. Program., 58 (1993), 353-367.doi: 10.1007/BF01581275.
[27]	G. Ravindran and M. S. Gowda, Regularization of $P_0$-functions in box variational inequality problems, SIAM J. Optim., 11 (2001), 748-760.doi: 10.1137/S1052623497329567.
[28]	D. Sun and R. S. Womersley, A new unconstrained differentiable merit function for box constrained variational inequality problems and a damped Guass-Newton method, SIAM J. Optim., 9 (1999), 388-413.doi: 10.1137/S1052623496314173.