Global Convergence of Damped Newton's Method for Nonsmooth Equations via the Path Search

Daniel Ralph
Daniel Ralph
Mathematics Department, University of Melbourne, Parkville, Victoria 3052, Australia
Search for more papers by this author

Mathematics Department, University of Melbourne, Parkville, Victoria 3052, Australia

Published Online:1 May 1994https://doi.org/10.1287/moor.19.2.352

Abstract

A natural damping of Newton's method for nonsmooth equations is presented. This damping, via the path search instead of the traditional line search, enlarges the domain of convergence of Newton's method and therefore is said to be globally convergent. Convergence behavior is like that of line search damped Newton's method for smooth equations, including Q-quadratic convergence rates under appropriate conditions.

Applications of the path search include damping Robinson-Newton's method for nonsmooth normal equations corresponding to nonlinear complementarity problems and variational inequalities, hence damping both Wilson's method (sequential quadratic programming) for nonlinear programming and Josephy-Newton's method for generalized equations. Computational examples from nonlinear programming are given.

Cited by
- New Methods for Parametric Optimization via Differential Equations
  8 July 2025 | SIAM Journal on Optimization, Vol. 35, No. 3
- A trust region-type normal map-based semismooth Newton method for nonsmooth nonconvex composite optimization
  22 July 2024 | Mathematical Programming, Vol. 212, No. 1-2
- A Numerical Approach to Dead-Beat Control Using Controlled Newton's Method
- Solving polynomial variational inequality problems via Lagrange multiplier expressions and Moment-SOS relaxations
  12 December 2024 | Computational Optimization and Applications, Vol. 90, No. 2
- New Generalized Derivatives for Solving Variational Inequalities Using the Nonsmooth Newton Methods
  19 October 2024 | Journal of Optimization Theory and Applications, Vol. 203, No. 3
- Optimal step length for the maximal decrease of a self-concordant function by the Newton method
  16 August 2023 | Optimization Letters, Vol. 18, No. 3
- Optimization with learning-informed differential equation constraints and its applications
  11 January 2022 | ESAIM: Control, Optimisation and Calculus of Variations, Vol. 28
- Optimal step length for the Newton method: case of self-concordant functions
  20 October 2021 | Mathematical Methods of Operations Research, Vol. 94, No. 2
- Comparison of Robust Hypothesis Tests for Fixed Sample Size and Sequential Observations
- A Global Linear and Local Superlinear (Quadratic) Inexact Non-Interior Continuation Method for Variational Inequalities Over General Closed Convex Sets
  18 March 2020 | Set-Valued and Variational Analysis, Vol. 29, No. 1
- Deflation for semismooth equations
  16 May 2019 | Optimization Methods and Software, Vol. 35, No. 6
- A Riemann solution approximation based on the zero diffusion–dispersion limit of Dafermos reformulation type problem
  30 July 2019 | Calcolo, Vol. 56, No. 3
- Self-concordant inclusions: a unified framework for path-following generalized Newton-type algorithms
  30 March 2018 | Mathematical Programming, Vol. 177, No. 1-2
- A Hybrid Inverse Problem in the Fluorescence Ultrasound Modulated Optical Tomography in the Diffusive Regime
  21 February 2019 | SIAM Journal on Applied Mathematics, Vol. 79, No. 1
- A vector forward mode of automatic differentiation for generalized derivative evaluation
  12 May 2015 | Optimization Methods and Software, Vol. 30, No. 6
- Finite purchasing power and computations of Bertrand–Nash equilibrium prices
  16 June 2015 | Computational Optimization and Applications, Vol. 62, No. 2
- MULTI-LEADER-FOLLOWER GAMES: MODELS, METHODS AND APPLICATIONS
  Journal of the Operations Research Society of Japan, Vol. 58, No. 1
- Sparse Recovery With Unknown Variance: A LASSO-Type Approach
  IEEE Transactions on Information Theory, Vol. 60, No. 7
- A geometrically implicit time-stepping method for multibody systems with intermittent contact
  28 October 2013 | The International Journal of Robotics Research, Vol. 33, No. 3
- Equations and Unconstrained Optimization
  22 January 2014
- Variational Problems: Globalization of Convergence
  22 January 2014
- On stable piecewise linearization and generalized algorithmic differentiation
  16 July 2013 | Optimization Methods and Software, Vol. 28, No. 6
- Algorithms for LCPs, NCPs and VIs
  19 June 2012
- A direct complementarity approach for the elastoplastic analysis of plane stress and plane strain structures
  28 March 2012 | International Journal for Numerical Methods in Engineering, Vol. 90, No. 7
- Distributed Computation of Equilibria in Monotone Nash Games via Iterative Regularization Techniques
  SIAM Journal on Optimization, Vol. 22, No. 4
- Implicit nonlinear complementarity: A new approach to contact dynamics
- A Nonsmooth Newton Method with Path Search and Its Use in Solving $C^{1,1}$ Programs and Semi-Infinite Problems
  SIAM Journal on Optimization, Vol. 20, No. 5
- A Stochastic Multiple-Leader Stackelberg Model: Analysis, Computation, and Application
  Victor DeMiguel,
  Huifu Xu,
  25 June 2009 | Operations Research, Vol. 57, No. 5
- On the convergence of modified Newton methods for solving equations containing a non-differentiable term
  Journal of Computational and Applied Mathematics, Vol. 231, No. 2
- Foreword: Special issue on nonlinear programming, variational inequalities, and stochastic programming
  8 August 2007 | Mathematical Programming, Vol. 117, No. 1-2
- Constraining Surface Interpolations Using Elastic Plate Bending Solutions with Applications to Geologic Folding
  1 November 2008 | Mathematical Geosciences, Vol. 41, No. 1
- Mathematical Programs with Complementarity Constraints in Function Space: C- and Strong Stationarity and a Path-Following Algorithm
  SIAM Journal on Optimization, Vol. 20, No. 2
- Globalizing a nonsmooth Newton method via nonmonotone path search
  22 April 2008 | Mathematical Methods of Operations Research, Vol. 68, No. 2
- Parametric Proximal-Point Methods
  9 May 2008 | Journal of Optimization Theory and Applications, Vol. 139, No. 1
- Smoothing Newton method for operator equations in Banach spaces
  17 June 2008 | Journal of Applied Mathematics and Computing, Vol. 28, No. 1-2
- Nondifferentiable Optimization: Newton Method
- Using EPECs to Model Bilevel Games in Restructured Electricity Markets with Locational Prices
  Xinmin Hu,
  Daniel Ralph,
  1 October 2007 | Operations Research, Vol. 55, No. 5
- Parametric Method for Global Optimization
  6 December 2006 | Journal of Optimization Theory and Applications, Vol. 130, No. 3
- A numerical study on multiple rate solutions and onset of directional instability in quasi-static frictional contact problems
  Computers & Structures, Vol. 82, No. 17-19
- Elastic–plastic and limit-state analyses of frames with softening plastic-hinge models by mathematical programming
  International Journal of Solids and Structures, Vol. 40, No. 25
- A Parametric Newton Method for Optimization Problems in Hilbert Spaces
  31 August 2006 | Numerical Functional Analysis and Optimization, Vol. 24, No. 3-4
- False Numerical Convergence in Some Generalized Newton Methods
- The Symmetric Galerkin BEM in Linear and Non-Linear Fracture Mechanics
- Steven A. Gabriel
  Top, Vol. 9, No. 1
- Nonholonomic elastoplastic analysis involving unilateral frictionless contact as a mixed complementarity problem
  Computer Methods in Applied Mechanics and Engineering, Vol. 190, No. 35-36
- HOLONOMIC SOFTENING: MODELS AND ANALYSIS *
  Mechanics of Structures and Machines, Vol. 29, No. 1
- Nondifferentiable Optimization: Newton Method
- A Complementarity Eigenproblem in the Stability Analysis of Finite Dimensional Elastic Systems with Frictional Contact
- A comparison of two algorithms for solving closed crack problems
  Engineering Fracture Mechanics, Vol. 66, No. 6
- Compressional fractures considered as contact problems and mixed complementarity problems
  Engineering Fracture Mechanics, Vol. 66, No. 3
- Complementarity problems in GAMS and the PATH solver
  Journal of Economic Dynamics and Control, Vol. 24, No. 2
- Formulating and Solving Nonlinear Programs as Mixed Complementarity Problems
- A Truly Globally Convergent Newton-Type Method for the Monotone Nonlinear Complementarity Problem
  SIAM Journal on Optimization, Vol. 10, No. 2
- Global Convergence Analysis of the Generalized Newton and Gauss-Newton Methods of the Fischer-Burmeister Equation for the Complementarity Problem
  Houyuan Jiang,
  1 August 1999 | Mathematics of Operations Research, Vol. 24, No. 3
- Time-stepping for three-dimensional rigid body dynamics
  Computer Methods in Applied Mechanics and Engineering, Vol. 177, No. 3-4
- Solutions to Affine Generalized Equations Using Proximal Mappings
  Stephen C. Billups,
  Michael C. Ferris,
  1 February 1999 | Mathematics of Operations Research, Vol. 24, No. 1
- Approximations to the Clarke Generalized Jacobians and Nonsmooth Least-Squares Minimization
- A Survey of Some Nonsmooth Equations and Smoothing Newton Methods
- Interfaces to PATH 3.0: Design, Implementation and Usage
- Metric regularity: characterizations, nonsmooth variations and successive approximation ∗
  Optimization, Vol. 46, No. 3
