zbMATH — the first resource for mathematics

A B-differentiable equation-based, globally and locally quadratically convergent algorithm for nonlinear programs, complementarity and variational inequality problems. (English) Zbl 0733.90063
This paper presents a globally convergent, locally quadratically convergent algorithm for solving general nonlinear programs, nonlinear complementarity and variational inequality problems. The algorithm is based on a unified formulation of these three mathematical programming problems as a certain system of B-differentiable equations, and is a modification of the damped Newton method proposed by the author in another paper for solving such a system of nonsmooth equations. The algorithm resembles some existing methods to solve these classes of mathematical programs, but has its own features; in particular, it possesses the combined advantage of a fast quadratic rate of convergence of a basic Newton method and the desirable global convergence induced by one-dimensional Armijo line searches.
In the context of a nonlinear program, the algorithm is of the sequential quadratic programming type with two distinct characteristics: (1) it makes no use of a penalty function; (2) it circumvents the Maratos effect. In the context of the variational inequality/complementarity problem, the algorithm provides a Newton-type descent method that is guaranteed globally convergent without requiring the F-differentiability assumption of the defining B-differentiable equations.

90C30 Nonlinear programming
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
49J40 Variational inequalities
49J52 Nonsmooth analysis
90-08 Computational methods for problems pertaining to operations research and mathematical programming
Full Text: DOI
[1] D.P. Bertsekas,Constrained Optimization and Lagrange Multiplier Methods (Academic Press, New York, 1982). · Zbl 0572.90067
[2] R.W. Cottle, ”Manifestations of the Schur complement,”Linear Algebra and its Applications 8 (1974) 189–211. · Zbl 0284.15005
[3] R. Fletcher,Practical Methods of Optimization (Wiley, New York, 1987, 2nd ed.). · Zbl 0905.65002
[4] P.T. Harker and J.S. Pang, ”Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications,”Mathematical Programming (Series B) 48 (1990) 161–220. · Zbl 0734.90098
[5] P.T. Harker and J.S. Pang, ”A damped-Newton method for the linear complementarity problem,” in: E.L. Allgower and K. Georg, eds.,Computational Solution of Nonlinear Systems of Equations. Lectures in Applied Mathematics No. 26 (American Mathematical Society, Providence, RI, 1990) pp. 265–284. · Zbl 0699.65054
[6] P.T. Harker and B. Xiao, ”Newton’s method for the nonlinear complementarity problem: a B-differentiable equation approach,”Mathematical Programming (Series B) 48 (1990) 339–358. · Zbl 0724.90071
[7] N.H. Josephy, ”Newton’s method for generalized equation,” Technical summary report 1965, Mathematics Research Center, University of Wisconsin-Madison (Madison, WI, 1979).
[8] N. Maratos, ”Exact penalty function algorithms for finite dimensional and control optimization problems,” Ph.D. thesis, University of London (London, 1978).
[9] G.P. McCormick,Nonlinear Programming: Theory, Algorithms, and Applications (Wiley, New York, 1983). · Zbl 0563.90068
[10] K.G. Murty,Linear Complementarity, Linear and Nonlinear Programming (Helderman-Verlag, Berlin, 1988). · Zbl 0634.90037
[11] J.M. Ortega and W.C. Rheinboldt,Iterative Solution of Nonlinear Equations in Several Variables (Academic Press, New York, 1970). · Zbl 0241.65046
[12] J.S. Pang, ”Newton’s method for B-differentiable equations,”Mathematics of Operations Research 15 (1990) 331–341. · Zbl 0716.90090
[13] J.S. Pang and D. Chan, ”Iterative methods for variational and complementarity problems,”Mathematical programming 24 (1982) 284–313. · Zbl 0499.90074
[14] S.M. Robinson, ”Strongly regular generalized equations,”Mathematics of Operations Research 5 (1980) 43–62. · Zbl 0437.90094
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.