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

Zhengyong Zhou; Bo Yu

doi:10.3934/jimo.2011.7.977

Article Contents

2011, Volume 7, Issue 4: 977-989. Doi: 10.3934/jimo.2011.7.977

This issue Previous Article A variational problem and optimal control Next Article Multiple solutions for a class of semilinear elliptic variational inclusion problems

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

Zhengyong Zhou^1, and
Bo Yu^2,

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

Received: December 31, 2010

Revised: May 31, 2011

Published: September 2011

Abstract Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: 90C33, 65D10, 65H20.

Citation:

Related Papers

Cited by

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-375.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, Springer-Verlag, Berlin, 1990.
[3]	S. C. Billups, A homotopy-based algorithm for mixed complementarity problems, SIAM J. Optim., 12 (2002), 583-605.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, 1995), Comput. Optim. Appl., 7 (1997), 3-25.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-626.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-138.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-540.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-616.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-316.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-345.doi: 10.1080/10556789508805619.
[11]	F. Facchinei and J.-S. Pang, "Finite-Dimensional Variational Inequalities and Complementarity Problems," Vol. I, Springer Series in Operations Research, Springer-Verlag, New York, 2003.
[12]	F. Facchinei and J.-S. Pang, "Finite-Dimensional Variational Inequalities and Complementarity Problems," Vol. II, Springer Series in Operations Research, Springer-Verlag, New York, 2003.
[13]	X. Fan and B. Yu, Homotopy method for solving variational inequalities with bounded box constraints, Nonlinear Anal., 68 (2008), 2357-2361.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, Part I, Comput. Optim. Appl., 12 (1999), 207-227.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-713.doi: 10.1137/S0036144595285963.
[16]	S. A. Gabriel and J. J. Moré, Smoothing of mixed complementarity problems, in "Complementarity and Variational Problems" (Baltimore, MD, 1995), SIAM, Philadelphia, PA, 1997, 105-116.
[17]	C. B. García and W. I. Zangwill, "Pathways to Solutions, Fixed Points and Equilibria," Prentice-Hall, Englewood Cliffs, New Jersey, 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-220.doi: 10.1007/BF01582255.
[19]	C. Kanzow and H. Pieper, Jacobian smoothing methods for nonlinear complementarity problems, SIAM J. Optim., 9 (1999), 342-373.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-230.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-131.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-35.
[23]	S. M. Robinson, Normal maps induced by linear transformations, Math. Oper. Res., 17 (1992), 691-714.doi: 10.1287/moor.17.3.691.
[24]	T. F. Rutherfold, "MILES: A Mixed Inequality and Nonlinear Equation Solver," Working paper, Department of Economics, University of Colorado, Boulder, 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-413.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-187.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-599.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-689.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, Piecewise Smooth, Semismooth and Smoothing Methods (Lausanne, 1997), Appl. Optim., 22, Kluwer Acad. Publ., Dordrecht, (1999), 421-441.