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)
Modified Newton methods for solving a semismooth reformulation of monotone complementarity problems. (English) Zbl 0872.90102
Summary: We propose a Newton-type method for solving a semismooth reformulation of monotone complementarity problems. In this method, a direction-finding subproblem, which is a system of linear equations, is uniquely solvable at each iteration. Moreover, the obtained search direction always affords a direction of sufficient decrease for the merit function defined as the squared residual for the semismooth equation equivalent to the complementarity problem. We show that the algorithm is globally convergent under some mild assumptions. Next, by slightly modifying the direction-finding problem, we propose another Newton-type method, which may be considered a restricted version of the first algorithm. We show that this algorithm has a superlinear, or possibly quadratic, rate of convergence under suitable assumptions. Finally, some numerical results are presented.
MSC:
90C33Complementarity and equilibrium problems; variational inequalities (finite dimensions)
90C30Nonlinear programming
References:
[1]F.H. Clarke,Optimization and Nonsmooth Analysis (Wiley, New York, 1983).
[2]R.W. Cottle, J.-S. Pang and R.E. Stone,The Linear Complementarity Problem (Academic, Boston, MA, 1992).
[3]T. De Luca, F. Facchinei and C. Kanzow, A semismooth equation approach to the solution of nonlinear complementarity problems,Mathematical Programming 75 (1996) 407–439.
[4]F. Facchinei and C. Kanzow, A nonsmooth inexact Newton method for the solution of large-scale nonlinear complementarity problems,Mathematical Programming 76 (1997) 493–512 (this issue).
[5]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
[6]A. Fischer, A special Newton-type optimization method,Optimization 24 (1992) 269–284. · Zbl 0814.65063 · doi:10.1080/02331939208843795
[7]A. Fischer, On the local superlinear convergence of a Newton-type method for LCP under weak conditions.Optimization Methods and Software 6 (1995) 83–107. · doi:10.1080/10556789508805627
[8]A. Fischer, An NCP-function and its use for the solution of complementarity problems, in: D.-Z. Du, L. Qi and R.S. Wormersley, eds.,Recent Advances in Nonsmooth Optimization (World Scientific, Singapore, 1995) 88–105.
[9]C. Geiger and C. Kanzow, On the resolution of monotone complementarity problems,Computational Optimization and Application 5 (1996) 155–173. · Zbl 0859.90113 · doi:10.1007/BF00249054
[10]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 · doi:10.1007/BF01582255
[11]W. Hock and K. Schittkowski,Test Examples for Nonlinear Programming Codes (Springer, Berlin, 1981).
[12]W.W. Hogan, Point-to-set maps in mathematical programming.SIAM Review 15 (1973) 591–603. · Zbl 0256.90042 · doi:10.1137/1015073
[13]G. Isac,Complementarity Problems (Springer, Berlin. 1992).
[14]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
[15]C. Kanzow, Nonlinear complementarity as unconstrained optimization,Journal of Optimization Theory and Applications 88 (1996) 139–155. · Zbl 0845.90120 · doi:10.1007/BF02192026
[16]C. Kanzow and H. Kleinmichel, A class of Newton type methods for equality and inequality constrained optimization,Optimization Methods and Software 5 (1995) 173–198. · doi:10.1080/10556789508805608
[17]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
[18]J.J. Moré and W.C. Rheinboldt, OnP- andS-functions and related classes ofn-dimensional nonlinear mappings,Linear Algebra and its Applications 6 (1973) 45–68. · Zbl 0247.65038 · doi:10.1016/0024-3795(73)90006-2
[19]J.M. Ortega and W.C. Rheinboldt,Iterative Solution of Nonlinear Equations in Several Variables (Academic, New York, 1970).
[20]J.-S. Pang, Complementarity problems, in: R. Horst and P. Pardalos. eds.,Handbook of Global Optimization (Kluwer Academic, Bloston, MA, 1994) 271–338.
[21]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
[22]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
[23]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
[24]L. Qi and H. Jiang, Semismooth Karush-Kuhn-Tucker equations and convergence analysis of Newton and quasi-Newton methods for solving these equations,Mathematics of Operations Research, to appear.
[25]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
[26]S.M. Robinson, Strongly regular generalized equations.Mathematics of Operations Research 5 (1980) 43–62. · Zbl 0437.90094 · doi:10.1287/moor.5.1.43
[27]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