QPCOMP: A quadratic programming based solver for mixed complementarity problems.

*(English)*Zbl 0873.90095Summary: QPCOMP is an extremely robust algorithm for solving mixed nonlinear complementarity problems that has fast local convergence behavior. Based in part on the NE/SQP method of Pang and Gabriel (1993), this algorithm represents a significant advance in robustness at no cost in efficiency. In particular, the algorithm is shown to solve any solvable Lipschitz continuous, continuously differentiable, pseudo-monotone mixed nonlinear complementarity problem. QPCOMP also extends the NE/SQP method for the nonlinear complementarity problem to the more general mixed nonlinear complementarity problem. Computational results are provided, which demonstrate the effectiveness of the algorithm.

##### MSC:

90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |

##### Keywords:

variational inequalities; proximal perturbations; pseudo-monotonicity; mixed nonlinear complementarity
PDF
BibTeX
Cite

\textit{S. C. Billups} and \textit{M. C. Ferris}, Math. Program. 76, No. 3 (B), 533--562 (1997; Zbl 0873.90095)

Full Text:
DOI

##### References:

[1] | S.C. Billups, Algorithms for complementarity problems and generalized equations, Ph.D. thesis, University of Wisconsin-Madison (Madison, WI, 1995). |

[2] | A. Brooke, D. Kendrick and A. Meeraus,GAMS: A User’s Guide (Scientific Press, South San Francisco, CA, 1988). |

[3] | C. Chen and O.L. Mangasarian, A class of smoothing functions for nonlinear and mixed complementarity problems,Computational Optimization and Applications 5 (1996) 97–138. · Zbl 0859.90112 |

[4] | S.P. Dirkse and M.C. Ferris. MCPLIB: A collection of nonlinear mixed complementarity problems.Optimization Methods and Software 5 (1995) 319–345. |

[5] | S.P. Dirkse and M.C. Ferris. The PATH solver: A non-monotone stabilization scheme for mixed complementarity problems.Optimization Methods and Software 5 (1995) 123–156. |

[6] | S.P. Dirkse, M.C. Ferris, P.V. Preckel and T. Rutherford, The GAMS callable program library for variational and complementarity solvers, Mathematical Programming Technical Report 94-07, Computer Sciences Department, University of Wisconsin (Madison, WI, 1994) available via ftp://ftp.cs.wisc.edu/math-prog/tech-reports/. |

[7] | M.C. Ferris and J.S. Pang, Engineering and economic applications of complementarity problems. Discussion Papers in Economics 95-4, Department of Economics, University of Colorado (Boulder, CO, 1995) available via ftp://ftp.cs.wisc.edu/math-prog/tech-reports/. |

[8] | S.A. Gabriel, Algorithms for the Nonlinear Complementarity Problem: The NE/SQP Method and Extensions. Ph.D. thesis, The Johns Hopkins University (Baltimore, MD, 1992). · Zbl 0794.90071 |

[9] | P.T. Harker and J.S. Pang, Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications,Mathematical Programming 48 (1990) 161–220. · Zbl 0734.90098 |

[10] | P.T. Harker and B. Xiao, Newton’s method for the nonlinear complementarity problem: A B-differentiable equation approach,Mathematical Programming 48 (1990) 339–358. · Zbl 0724.90071 |

[11] | O.L. Mangasarian,Nonlinear Programming (McGraw-Hill, New York, 1969); SIAM Classics in Applied Mathematics 10 (SIAM, Philadelphia, PA, 1994). |

[12] | B.A. Murtagh and M.A. Saunders, MINOS 5.0 user’s guide. Technical Report SOL 83.20, Stanford University (Stanford, CA, 1983). |

[13] | J.M. Ortega and W.C. Rheinboldt,Iterative Solution of Nonlinear Equations in Several Variables (Academic, San Diego, CA, 1970). · Zbl 0241.65046 |

[14] | J.S. Pang and S.A. Gabriel, NE/SQP: A robust algorithm for the nonlinear complementarity problem,Mathematical Programming 60 (1993) 295–338. · Zbl 0808.90123 |

[15] | D. Ralph, Global convergence of damped Newton’s method for nonsmooth equations, via the path search,Mathematics of Operations Research 19 (1994) 352–389. · Zbl 0819.90102 |

[16] | R.T. Rockafellat, Monotone operators and augmented Lagrangian methods in nonlinear programming, in: O.L. Mangasarian, R.R. Meyer and S.M. Robinson, eds.,Nonlinear Programming 3 (Academic, London, 1978) pp. 1–26. |

[17] | T.F. Rutherford, MILES: A mixed inequality and nonlinear equation solver, Working Paper, Department of Economics, University of Colorado, Boulder, CO. |

[18] | A.N. Tikhonov and V.Y. Arsenin,Solutions of Ill-Posed Problems (Wiley, New York, 1977). |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.