# American Institute of Mathematical Sciences

2011, 7(4): 977-989. doi: 10.3934/jimo.2011.7.977

## A smoothing homotopy method based on Robinson's normal equation for mixed complementarity problems

 1 School of Mathematical Sciences, Dalian University of Technology, Dalian, Liaoning 116024, China 2 School of Mathematical Science, Dalian University of Technology, Dalian, Liaoning 116024, China

Received  January 2011 Revised  June 2011 Published  August 2011

In this paper, a probability-one homotopy method for solving mixed complementarity problems is proposed. The homotopy equation is constructed by using the Robinson's normal equation of mixed complementarity problem and a $C^2$-smooth approximation of projection function. Under the condition that the mixed complementarity problem has no solution at infinity, which is a weaker condition than several well-known ones, existence and convergence of a smooth homotopy path from almost any starting point in $\mathbb{R}^n$ are proven. The homotopy method is implemented in Matlab and numerical results on the MCPLIB test collection are given.
Citation: Zhengyong Zhou, Bo Yu. A smoothing homotopy method based on Robinson's normal equation for mixed complementarity problems. Journal of Industrial & Management Optimization, 2011, 7 (4) : 977-989. doi: 10.3934/jimo.2011.7.977
##### References:
 [1] K. Ahuja, L. T. Watson and S. C. Billups, Probability-one homotopy maps for mixed complementarity problems,, Comput. Optim. Appl., 41 (2008), 363. doi: 10.1007/s10589-007-9107-z. [2] E. L. Allgower and K. Georg, "Numerical Continuation Methods, An Introduction,", Springer Series in Computational Mathematics, 13 (1990). [3] S. C. Billups, A homotopy-based algorithm for mixed complementarity problems,, SIAM J. Optim., 12 (2002), 583. doi: 10.1137/S1052623498337431. [4] S. C. Billups, S. P. Dirkse and M. C. Ferris, A comparison of large scale mixed complementarity problem solvers,, Computational Issues in High Performance Software for Nonlinear Optimization (Capri, 7 (1997), 3. doi: 10.1023/A:1008632215341. [5] S. C. Billups and L. T. Watson, A probability-one homotopy algorithm for nonsmooth equations and mixed complementarity problems,, SIAM J. Optim., 12 (2002), 606. doi: 10.1137/S105262340037758X. [6] C. H. 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. [7] 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. Comp., 67 (1998), 519. doi: 10.1090/S0025-5718-98-00932-6. [8] 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. [9] A. N. Daryina, A. F. Izmailov and M. V. Solodov, Numerical results for a globalized active-set Newton method for mixed complementarity problems,, Comput. Appl. Math., 24 (2005), 293. doi: 10.1590/S0101-82052005000200008. [10] S. P. Dirkse and M. C. Ferris, MCPLIB: A collection of nonlinear mixed complementarity problems,, Optim. Methods Softw., 5 (1995), 319. doi: 10.1080/10556789508805619. [11] F. Facchinei and J.-S. Pang, "Finite-Dimensional Variational Inequalities and Complementarity Problems,", Vol. I, I (2003). [12] F. Facchinei and J.-S. Pang, "Finite-Dimensional Variational Inequalities and Complementarity Problems,", Vol. \textbf{II}, II (2003). [13] X. Fan and B. Yu, Homotopy method for solving variational inequalities with bounded box constraints,, Nonlinear Anal., 68 (2008), 2357. doi: 10.1016/j.na.2007.01.063. [14] M. C. Ferris and T. S. Munson, Interfaces to PATH 3.0: Design, implementation and usage,, Computational Optimization-A tribute to Olvi Mangasarian, 12 (1999), 207. doi: 10.1023/A:1008636318275. [15] M. C. Ferris and J.-S. Pang, Engineering and economic applications of complementarity problems,, SIAM Rev., 39 (1997), 669. doi: 10.1137/S0036144595285963. [16] S. A. Gabriel and J. J. Moré, Smoothing of mixed complementarity problems,, in, (1995), 105. [17] C. B. García and W. I. Zangwill, "Pathways to Solutions, Fixed Points and Equilibria,", Prentice-Hall, (1981). [18] P. T. Harker and J.-S. Pang, Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications,, Math. Programming, 48 (1990), 161. doi: 10.1007/BF01582255. [19] C. Kanzow and H. Pieper, Jacobian smoothing methods for nonlinear complementarity problems,, SIAM J. Optim., 9 (1999), 342. doi: 10.1137/S1052623497328781. [20] D. H. Li and M. Fukushima, Smoothing Newton and quasi-Newton methods for mixed complementarity problems, Nonsmooth and Smoothing Methods (Hong Kong, 1998),, Comput. Optim. Appl., 17 (2000), 203. doi: 10.1023/A:1026502415830. [21] J.-S. Pang, A B-differentiable equation-based, globally and locally quadratically convergent algorithm for nonlinear programs, complementarity and variational inequality problems,, Math. Programming, 51 (1991), 101. doi: 10.1007/BF01586928. [22] L. Q. Qi, D. F. Sun and G. L. Zhou, A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities,, Math. Program., 87 (2000), 1. [23] S. M. Robinson, Normal maps induced by linear transformations,, Math. Oper. Res., 17 (1992), 691. doi: 10.1287/moor.17.3.691. [24] T. F. Rutherfold, "MILES: A Mixed Inequality and Nonlinear Equation Solver,", Working paper, (1993). [25] D. F. Sun and R. S. Womersley, A new unconstrained differentiable merit function for box constrained variational inequality problems and a damped Gauss-Newton method,, SIAM J. Optim., 9 (1999), 388. doi: 10.1137/S1052623496314173. [26] D. F. Sun, R. S. Womersley and H. D. Qi, A feasible semismooth asymptotically Newton method for mixed complementarity problems,, Math. Program., 94 (2002), 167. doi: 10.1007/s10107-002-0305-2. [27] Q. Xu, B. Yu, G. C. Feng and C. Y. Dang, Condition for global convergence of a homotopy method for variational inequality problems on unbounded sets,, Optim. Methods Softw., 22 (2007), 587. doi: 10.1080/10556780600887883. [28] Q. Xu and C. Y. Dang, A new homotopy method for solving non-linear complementarity problems,, Optimization, 57 (2008), 681. doi: 10.1080/02331930802355317. [29] G. L. Zhou, D. F. Sun and L. Q. Qi, "Numerical Experiments for a Class of Squared Smoothing Newton Methods for Box Constrained Variational Inequality Problems,", Reformation: Nonsmooth, 22 (1999), 421.

show all references

##### References:
 [1] K. Ahuja, L. T. Watson and S. C. Billups, Probability-one homotopy maps for mixed complementarity problems,, Comput. Optim. Appl., 41 (2008), 363. doi: 10.1007/s10589-007-9107-z. [2] E. L. Allgower and K. Georg, "Numerical Continuation Methods, An Introduction,", Springer Series in Computational Mathematics, 13 (1990). [3] S. C. Billups, A homotopy-based algorithm for mixed complementarity problems,, SIAM J. Optim., 12 (2002), 583. doi: 10.1137/S1052623498337431. [4] S. C. Billups, S. P. Dirkse and M. C. Ferris, A comparison of large scale mixed complementarity problem solvers,, Computational Issues in High Performance Software for Nonlinear Optimization (Capri, 7 (1997), 3. doi: 10.1023/A:1008632215341. [5] S. C. Billups and L. T. Watson, A probability-one homotopy algorithm for nonsmooth equations and mixed complementarity problems,, SIAM J. Optim., 12 (2002), 606. doi: 10.1137/S105262340037758X. [6] C. H. 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. [7] 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. Comp., 67 (1998), 519. doi: 10.1090/S0025-5718-98-00932-6. [8] 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. [9] A. N. Daryina, A. F. Izmailov and M. V. Solodov, Numerical results for a globalized active-set Newton method for mixed complementarity problems,, Comput. Appl. Math., 24 (2005), 293. doi: 10.1590/S0101-82052005000200008. [10] S. P. Dirkse and M. C. Ferris, MCPLIB: A collection of nonlinear mixed complementarity problems,, Optim. Methods Softw., 5 (1995), 319. doi: 10.1080/10556789508805619. [11] F. Facchinei and J.-S. Pang, "Finite-Dimensional Variational Inequalities and Complementarity Problems,", Vol. I, I (2003). [12] F. Facchinei and J.-S. Pang, "Finite-Dimensional Variational Inequalities and Complementarity Problems,", Vol. \textbf{II}, II (2003). [13] X. Fan and B. Yu, Homotopy method for solving variational inequalities with bounded box constraints,, Nonlinear Anal., 68 (2008), 2357. doi: 10.1016/j.na.2007.01.063. [14] M. C. Ferris and T. S. Munson, Interfaces to PATH 3.0: Design, implementation and usage,, Computational Optimization-A tribute to Olvi Mangasarian, 12 (1999), 207. doi: 10.1023/A:1008636318275. [15] M. C. Ferris and J.-S. Pang, Engineering and economic applications of complementarity problems,, SIAM Rev., 39 (1997), 669. doi: 10.1137/S0036144595285963. [16] S. A. Gabriel and J. J. Moré, Smoothing of mixed complementarity problems,, in, (1995), 105. [17] C. B. García and W. I. Zangwill, "Pathways to Solutions, Fixed Points and Equilibria,", Prentice-Hall, (1981). [18] P. T. Harker and J.-S. Pang, Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications,, Math. Programming, 48 (1990), 161. doi: 10.1007/BF01582255. [19] C. Kanzow and H. Pieper, Jacobian smoothing methods for nonlinear complementarity problems,, SIAM J. Optim., 9 (1999), 342. doi: 10.1137/S1052623497328781. [20] D. H. Li and M. Fukushima, Smoothing Newton and quasi-Newton methods for mixed complementarity problems, Nonsmooth and Smoothing Methods (Hong Kong, 1998),, Comput. Optim. Appl., 17 (2000), 203. doi: 10.1023/A:1026502415830. [21] J.-S. Pang, A B-differentiable equation-based, globally and locally quadratically convergent algorithm for nonlinear programs, complementarity and variational inequality problems,, Math. Programming, 51 (1991), 101. doi: 10.1007/BF01586928. [22] L. Q. Qi, D. F. Sun and G. L. Zhou, A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities,, Math. Program., 87 (2000), 1. [23] S. M. Robinson, Normal maps induced by linear transformations,, Math. Oper. Res., 17 (1992), 691. doi: 10.1287/moor.17.3.691. [24] T. F. Rutherfold, "MILES: A Mixed Inequality and Nonlinear Equation Solver,", Working paper, (1993). [25] D. F. Sun and R. S. Womersley, A new unconstrained differentiable merit function for box constrained variational inequality problems and a damped Gauss-Newton method,, SIAM J. Optim., 9 (1999), 388. doi: 10.1137/S1052623496314173. [26] D. F. Sun, R. S. Womersley and H. D. Qi, A feasible semismooth asymptotically Newton method for mixed complementarity problems,, Math. Program., 94 (2002), 167. doi: 10.1007/s10107-002-0305-2. [27] Q. Xu, B. Yu, G. C. Feng and C. Y. Dang, Condition for global convergence of a homotopy method for variational inequality problems on unbounded sets,, Optim. Methods Softw., 22 (2007), 587. doi: 10.1080/10556780600887883. [28] Q. Xu and C. Y. Dang, A new homotopy method for solving non-linear complementarity problems,, Optimization, 57 (2008), 681. doi: 10.1080/02331930802355317. [29] G. L. Zhou, D. F. Sun and L. Q. Qi, "Numerical Experiments for a Class of Squared Smoothing Newton Methods for Box Constrained Variational Inequality Problems,", Reformation: Nonsmooth, 22 (1999), 421.
 [1] Kaili Zhang, Haibin Chen, Pengfei Zhao. A potential reduction method for tensor complementarity problems. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-15. doi: 10.3934/jimo.2018049 [2] Chunyang Zhang, Shugong Zhang, Qinghuai Liu. Homotopy method for a class of multiobjective optimization problems with equilibrium constraints. Journal of Industrial & Management Optimization, 2017, 13 (1) : 81-92. doi: 10.3934/jimo.2016005 [3] 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 [4] Behrouz Kheirfam. A weighted-path-following method for symmetric cone linear complementarity problems. Numerical Algebra, Control & Optimization, 2014, 4 (2) : 141-150. doi: 10.3934/naco.2014.4.141 [5] Ming-Zheng Wang, M. Montaz Ali. Penalty-based SAA method of stochastic nonlinear complementarity problems. Journal of Industrial & Management Optimization, 2010, 6 (1) : 241-257. doi: 10.3934/jimo.2010.6.241 [6] Wei-Zhe Gu, Li-Yong Lu. The linear convergence of a derivative-free descent method for nonlinear complementarity problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 531-548. doi: 10.3934/jimo.2016030 [7] 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 [8] 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 [9] Mingzheng Wang, M. Montaz Ali, Guihua Lin. Sample average approximation method for stochastic complementarity problems with applications to supply chain supernetworks. Journal of Industrial & Management Optimization, 2011, 7 (2) : 317-345. doi: 10.3934/jimo.2011.7.317 [10] 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 [11] Yi Zhang, Liwei Zhang, Jia Wu. On the convergence properties of a smoothing approach for mathematical programs with symmetric cone complementarity constraints. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1-25. doi: 10.3934/jimo.2017086 [12] Jie Zhang, Yue Wu, Liwei Zhang. A class of smoothing SAA methods for a stochastic linear complementarity problem. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 145-156. doi: 10.3934/naco.2012.2.145 [13] Zhichuan Zhu, Bo Yu, Li Yang. Globally convergent homotopy method for designing piecewise linear deterministic contractual function. Journal of Industrial & Management Optimization, 2014, 10 (3) : 717-741. doi: 10.3934/jimo.2014.10.717 [14] Liuyang Yuan, Zhongping Wan, Jingjing Zhang, Bin Sun. A filled function method for solving nonlinear complementarity problem. Journal of Industrial & Management Optimization, 2009, 5 (4) : 911-928. doi: 10.3934/jimo.2009.5.911 [15] Xin-He Miao, Jein-Shan Chen. Error bounds for symmetric cone complementarity problems. Numerical Algebra, Control & Optimization, 2013, 3 (4) : 627-641. doi: 10.3934/naco.2013.3.627 [16] 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 [17] Fengming Ma, Yiju Wang, Hongge Zhao. A potential reduction method for the generalized linear complementarity problem over a polyhedral cone. Journal of Industrial & Management Optimization, 2010, 6 (1) : 259-267. doi: 10.3934/jimo.2010.6.259 [18] Jinchuan Zhou, Naihua Xiu, Jein-Shan Chen. Solution properties and error bounds for semi-infinite complementarity problems. Journal of Industrial & Management Optimization, 2013, 9 (1) : 99-115. doi: 10.3934/jimo.2013.9.99 [19] X. X. Huang, D. Li, Xiaoqi Yang. Convergence of optimal values of quadratic penalty problems for mathematical programs with complementarity constraints. Journal of Industrial & Management Optimization, 2006, 2 (3) : 287-296. doi: 10.3934/jimo.2006.2.287 [20] 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

2016 Impact Factor: 0.994