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]

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

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

Lianjun Zhang, Lingchen Kong, Yan Li, Shenglong Zhou. A smoothing iterative method for quantile regression with nonconvex $ \ell_p $ penalty. Journal of Industrial & Management Optimization, 2017, 13 (1) : 93-112. doi: 10.3934/jimo.2016006

[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

Metrics

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

Other articles
by authors

[Back to Top]