A nonmonotone smoothing Newton algorithm for solving box constrained variational inequalities with a P

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

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

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

Abstract
Related Papers

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]	Li Wang, Yang Li, Liwei Zhang. A differential equation method for solving box constrained variational inequality problems. Journal of Industrial & Management Optimization, 2011, 7 (1) : 183-198. doi: 10.3934/jimo.2011.7.183
[2]	Hui-Qiang Ma, Nan-Jing Huang. Neural network smoothing approximation method for stochastic variational inequality problems. Journal of Industrial & Management Optimization, 2015, 11 (2) : 645-660. doi: 10.3934/jimo.2015.11.645
[3]	Yafeng Li, Guo Sun, Yiju Wang. A smoothing Broyden-like method for polyhedral cone constrained eigenvalue problem. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 529-537. doi: 10.3934/naco.2011.1.529
[4]	Ahmet Sahiner, Gulden Kapusuz, Nurullah Yilmaz. A new smoothing approach to exact penalty functions for inequality constrained optimization problems. Numerical Algebra, Control & Optimization, 2016, 6 (2) : 161-173. doi: 10.3934/naco.2016006
[5]	Xiaojiao Tong, Shuzi Zhou. A smoothing projected Newton-type method for semismooth equations with bound constraints. Journal of Industrial & Management Optimization, 2005, 1 (2) : 235-250. doi: 10.3934/jimo.2005.1.235
[6]	Walter Allegretto, Yanping Lin, Shuqing Ma. On the box method for a non-local parabolic variational inequality. Discrete & Continuous Dynamical Systems - B, 2001, 1 (1) : 71-88. doi: 10.3934/dcdsb.2001.1.71
[7]	Burcu Özçam, Hao Cheng. A discretization based smoothing method for solving semi-infinite variational inequalities. Journal of Industrial & Management Optimization, 2005, 1 (2) : 219-233. doi: 10.3934/jimo.2005.1.219
[8]	Changjun Yu, Kok Lay Teo, Liansheng Zhang, Yanqin Bai. On a refinement of the convergence analysis for the new exact penalty function method for continuous inequality constrained optimization problem. Journal of Industrial & Management Optimization, 2012, 8 (2) : 485-491. doi: 10.3934/jimo.2012.8.485
[9]	Matthias Gerdts, Stefan Horn, Sven-Joachim Kimmerle. Line search globalization of a semismooth Newton method for operator equations in Hilbert spaces with applications in optimal control. Journal of Industrial & Management Optimization, 2017, 13 (1) : 47-62. doi: 10.3934/jimo.2016003
[10]	Shuang Chen, Li-Ping Pang, Dan Li. An inexact semismooth Newton method for variational inequality with symmetric cone constraints. Journal of Industrial & Management Optimization, 2015, 11 (3) : 733-746. doi: 10.3934/jimo.2015.11.733
[11]	Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A smoothing Newton method for generalized Nash equilibrium problems with second-order cone constraints. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 1-18. doi: 10.3934/naco.2012.2.1
[12]	Changjun Yu, Kok Lay Teo, Liansheng Zhang, Yanqin Bai. A new exact penalty function method for continuous inequality constrained optimization problems. Journal of Industrial & Management Optimization, 2010, 6 (4) : 895-910. doi: 10.3934/jimo.2010.6.895
[13]	Zheng-Hai Huang, Jie Sun. A smoothing Newton algorithm for mathematical programs with complementarity constraints. Journal of Industrial & Management Optimization, 2005, 1 (2) : 153-170. doi: 10.3934/jimo.2005.1.153
[14]	Li-Xia Liu, Sanyang Liu, Chun-Feng Wang. Smoothing Newton methods for symmetric cone linear complementarity problem with the Cartesian $P$/$P_0$-property. Journal of Industrial & Management Optimization, 2011, 7 (1) : 53-66. doi: 10.3934/jimo.2011.7.53
[15]	Ming Chen, Chongchao Huang. A power penalty method for a class of linearly constrained variational inequality. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1381-1396. doi: 10.3934/jimo.2018012
[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 & Management Optimization, 2019, 15 (3) : 1241-1261. doi: 10.3934/jimo.2018094
[17]	Jianlin Jiang, Shun Zhang, Su Zhang, Jie Wen. A variational inequality approach for constrained multifacility Weber problem under gauge. Journal of Industrial & Management Optimization, 2018, 14 (3) : 1085-1104. doi: 10.3934/jimo.2017091
[18]	Yekini Shehu, Olaniyi Iyiola. On a modified extragradient method for variational inequality problem with application to industrial electricity production. Journal of Industrial & Management Optimization, 2019, 15 (1) : 319-342. doi: 10.3934/jimo.2018045
[19]	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 & Management Optimization, 2014, 10 (3) : 977-987. doi: 10.3934/jimo.2014.10.977
[20]	Xiao-Hong Liu, Wei-Zhe Gu. Smoothing Newton algorithm based on a regularized one-parametric class of smoothing functions for generalized complementarity problems over symmetric cones. Journal of Industrial & Management Optimization, 2010, 6 (2) : 363-380. doi: 10.3934/jimo.2010.6.363

2018 Impact Factor: 1.025

American Institute of Mathematical Sciences