## Abstract

In this paper we present a new algorithm for the solution of nonlinear complementarity problems. The algorithm is based on a semismooth equation reformulation of the complementarity problem. We exploit the recent extension of Newton's method to semismooth systems of equations and the fact that the natural merit function associated to the equation reformulation is continuously differentiable to develop an algorithm whose global and quadratic convergence properties can be established under very mild assumptions. Other interesting features of the new algorithm are an extreme simplicity along with a low computational burden per iteration. We include numerical tests which show the viability of the approach.

This is a preview of subscription content, access via your institution.

## References

- [1]
D.P. Bertsekas,

*Constrained Optimization and Lagrange Multiplier Methods*(Academic Press, New York, 1982). - [2]
B. Chen and P.T. Harker, A noninterior continuation method for quadratic and linear programming,

*SIAM J. on Optimization*3 (1993) 503–515. - [3]
F.H. Clarke,

*Optimization and Nonsmooth Analysis*(John Wiley & Sons, New York, 1983) (reprinted by SIAM, Philadelphia, PA, 1990). - [4]
R.W. Cottle, J.-S. Pang and R.E. Stone,

*The Linear Complementarity Problem*(Academic Press, Boston, 1992). - [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]
F. Facchinei, Minimization of

*SC*^{1}functions and the Maratos effect,*Operations Research Letters*17 (1995), 131–137. - [7]
F. Facchinei and J. Soares, A new meril function for nonlinear complementarity problems and a related algorithm, Technical Report 15.94, Dipartimento di Informatica e Sistemistica, Università di Roma “La Sapienza”, Rome, Italy (1994) (to appear in:

*SIAM J. on Optimization*). - [8]
F. Facchinei and J. Soares, Testing a new class of algorithms for nonlinear complementarity problems, in: F. Giannessi and A. Maugeri, eds.,

*Variational Inequalities and Network Equilibrium Problems*(Plenum Press, New York, 1995) 69–83. - [9]
M.C. Ferris and S. Lucidi, Nonmonotone stabilization methods for nonlinear equations,

*J. of Optimization Theory and Applications*81 (1994) 53–71. - [10]
M.C. Ferris and D. Ralph, Projected gradient methods for nonlinear complementarity problems via normal maps, in: D.Z. Du, L. Qi and R.S. Womersley, eds.,

*Recent Advances in Nonsmooth Optimization*(World Scientific Publishers, Singapore) 57–87. - [11]
A. Fischer, A special Newton-type optimization method.

*Optimization*24 (1992) 269–284. - [12]
A. Fischer, A Newton-type method for positive semidefinite linear complementarity problems,

*J. of Optimization Theory and Applications*86 (1995) 585–608. - [13]
A. Fischer, An NCP-function and its use for the solution of complementarity problems, in: D.Z. Du, L. Qi and R.S. Womersley, eds.,

*Recent Advances in Nonsmooth Optimization*(World Scientific Publishers, Singapore) 88–105. - [14]
A. Fischer and C. Kanzow, On finite termination of an iterative method for linear complementarity problems, Preprint MATH-NM-10-1994 Institute for Numerical Mathematics, Technical University of Dresden, Dresden, Germany (1994) (to appear in:

*Mathematical Programming*). - [15]
M. Fukushima, Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems,

*Mathematical Programming*(Series A) 53 (1992) 99–110. - [16]
C. Geiger and C. Kanzow, On the resolution of monotone complementarity problems,

*Computational Optimization and Applications*5 (1996) 155–173. - [17]
L. Grippo, F. Lampariello and S. Lucidi, A nonmonotone linesearch technique for Newton's method,

*SIAM J. on Numerical Analysis*23 (1986) 707–716. - [18]
S.P. Han, J.-S. Pang and N. Rangaraj, Globally convergent Newton methods for nonsmooth equations,

*Mathematics of Operations Research*17 (1992) 586–607. - [19]
P.T. Harker, Accelerating the convergence of the diagonalization and projection algorithm for finitedimensional variational inequalities,

*Mathematical Programming*(Series A) 41 (1988) 25–59. - [20]
P.T. Harker and B. Xiao, Newton's method for the nonlinear complementarity problem: A

*B*-differentiable equation approach,*Mathematical Programming*(Series A) 48 (1990) 339–357. - [21]
W. Hock and K. Schittkowski, Test examples for nonlinear programming codes, Lectures Notes in Economics and Mathematical Systems 187 (Springer-Verlag, Berlin, 1981).

- [22]
H. Jiang, Unconstrained minimization approaches to nonlinear complementarities, Applied Mathematics Report AMR 94/33, School of Mathematics, University of New South Wales, Sydney, Australia (1994).

- [23]
H. Jiang and L. Qi, A nonsmooth equations approach to nonlinear complementarities, Applied Mathematics Report AMR 94/31, School of Mathematics, University of New South Wales, Sydney, Australia (1994) (to appear in:

*SIAM J. on Control and Optimization*). - [24]
N.H. Josephy, Newton's method for generalized equations, MRC Technical Summary Report 1965, Mathematics Research Center. University of Wisconsin-Madison, WI (1979).

- [25]
C. Kanzow, Some equation-based methods for the nonlinear complementarity problem,

*Optimization Methods and Software*3 (1994) 327–340. - [26]
C. Kanzow, Nonlinear complementarity as unconstrained optimization,

