American Institute of Mathematical Sciences

Advanced
April  2011, 7(2): 467-482. doi: 10.3934/jimo.2011.7.467

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, China
2. 

Department of Mathematics, School of Science, Tianjin University, Tianjin 300072

Received  March 2010 Revised  February 2011 Published  April 2011

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: smoothing function, Box constrained variational inequality problem, smoothing Newton method, nonmonotone line search..
Mathematics Subject Classification: Primary: 90C33; Secondary: 65K1.
Citation: Na Zhao, Zheng-Hai Huang. A nonmonotone smoothing Newton algorithm for solving box constrained variational inequalities with a $P_0$ function. Journal of Industrial & Management Optimization, 2011, 7 (2) : 467-482. doi: 10.3934/jimo.2011.7.467
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.  doi: 10.1023/A:1008632215341.  Google Scholar

[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.  doi: 10.1023/A:1026546230851.  Google Scholar

[3]

C. Chen and O. L. Mangasarian, A class of smoothing functions for nonlinear and mixed complementarity problems,, Comput. Optim. Appl., 5 (1996), 97.  doi: 10.1007/BF00249052.  Google Scholar

[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.  doi: 10.1007/s10898-006-9027-y.  Google Scholar

[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.  doi: 10.1007/s10589-007-9086-0.  Google Scholar

[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.  doi: 10.1016/j.na.2010.01.012.  Google Scholar

[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.  doi: 10.1016/j.cam.2010.01.004.  Google Scholar

[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.  doi: 10.1090/S0025-5718-98-00932-6.  Google Scholar

[9]

X. Chen and Y. Ye, On homotopy-smoothing methods for box-constrained variational inequalities,, SIAM J. Control Optim., 37 (1999), 589.  doi: 10.1137/S0363012997315907.  Google Scholar

[10]

F. Facchinei, A. Fischer and C. Kanzow, A semismooth Newton method for variational inequalities: The case of box constraints,, in, (1997), 76.   Google Scholar

[11]

M. Ferris, C. Kanzow and T. S. Munson, Feasible descent algorithms for mixed complentarity problems,, Math. Program., 86 (1999), 475.  doi: 10.1007/s101070050101.  Google Scholar

[12]

A. Fischer, Solution of monotone complementarity problems with Lipschitzian functions,, Math. Program., 76 (1997), 513.  doi: 10.1007/BF02614396.  Google Scholar

[13]

M. S. Gowda and J. J. Sznajder, Weak univalence and connectedness of inverse images of continuous functions,, Math. Oper. Res., 24 (1999), 255.  doi: 10.1287/moor.24.1.255.  Google Scholar

[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.  doi: 10.1023/A:1008688302346.  Google Scholar

[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.   Google Scholar

[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.  doi: 10.1016/j.cam.2008.10.056.  Google Scholar

[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.  doi: 10.1007/s10915-009-9314-0.  Google Scholar

[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.  doi: 10.1080/10556780902769862.  Google Scholar

[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.  doi: 10.1007/s10107-003-0457-8.  Google Scholar

[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.  doi: 10.1007/BF02680550.  Google Scholar

[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.  doi: 10.1080/10556780701296455.  Google Scholar

[22]

D. Li and M. Fukushima, Smoothing Newton and quasi-Newton methods for mixed complementarity problems,, Comput. Optim. Appl., 17 (2000), 203.  doi: 10.1023/A:1026502415830.  Google Scholar

[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.  doi: 10.1080/10556789908805734.  Google Scholar

[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.  doi: 10.1137/S1052623497324047.  Google Scholar

[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.   Google Scholar

[26]

L. Qi and J. Sun, A nonsmooth version of Newton's method,, Math. Program., 58 (1993), 353.  doi: 10.1007/BF01581275.  Google Scholar

[27]

G. Ravindran and M. S. Gowda, Regularization of $P_0$-functions in box variational inequality problems,, SIAM J. Optim., 11 (2001), 748.  doi: 10.1137/S1052623497329567.  Google Scholar

[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.  doi: 10.1137/S1052623496314173.  Google Scholar

show all references

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.  doi: 10.1023/A:1008632215341.  Google Scholar

[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.  doi: 10.1023/A:1026546230851.  Google Scholar

[3]

C. Chen and O. L. Mangasarian, A class of smoothing functions for nonlinear and mixed complementarity problems,, Comput. Optim. Appl., 5 (1996), 97.  doi: 10.1007/BF00249052.  Google Scholar

[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.  doi: 10.1007/s10898-006-9027-y.  Google Scholar

[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.  doi: 10.1007/s10589-007-9086-0.  Google Scholar

[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.  doi: 10.1016/j.na.2010.01.012.  Google Scholar

[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.  doi: 10.1016/j.cam.2010.01.004.  Google Scholar

[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.  doi: 10.1090/S0025-5718-98-00932-6.  Google Scholar

[9]

X. Chen and Y. Ye, On homotopy-smoothing methods for box-constrained variational inequalities,, SIAM J. Control Optim., 37 (1999), 589.  doi: 10.1137/S0363012997315907.  Google Scholar

[10]

F. Facchinei, A. Fischer and C. Kanzow, A semismooth Newton method for variational inequalities: The case of box constraints,, in, (1997), 76.   Google Scholar

[11]

M. Ferris, C. Kanzow and T. S. Munson, Feasible descent algorithms for mixed complentarity problems,, Math. Program., 86 (1999), 475.  doi: 10.1007/s101070050101.  Google Scholar

[12]

A. Fischer, Solution of monotone complementarity problems with Lipschitzian functions,, Math. Program., 76 (1997), 513.  doi: 10.1007/BF02614396.  Google Scholar

[13]

M. S. Gowda and J. J. Sznajder, Weak univalence and connectedness of inverse images of continuous functions,, Math. Oper. Res., 24 (1999), 255.  doi: 10.1287/moor.24.1.255.  Google Scholar

[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.  doi: 10.1023/A:1008688302346.  Google Scholar

[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.   Google Scholar

[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.  doi: 10.1016/j.cam.2008.10.056.  Google Scholar

[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.  doi: 10.1007/s10915-009-9314-0.  Google Scholar

[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.  doi: 10.1080/10556780902769862.  Google Scholar

[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.  doi: 10.1007/s10107-003-0457-8.  Google Scholar

[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.  doi: 10.1007/BF02680550.  Google Scholar

[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.  doi: 10.1080/10556780701296455.  Google Scholar

[22]

D. Li and M. Fukushima, Smoothing Newton and quasi-Newton methods for mixed complementarity problems,, Comput. Optim. Appl., 17 (2000), 203.  doi: 10.1023/A:1026502415830.  Google Scholar

[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.  doi: 10.1080/10556789908805734.  Google Scholar

[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.  doi: 10.1137/S1052623497324047.  Google Scholar

[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.   Google Scholar

[26]

L. Qi and J. Sun, A nonsmooth version of Newton's method,, Math. Program., 58 (1993), 353.  doi: 10.1007/BF01581275.  Google Scholar

[27]

G. Ravindran and M. S. Gowda, Regularization of $P_0$-functions in box variational inequality problems,, SIAM J. Optim., 11 (2001), 748.  doi: 10.1137/S1052623497329567.  Google Scholar

[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.  doi: 10.1137/S1052623496314173.  Google Scholar

[1]

Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028
[2]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271
[3]

Min Li. A three term Polak-Ribière-Polyak conjugate gradient method close to the memoryless BFGS quasi-Newton method. Journal of Industrial & Management Optimization, 2020, 16 (1) : 245-260. doi: 10.3934/jimo.2018149
[4]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056
[5]

Sergi Simon. Linearised higher variational equations. Discrete & Continuous Dynamical Systems - A, 2014, 34 (11) : 4827-4854. doi: 10.3934/dcds.2014.34.4827
[6]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[7]

Xue-Ping Luo, Yi-Bin Xiao, Wei Li. Strict feasibility of variational inclusion problems in reflexive Banach spaces. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2495-2502. doi: 10.3934/jimo.2019065
[8]

Livia Betz, Irwin Yousept. Optimal control of elliptic variational inequalities with bounded and unbounded operators. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021009
[9]

Sara Munday. On the derivative of the $\alpha$-Farey-Minkowski function. Discrete & Continuous Dynamical Systems - A, 2014, 34 (2) : 709-732. doi: 10.3934/dcds.2014.34.709
[10]

Haibo Cui, Haiyan Yin. Convergence rate of solutions toward stationary solutions to the isentropic micropolar fluid model in a half line. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020210
[11]

Ademir Fernando Pazoto, Lionel Rosier. Uniform stabilization in weighted Sobolev spaces for the KdV equation posed on the half-line. Discrete & Continuous Dynamical Systems - B, 2010, 14 (4) : 1511-1535. doi: 10.3934/dcdsb.2010.14.1511
[12]

Ralf Hielscher, Michael Quellmalz. Reconstructing a function on the sphere from its means along vertical slices. Inverse Problems & Imaging, 2016, 10 (3) : 711-739. doi: 10.3934/ipi.2016018
[13]

Enkhbat Rentsen, Battur Gompil. Generalized Nash equilibrium problem based on malfatti's problem. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 209-220. doi: 10.3934/naco.2020022
[14]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021
[15]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327
[16]

Hildeberto E. Cabral, Zhihong Xia. Subharmonic solutions in the restricted three-body problem. Discrete & Continuous Dynamical Systems - A, 1995, 1 (4) : 463-474. doi: 10.3934/dcds.1995.1.463
[17]

Charles Fulton, David Pearson, Steven Pruess. Characterization of the spectral density function for a one-sided tridiagonal Jacobi matrix operator. Conference Publications, 2013, 2013 (special) : 247-257. doi: 10.3934/proc.2013.2013.247
[18]

Dayalal Suthar, Sunil Dutt Purohit, Haile Habenom, Jagdev Singh. Class of integrals and applications of fractional kinetic equation with the generalized multi-index Bessel function. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021019
[19]

Saima Rashid, Fahd Jarad, Zakia Hammouch. Some new bounds analogous to generalized proportional fractional integral operator with respect to another function. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021020
[20]

Davide La Torre, Simone Marsiglio, Franklin Mendivil, Fabio Privileggi. Public debt dynamics under ambiguity by means of iterated function systems on density functions. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021070

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (34)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences