# zbMATH — the first resource for mathematics

##### Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
Solution of monotone complementarity problems with locally Lipschitzian functions. (English) Zbl 0871.90097

Summary: The paper deals with complementarity problems $\text{CP}\left(F\right)$, where the underlying function $F$ is assumed to be locally Lipschitzian. Based on a special equivalent reformulation of $\text{CP}\left(F\right)$ as a system of equations ${\Phi }\left(x\right)=0$ or as the problem of minimizing the merit function ${\Psi }=\frac{1}{2}{|{\Phi }|}_{2}^{2}$, we extend results which hold for sufficiently smooth functions $F$ to the nonsmooth case.

In particular, if $F$ is monotone in a neighbourhood of $x$, it is proved that $0\in \partial {\Psi }\left(x\right)$ is necessary and sufficient for $x$ to be a solution of $\text{CP}\left(F\right)$. Moreover, for monotone functions $F$, a simple derivative-free algorithm that reduces ${\Psi }$ is shown to possess global convergence properties. Finally, the local behaviour of a generalized Newton method is analyzed. To this end, the result by Mifflin that the composition of semismooth functions is again semismooth is extended to $p$-order semismooth functions. Under a suitable regularity condition and if $F$ is $p$-order semismooth the generalized Newton method is shown to be locally well defined and superlinearly convergent with the order of $1+p$.

##### MSC:
 90C33 Complementarity and equilibrium problems; variational inequalities (finite dimensions)
QPCOMP
##### References:
 [1] S.C. Billups and M.C. Ferris, QPCOMP: A quadratic programming based solver for mixed complementarity problems,Mathematical Programming 76 (1997) 533–562 (this issue). [2] B. Chen and P.T. Harker, Smooth approximations to nonlinear complementarity problems, Technical Report, Department of Management and Systems, College of Business and Economics, Washington State University (Pullman, WA 1995). [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 · doi:10.1007/BF00249052 [4] F.H. Clarke,Optimization and Nonsmooth Analysis (Wiley, New York, 1983). [5] R.W. Cottle, J.-S. Pang and R.E. Stone,The Linear Complementarity Problem (Academic, New York, 1992). [6] T. De Luca, F. Facchinci and C. Kanzow, A semismooth equation approach to the solution of nonlinear complementarity problems,Mathematical Programming 75 (1996) 407–439. [7] 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. · doi:10.1080/10556789508805606 [8] F. Facchinei, A. Fischer and C. Kanzow, A semismooth Newton method for variational inequalities: Theoretical results and preliminary numerical experience, Preprint MATH-NM-21-1995, Institute for Numerical Mathematics, Technical University of Dresden (Dresden, 1995). [9] F. Facchinei and J. Soares, A new merit function for nonlinear complementarity problems and a related algorithm,SIAM Journal on Optimization 7 (1997) 225–247. · Zbl 0873.90096 · doi:10.1137/S1052623494279110 [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, Singapore, 1995) 57–87. [11] M.C. Ferris and S. Lucidi, Nonmonotone stabilization methods for nonlinear equations,Journal of Optimization Theory and Applications 81 (1994) 53–71. · Zbl 0803.65070 · doi:10.1007/BF02190313 [12] A. Fischer, A special Newton-type optimization method,Optimization 24 (1992) 269–284. · Zbl 0814.65063 · doi:10.1080/02331939208843795 [13] A. Fischer, A Newton-type method for positive semidefinite linear complementarity problems,Journal of Optimization Theory and Applications 86 (1995) 585–608. · Zbl 0839.90121 · doi:10.1007/BF02192160 [14] A. Fischer, On the superlinear convergence of a Newton-type method for LCP under weak conditions,Optimization Methods and Software 6 (1995) 83–107. · doi:10.1080/10556789508805627 [15] 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, Singapore, 1995) 88–105. [16] A. Friedlander, J.M. Martinez and S.A. Santos, Solution of linear complementarity problems using minimization with simple bounds,Global Optimization 6 (1995) 253–267. · Zbl 0835.90101 · doi:10.1007/BF01099464 [17] C. Geiger and C. Kanzow, On the resolution of monotone complementarity problems,Computational Optimization and Applications 5 (1996) 155–173. · Zbl 0859.90113 · doi:10.1007/BF00249054 [18] P.T. Harker and B. Xian, Newton’s method for the nonlinear complementarity problem: a B-differentiable equation approach,Mathematical Programming 48 (1990) 339–357. · Zbl 0724.90071 · doi:10.1007/BF01582262 [19] J.-B. Hiriart-Urruty and C. Lemaréchal,Convex Analysis and Minimization Algorithms (Springer, Heidelberg, 1993). [20] H. Jiang, Unconstrained minimization approaches to nonlinear complementarity problems,Journal of Global Optimization 9 (1996) 169–181. · Zbl 0868.90122 · doi:10.1007/BF00121662 [21] H. Jiang and L. Qi, Local uniqueness and convergence of iterative methods for nonsmooth variational inequalities,Journal of Mathematical Analysis and Applications 196 (1995) 314–331. · Zbl 0845.65028 · doi:10.1006/jmaa.1995.1412 [22] H. Jiang and L. Qi, Globally and superlinearly convergent trust region algorithm for convex SC1 minimization problems and its application to stochastic programs,Journal of Optimization Theory and Applications 90 (1996) 653–673. · Zbl 0866.90093 · doi:10.1007/BF02189800 [23] H. Jiang and L. Qi, A new nonsmooth equations approach to nonlinear complementarity problems,SIAM Journal on Control and Optimization 35 (1997) 178–193. · Zbl 0872.90097 · doi:10.1137/S0363012994276494 [24] S.-P. Han, J.-S. Pang and N. Rangaraj, Globally convergent Newton methods for nonsmooth equations,Mathematics of Operations Research 17 (1992) 586–607. · Zbl 0777.90057 · doi:10.1287/moor.17.3.586 [25] C. Kanzow, Some equation-based methods for the nonlinear complementarity problem,Optimization Methods and Saftware 3 (1994) 327–340. · doi:10.1080/10556789408805573 [26] C. Kanzow, An unconstrained optimization technique for large-scale linearly constrained convex minimization problems,Computing 53 (1994) 101–117. · Zbl 0820.90099 · doi:10.1007/BF02252984 [27] C. Kanzow, Global convergence properties of some iterative methods for linear complementarity problems,SIAM Journal on Optimization, to appear. [28] M. Kojima and S. Shindo, Extensions of Newton and quasi-Newton methods to systems ofPC 1 equations,Journal of Operations Research Society of Japan 29 (1986) 352–374. [29] B. Kummer, Newton’s method for non-differentiable functions, in: J. Guddat et al., eds.,Mathematical Research, Advances in Mathematical Optimization (Akademie, Berlin, 1988) pp. 114–125. [30] B. Kummer, Newton’s method based on generalized derivatives for nonsmooth functions: Convergence analysis, in: W. Oettli and D. Pallaschke, eds.,Advances in Optimization, Lecture Notes in Economics and Mathematical Systems, Vol. 382 (Springer, Heidelberg, 1992) pp. 171–194. [31] O.L. Mangasarian, Equivalence of the complementarity problem to a system of nonlinear equations,SIAM Journal on Applied Mathematics 31 (1976) 89–92. · Zbl 0339.90051 · doi:10.1137/0131009 [32] O.L. Mangasarian and M.V. Solodov, Nonlinear complementarity as unconstrained and constrained minimization,Mathematical Programming 62 (1993) 277–297. · Zbl 0813.90117 · doi:10.1007/BF01585171 [33] R. Mifflin, Semismooth and semiconvex functions in constrained optimization,SIAM Journal on Control and Optimization 15 (1977) 959–972. · Zbl 0376.90081 · doi:10.1137/0315061 [34] J.J. Moré, Global methods for nonlinear complementarity problems,Mathematics of Operations Research, to appear. [35] J.-S. Pang, Newton’s method for B-differentiable equations,Mathematics of Operations Research 15 (1990) 311–341. · Zbl 0716.90090 · doi:10.1287/moor.15.2.311 [36] J.-S. Pang, A B-differentiable equation-based, globally and locally quadratically convergent algorithm for nonlinear programs, complementarity and variational inequality problems,Mathematical Programming 51 (1991) 101–131. · Zbl 0733.90063 · doi:10.1007/BF01586928 [37] J.-S. Pang and S.A. Gabriel, NE/SQP: A robust algorithm for the nonlinear complementarity problem,Mathematical Programming 60 (1993) 295–337. · Zbl 0808.90123 · doi:10.1007/BF01580617 [38] J.-S. Pang and L. Qi, Nonsmooth equations: Motivation and algorithms,SIAM Journal on Optimization 3 (1993) 443–465. · Zbl 0784.90082 · doi:10.1137/0803021 [39] J.-S. Pang and L. Qi, A globally convergent Newton method for convex SC1 minimization problems,Journal of Optimization Theory and Applications 85 (1995) 633–648. · Zbl 0831.90095 · doi:10.1007/BF02193060 [40] L. Qi, Convergence analysis of some algorithms for solving nonsmooth equations,Mathematics of Operations Research 18 (1993) 227–244. · Zbl 0776.65037 · doi:10.1287/moor.18.1.227 [41] L. Qi and H. Jiang, Karush-Kuhn-Tucker equations and convergence analysis of Newton methods and quasi-Newton methods for solving these equations,Mathematics of Operations Research, to appear. [42] L. Qi and J. Sun, A nonsmooth version of Newton’s method,Mathematical Programming 58 (1993) 353–367. · Zbl 0780.90090 · doi:10.1007/BF01581275 [43] 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 · doi:10.1287/moor.19.2.352 [44] S.M. Robinson, Mathematical foundations of nonsmooth embedding methods,Mathematical Programming 48 (1990) 221–229. · Zbl 0728.90084 · doi:10.1007/BF01582256 [45] S.M. Robinson, Newton’s method for a class of nonsmooth functions,Set Valued Analysis 2 (1994) 291–305. · Zbl 0804.65062 · doi:10.1007/BF01027107 [46] R.T. Rockafellar, Computational schemes for large-scale problems in extended linear quadratic programming,Mathematical Programming 48 (1990) 447–474. · Zbl 0735.90050 · doi:10.1007/BF01582268 [47] R.T. Rockafellar and R.J.-B. Wets, A Lagrangian finite-generation technique for solving linear-quadratic problems in stochastic programming,Mathematical Programming Study 28 (1986) 63–93. · Zbl 0599.90090 · doi:10.1007/BFb0121126 [48] P.K. Subramanian, Gauss-Newton methods for the complementarity problem,Journal of Optimization Theory and Applications 77 (1993) 467–482. · Zbl 0792.90082 · doi:10.1007/BF00940445 [49] P. Tseng, Growth behaviour of a class of merit functions for the nonlinear complementarity problem,Journal of Optimization Theory and Applications 89 (1996) 17–37. · Zbl 0866.90127 · doi:10.1007/BF02192639 [50] P. Tseng, An infeasible path-following method for monotone complementarity problem,SIAM Journal on Optimization, to appear. [51] P. Tseng, N. Yamashita and M. Fukushima, Equivalence of complementarity problems to differentiable minimization: A unified approach,SIAM Journal on Optimization, to appear. [52] N. Yamashita and M. Fukushima, On stationary points of the implicit Lagrangian for nonlinear complementarity problems,Journal of Optimization Theory and Applications 84 (1995) 653–663. · Zbl 0824.90131 · doi:10.1007/BF02191990