Mathematics of Operations Research · 1990 · 352 citations · 12 references
Natural SciencesMathematicsAlgorithmsComputational MechanicsOptimizationGlobal OptimizationGradient-based OptimizationNonlinear ProgrammingVariational FormulationVariational InequalitiesConvergenceDescentEquation FormulationNewton ConvergenceNonlinear Complementarity ProblemsNonlinear OptimizationVariational Inequality ProblemsVariational Inequality Theory
Such B‑differentiable systems of equations provide a unified framework for nonlinear complementarity, variational inequality, and nonlinear programming problems. The paper extends the classical Newton method to B‑differentiable systems, establishes local quadratic convergence, proposes a modification for global convergence, and outlines applications to complementarity, variational inequality, and optimization. The method incorporates an active‑set strategy to define subproblems, thereby extending Newton’s algorithm to B‑differentiable systems. The extended method achieves local quadratic convergence, offers a computational advantage over Robinson‑based Newton methods, and the modified version yields a globally convergent descent algorithm under mild assumptions.
In this paper, we extend the classical Newton method for solving continuously differentiable systems of nonlinear equations to B-differentiable systems. Such B-differentiable systems of equations provide a unified framework for the nonlinear complementarity, variational inequality and nonlinear programming problems. We establish the local and quadratic convergence of the method and propose a modification for global convergence. Applications of the theory to complementarity, variational inequality and optimization will be explained. In each of these contexts, the resulting method resembles the known Newton methods derived from Robinson's generalized equation formulation, but with a computational advantage. Namely, the new method incorporates a kind of active-set strategy in defining the subproblems. Unlike the previous methods which are only locally convergent, the modified version of the new method provides a descent algorithm which is globally convergent under some mild assumptions.
12
Ron S. Dembo, Stanley C. Eisenstat, Trond Steihaug · SIAM Journal on Numerical Analysis · 1982 · 1.6K citations