- Computing Wardropian equilibria in a complementarity framework
  Optimization Methods and Software, Vol. 10, No. 5
- A New Unconstrained Differentiable Merit Function for Box Constrained Variational Inequality Problems and a Damped Gauss--Newton Method
  SIAM Journal on Optimization, Vol. 9, No. 2
- A Global and Local Superlinear Continuation-Smoothing Method for P0 and R0 NCP or Monotone NCP
  SIAM Journal on Optimization, Vol. 9, No. 3
- Interfaces to PATH 3.0: Design, Implementation and Usage
  Computational Optimization and Applications, Vol. 12, No. 1-3
- Regularity Properties of a Semismooth Reformulation of Variational Inequalities
  SIAM Journal on Optimization, Vol. 8, No. 3
- Global and Superlinear Convergence of Inexact Uzawa Methods for Saddle Point Problems with Nondifferentiable Mappings
  SIAM Journal on Numerical Analysis, Vol. 35, No. 3
- Formulation and comparison of algorithms for frictional contact problems
  International Journal for Numerical Methods in Engineering, Vol. 42, No. 1
- Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities
  1 January 1998 | Mathematics of Computation, Vol. 67, No. 222
- A Hybrid Smoothing Method for Mixed Nonlinear Complementarity Problems
  Computational Optimization and Applications, Vol. 9, No. 2
- Global and Local Superlinear Convergence Analysis of Newton-Type Methods for Semismooth Equations with Smooth Least Squares
- On the convergence of an iterative method for the minimax problem
  17 February 2009 | The Journal of the Australian Mathematical Society. Series B. Applied Mathematics, Vol. 39, No. 2
- A verification method for solutions of nonsmooth equations
  Computing, Vol. 58, No. 3
- Solution of monotone complementarity problems with locally Lipschitzian functions
  Mathematical Programming, Vol. 76, No. 3
- QPCOMP: A quadratic programming based solver for mixed complementarity problems
  Mathematical Programming, Vol. 76, No. 3
- Implementation of a continuation method for normal maps
  Mathematical Programming, Vol. 76, No. 3
- Sensitivity analysis of composite piecewise smooth equations
  Mathematical Programming, Vol. 76, No. 3
- A New Merit Function For Nonlinear Complementarity Problems And A Related Algorithm
  SIAM Journal on Optimization, Vol. 7, No. 1
- A Comparison of Large Scale Mixed Complementarity Problem Solvers
- Engineering and Economic Applications of Complementarity Problems
  SIAM Review, Vol. 39, No. 4
- A New Nonsmooth Equations Approach to Nonlinear Complementarity Problems
  SIAM Journal on Control and Optimization, Vol. 35, No. 1
- A Comparison of Large Scale Mixed Complementarity Problem Solvers
  Computational Optimization and Applications, Vol. 7, No. 1
- A semismooth equation approach to the solution of nonlinear complementarity problems
  Mathematical Programming, Vol. 75, No. 3
- A pathsearch damped Newton method for computing general equilibria
  Annals of Operations Research, Vol. 68, No. 2
- A class of smoothing functions for nonlinear and mixed complementarity problems
  Computational Optimization and Applications, Vol. 5, No. 2
- Semismoothness and Superlinear Convergence in Nonsmooth Optimization and Nonsmooth Equations
- Extension of GAMS for complementarity problems arising in applied economic analysis
  Journal of Economic Dynamics and Control, Vol. 19, No. 8
- Inexact Newton methods for solving nonsmooth equations
  Journal of Computational and Applied Mathematics, Vol. 60, No. 1-2
- Strong Stability in Variational Inequalities
  SIAM Journal on Control and Optimization, Vol. 33, No. 3
- A Globally Convergent Successive Approximation Method for Severely Nonsmooth Equations
  SIAM Journal on Control and Optimization, Vol. 33, No. 2
- Trust Region Algorithms for Solving Nonsmooth Equations
  SIAM Journal on Optimization, Vol. 5, No. 1
- Complementarity Problems
- The path solver: a nommonotone stabilization scheme for mixed complementarity problems
  Optimization Methods and Software, Vol. 5, No. 2
- Nonsmooth Equations: Motivation and Algorithms
  SIAM Journal on Optimization, Vol. 3, No. 3

cover image Mathematics of Operations Research

Volume 19, Issue 2

May 1994

Pages 257-512

Article Information

Metrics

Information

Published Online:May 01, 1994

Cite as

Daniel Ralph, (1994) Global Convergence of Damped Newton's Method for Nonsmooth Equations via the Path Search. Mathematics of Operations Research 19(2):352-389.

https://doi.org/10.1287/moor.19.2.352

Keywords

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Global Convergence of Damped Newton's Method for Nonsmooth Equations via the Path Search

Abstract

Volume 19, Issue 2

Article Information

Metrics

Information

Cite as

Keywords

Sign Up for INFORMS Publications Updates and News