*J. of Optimization Theory and Applications*88 (1996) 139–155. - [27]
C. Kanzow, Global convergence properties of some iterative methods for linear complementarity problems, Preprint 72, Institute of Applied Mathematics, University of Hamburg Hamburg, Germany (1993) revised (1994) (to appear in:

*SIAM J. on Optimization*). - [28]
M. Kojima, Computational methods for solving the nonlinear complementarity problem, Keio Engineering Reports 27 (1974) 1–41.

- [29]
O.L. Mangasarian, Equivalence of the complementarity problem to a system of nonlinear equations,

*SIAM J. on Applied Muthematics*31 (1976) 89–92. - [30]
O.L. Mangasarian and M.V. Solodov, Nonlinear complementarity as unconstrained and constrained minimization,

*Mathematical Programming*(Series B) 62 (1993) 277–297. - [31]
R. Mifflin, Semismooth and semiconvex functions in constrained optimization,

*SIAM J. on Control and Optimization*15 (1977) 957–972. - [32]
J.J. Moré, Global methods for nonlinear complementarity problems, Preprint MCS-P429-0494 Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL (1994).

- [33]
J.J. Moré and W.C. Rheinboldt, On

*P*- and*S*-functions and related classes of*n*-dimensional nonlinear mappings,*Linear Algebra and its Applications*6 (1973) 45–68. - [34]
J.-S. Pang, Newton's method for B-differentiable equations.

*Mathematics of Operations Research*15 (1990) 311–341. - [35]
J.-S. Pang, A B-differentiable equation-based, globally and locally quadratically convergent algorithm for nonlinear programs, complementarity and variational inequality problems,

*Mathematical Programming*(Series A) 51 (1991) 101–132. - [36]
J.-S. Pang and S.A. Gabriel, NE/SQP: A robust algorithm for the nonlinear complementarity problem,

*Mathematical Programming*(Series A) 60 (1993) 295–337. - [37]
J.-S. Pang and L. Qi, Nonsmooth equations: motivation and algorithms,

*SIAM J. on Optimization*3 (1993) 443–465. - [38]
L. Qi, A convergence analysis of some algorithms for solving nonsmooth equations,

*Mathematics of Operations Research*18 (1993) 227–244. - [39]
L. Qi and H. Jiang, Karush-Kuhn-Tucker equations and convergence analysis of Newton methods and Quasi-Newton methods for solving these equations, Technical Report AMR 94/5, School of Mathematics, University of New South Wales, Australia (1994) (to appear in:

*SIAM J. on Control and Optimization*). - [40]
L. Qi and J. Sun, A nonsmooth version of Newton's method,

*Mathematical Programming*(Series A) 58 (1993) 353–368. - [41]
D. Ralph. Global convergence of damped Newton's method for nonsmooth equations via the path search,

*Mathematics of Operations Research*19 (1994) 352–389. - [42]
S.M. Robinson, Strongly regular generalized equations,

*Mathematics of Operations Research*5 (1980) 43–62. - [43]
S.M. Robinson, Implicit

*B*-differentiability in generalized equations, Technical Summary Report 2854, Mathematics Research Center, University of Wisconsin-Madison. WI (1985). - [44]
S.M. Robinson, An implicit function theorem for

*B*-differentiable functions, IIASA Working Paper 88-67, Laxemburg, Austria (1988). - [45]
S.M. Robinson, Newton's method for a class of nonsmooth functions, Manuscript, Department of Industrial Engineering, University of Wisconsin-Madison, WI (1988).

- [46]
S.M. Robinson, Normal maps induced by linear transformations,

*Mathematics of Operations Research*17 (1992) 691–714. - [47]
S.M. Robinson, Generalized equations, in: A. Bachem, M. Groetschel and B. Korte, eds.,

*Mathematical programming: the state of the art*(Springer-Verlag, Berlin, 1983) 346–367. - [48]
H. Scarf,

*The Computation of Economic Equilibria*(Yale University Press, New Haven, CT, 1973). - [49]
P.K. Subramanian, Gauss-Newton methods for the complementarity problem,

*J. of Optimization Theory and Applications*77 (1993) 467–482. - [50]
R.L. Tobin, Variable dimension spatial price equilibrium algorithm,

*Mathematical Programming*(Series A) 40 (1988) 33–51. - [51]
P.L. Toint, A non-monotone trust-region algorithm for nonlinear optimization subject to convex constraints, Report 92/94, Department of Mathematics, FUNDP, Namur, Belgium (1994).

- [52]
P. Tseng, Growth behavior of a class of merit functions for the nonlinear complementarity problem, Technical Report, Department of Mathematics, University of Washington, Seattle, WA (1994).

- [53]
L.T. Watson, Solving the nonlinear complementarity problem by a homotopy method,

*SIAM J. on Control and Optimization*17 (1979) 36–46. - [54]
B. Xiao and P.T. Harker, A nonsmooth Newton method for variational inequalities, 1: Theory,

*Mathematical Programming*(Series A) 65 (1994) 151–194. - [55]
B. Xiao and P.T. Harker, A nonsmooth Newton method for variational inequalities, II: Numerical results,

*Mathematical Programming*(Series A) 65 (1994) 195–216.

## Author information

### Affiliations

### Corresponding author

## Rights and permissions

## About this article

### Cite this article

De Luca, T., Facchinei, F. & Kanzow, C. A semismooth equation approach to the solution of nonlinear complementarity problems.
*Mathematical Programming* **75, **407–439 (1996). https://doi.org/10.1007/BF02592192

Received:

Revised:

Issue Date:

### Key words

- Nonlinear complementarity problem
- Semismoothness
- Smooth merit function
- Global convergence
- Quadratic convergence