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]

Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070
[2]

Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296
[3]

M. S. Lee, H. G. Harno, B. S. Goh, K. H. Lim. On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 45-61. doi: 10.3934/naco.2020014
[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]

Gang Bao, Mingming Zhang, Bin Hu, Peijun Li. An adaptive finite element DtN method for the three-dimensional acoustic scattering problem. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020351
[6]

José Madrid, João P. G. Ramos. On optimal autocorrelation inequalities on the real line. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020271
[7]

Tommi Brander, Joonas Ilmavirta, Petteri Piiroinen, Teemu Tyni. Optimal recovery of a radiating source with multiple frequencies along one line. Inverse Problems & Imaging, 2020, 14 (6) : 967-983. doi: 10.3934/ipi.2020044
[8]

Reza Lotfi, Zahra Yadegari, Seyed Hossein Hosseini, Amir Hossein Khameneh, Erfan Babaee Tirkolaee, Gerhard-Wilhelm Weber. A robust time-cost-quality-energy-environment trade-off with resource-constrained in project management: A case study for a bridge construction project. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020158
[9]

Bahaaeldin Abdalla, Thabet Abdeljawad. Oscillation criteria for kernel function dependent fractional dynamic equations. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020443
[10]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013
[11]

Min Chen, Olivier Goubet, Shenghao Li. Mathematical analysis of bump to bucket problem. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5567-5580. doi: 10.3934/cpaa.2020251
[12]

Qingfang Wang, Hua Yang. Solutions of nonlocal problem with critical exponent. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5591-5608. doi: 10.3934/cpaa.2020253
[13]

Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017
[14]

Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019
[15]

Stefano Bianchini, Paolo Bonicatto. Forward untangling and applications to the uniqueness problem for the continuity equation. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020384
[16]

Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao. A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28 (4) : 1439-1457. doi: 10.3934/era.2020076
[17]

Zexuan Liu, Zhiyuan Sun, Jerry Zhijian Yang. A numerical study of superconvergence of the discontinuous Galerkin method by patch reconstruction. Electronic Research Archive, 2020, 28 (4) : 1487-1501. doi: 10.3934/era.2020078
[18]

Yuxia Guo, Shaolong Peng. A direct method of moving planes for fully nonlinear nonlocal operators and applications. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020462
[19]

Noah Stevenson, Ian Tice. A truncated real interpolation method and characterizations of screened Sobolev spaces. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5509-5566. doi: 10.3934/cpaa.2020250
[20]

Yue Feng, Yujie Liu, Ruishu Wang, Shangyou Zhang. A conforming discontinuous Galerkin finite element method on rectangular partitions. Electronic Research Archive, , () : -. doi: 10.3934/era.2020120

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences