Article Contents
Article Contents

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

• 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.
Mathematics Subject Classification: 90C33, 65D10, 65H20.

 Citation:

•  [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.