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 and 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-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.

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-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.

[1]

Li Wang, Yang Li, Liwei Zhang. A differential equation method for solving box constrained variational inequality problems. Journal of Industrial and 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 and 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 and 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 and 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 and Management Optimization, 2005, 1 (2) : 235-250. doi: 10.3934/jimo.2005.1.235
[6]

Peili Li, Xiliang Lu, Yunhai Xiao. Smoothing Newton method for $ \ell^0 $-$ \ell^2 $ regularized linear inverse problem. Inverse Problems and Imaging, 2022, 16 (1) : 153-177. doi: 10.3934/ipi.2021044
[7]

Walter Allegretto, Yanping Lin, Shuqing Ma. On the box method for a non-local parabolic variational inequality. Discrete and Continuous Dynamical Systems - B, 2001, 1 (1) : 71-88. doi: 10.3934/dcdsb.2001.1.71
[8]

Burcu Özçam, Hao Cheng. A discretization based smoothing method for solving semi-infinite variational inequalities. Journal of Industrial and Management Optimization, 2005, 1 (2) : 219-233. doi: 10.3934/jimo.2005.1.219
[9]

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 and Management Optimization, 2012, 8 (2) : 485-491. doi: 10.3934/jimo.2012.8.485
[10]

Shuang Chen, Li-Ping Pang, Dan Li. An inexact semismooth Newton method for variational inequality with symmetric cone constraints. Journal of Industrial and Management Optimization, 2015, 11 (3) : 733-746. doi: 10.3934/jimo.2015.11.733
[11]

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 and Management Optimization, 2017, 13 (1) : 47-62. doi: 10.3934/jimo.2016003
[12]

Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A smoothing Newton method for generalized Nash equilibrium problems with second-order cone constraints. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 1-18. doi: 10.3934/naco.2012.2.1
[13]

Zheng-Hai Huang, Jie Sun. A smoothing Newton algorithm for mathematical programs with complementarity constraints. Journal of Industrial and 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 and Management Optimization, 2011, 7 (1) : 53-66. doi: 10.3934/jimo.2011.7.53
[15]

Changjun Yu, Kok Lay Teo, Liansheng Zhang, Yanqin Bai. A new exact penalty function method for continuous inequality constrained optimization problems. Journal of Industrial and Management Optimization, 2010, 6 (4) : 895-910. doi: 10.3934/jimo.2010.6.895
[16]

Ming Chen, Chongchao Huang. A power penalty method for a class of linearly constrained variational inequality. Journal of Industrial and Management Optimization, 2018, 14 (4) : 1381-1396. doi: 10.3934/jimo.2018012
[17]

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 and Management Optimization, 2019, 15 (3) : 1241-1261. doi: 10.3934/jimo.2018094
[18]

Jianlin Jiang, Shun Zhang, Su Zhang, Jie Wen. A variational inequality approach for constrained multifacility Weber problem under gauge. Journal of Industrial and Management Optimization, 2018, 14 (3) : 1085-1104. doi: 10.3934/jimo.2017091
[19]

Yan Li, Liping Zhang. A smoothing Newton method preserving nonnegativity for solving tensor complementarity problems with $ P_0 $ mappings. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022041
[20]

Zhuoyi Xu, Yong Xia, Deren Han. On box-constrained total least squares problem. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 439-449. doi: 10.3934/naco.2020043

2020 Impact Factor: 1.801

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy