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

[2]

E. L. Allgower and K. Georg, "Numerical Continuation Methods, An Introduction,", Springer Series in Computational Mathematics, 13 (1990).   Google Scholar

[3]

S. C. Billups, A homotopy-based algorithm for mixed complementarity problems,, SIAM J. Optim., 12 (2002), 583.  doi: 10.1137/S1052623498337431.  Google Scholar

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

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

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

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

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

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

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

[11]

F. Facchinei and J.-S. Pang, "Finite-Dimensional Variational Inequalities and Complementarity Problems,", Vol. I, I (2003).   Google Scholar

[12]

F. Facchinei and J.-S. Pang, "Finite-Dimensional Variational Inequalities and Complementarity Problems,", Vol. \textbf{II}, II (2003).   Google Scholar

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

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

[15]

M. C. Ferris and J.-S. Pang, Engineering and economic applications of complementarity problems,, SIAM Rev., 39 (1997), 669.  doi: 10.1137/S0036144595285963.  Google Scholar

[16]

S. A. Gabriel and J. J. Moré, Smoothing of mixed complementarity problems,, in, (1995), 105.   Google Scholar

[17]

C. B. García and W. I. Zangwill, "Pathways to Solutions, Fixed Points and Equilibria,", Prentice-Hall, (1981).   Google Scholar

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

[19]

C. Kanzow and H. Pieper, Jacobian smoothing methods for nonlinear complementarity problems,, SIAM J. Optim., 9 (1999), 342.  doi: 10.1137/S1052623497328781.  Google Scholar

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

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

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

[23]

S. M. Robinson, Normal maps induced by linear transformations,, Math. Oper. Res., 17 (1992), 691.  doi: 10.1287/moor.17.3.691.  Google Scholar

[24]

T. F. Rutherfold, "MILES: A Mixed Inequality and Nonlinear Equation Solver,", Working paper, (1993).   Google Scholar

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

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

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

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

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

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

[2]

E. L. Allgower and K. Georg, "Numerical Continuation Methods, An Introduction,", Springer Series in Computational Mathematics, 13 (1990).   Google Scholar

[3]

S. C. Billups, A homotopy-based algorithm for mixed complementarity problems,, SIAM J. Optim., 12 (2002), 583.  doi: 10.1137/S1052623498337431.  Google Scholar

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

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

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

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

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

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

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

[11]

F. Facchinei and J.-S. Pang, "Finite-Dimensional Variational Inequalities and Complementarity Problems,", Vol. I, I (2003).   Google Scholar

[12]

F. Facchinei and J.-S. Pang, "Finite-Dimensional Variational Inequalities and Complementarity Problems,", Vol. \textbf{II}, II (2003).   Google Scholar

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

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

[15]

M. C. Ferris and J.-S. Pang, Engineering and economic applications of complementarity problems,, SIAM Rev., 39 (1997), 669.  doi: 10.1137/S0036144595285963.  Google Scholar

[16]

S. A. Gabriel and J. J. Moré, Smoothing of mixed complementarity problems,, in, (1995), 105.   Google Scholar

[17]

C. B. García and W. I. Zangwill, "Pathways to Solutions, Fixed Points and Equilibria,", Prentice-Hall, (1981).   Google Scholar

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

[19]

C. Kanzow and H. Pieper, Jacobian smoothing methods for nonlinear complementarity problems,, SIAM J. Optim., 9 (1999), 342.  doi: 10.1137/S1052623497328781.  Google Scholar

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

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

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

[23]

S. M. Robinson, Normal maps induced by linear transformations,, Math. Oper. Res., 17 (1992), 691.  doi: 10.1287/moor.17.3.691.  Google Scholar

[24]

T. F. Rutherfold, "MILES: A Mixed Inequality and Nonlinear Equation Solver,", Working paper, (1993).   Google Scholar

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

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

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

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

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

[1]

Kaili Zhang, Haibin Chen, Pengfei Zhao. A potential reduction method for tensor complementarity problems. Journal of Industrial & Management Optimization, 2019, 15 (2) : 429-443. 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]

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

[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, 2018, 14 (3) : 981-1005. doi: 10.3934/jimo.2017086

[12]

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

[13]

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

[14]

Zhengshan Dong, Jianli Chen, Wenxing Zhu. Homotopy method for matrix rank minimization based on the matrix hard thresholding method. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 211-224. doi: 10.3934/naco.2019015

[15]

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

[16]

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

[17]

Figen Özpinar, Fethi Bin Muhammad Belgacem. The discrete homotopy perturbation Sumudu transform method for solving partial difference equations. Discrete & Continuous Dynamical Systems - S, 2019, 12 (3) : 615-624. doi: 10.3934/dcdss.2019039

[18]

Xiaona Fan, Li Jiang, Mengsi Li. Homotopy method for solving generalized Nash equilibrium problem with equality and inequality constraints. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1795-1807. doi: 10.3934/jimo.2018123

[19]

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

[20]

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

2018 Impact Factor: 1.025

Metrics

  • PDF downloads (7)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]