New versions of Newton method: step-size choice, convergence domain and under-determined equations

DOI10.1080/10556788.2019.1669154zbMATH Open1464.90112OpenAlexW2977911200WikidataQ127179329 ScholiaQ127179329MaRDI QIDQ5859005FDOQ5859005

Authors A. A. Tremba, Boris T. Polyak

Publication date 15 April 2021

Published in Optimization Methods \& Software (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1703.07810

zbMATH Keywords

global convergencemetric regularitynonlinear equationsadaptive algorithmsNewton methodunder-determined equations

Mathematics Subject Classification ID

Nonlinear programming (90C30) Methods of quasi-Newton type (90C53) Numerical computation of solutions to systems of equations (65H10) Implicit function theorems; global Newton methods on manifolds (58C15)

Abstract: Newton method is one of the most powerful methods for finding solutions of nonlinear equations and for proving their existence. In its "pure" form it has fast convergence near the solution, but small convergence domain. On the other hand damped Newton method has slower convergence rate, but weaker conditions on the initial point. We provide new versions of Newton-like algorithms, resulting in combinations of Newton and damped Newton method with special step-size choice, and estimate its convergence domain. Under some assumptions the convergence is global. Explicit complexity results are also addressed. The adaptive version of the algorithm (with no a priori constants knowledge) is presented. The method is applicable for under-determined equations (with $m<n$, $m$ being the number of equations and $n$ being the number of variables). The results are specified for systems of quadratic equations, for composite mappings and for one-dimensional equations and inequalities.

Recommendations

• A Newton method for systems of \(m\) equations in \(n\) variables.
• Newton-like methods for solving underdetermined nonlinear equations with nondifferentiable terms
• Newton's Method for Underdetermined Systems of Equations Under the γ-Condition
• The theory of Newton's method
• scientific article; zbMATH DE number 3921835

Cites work

• scientific article; zbMATH DE number 4141412 (Why is no real title available?)
• scientific article; zbMATH DE number 3738816 (Why is no real title available?)
• scientific article; zbMATH DE number 3760758 (Why is no real title available?)
• scientific article; zbMATH DE number 729680 (Why is no real title available?)
• scientific article; zbMATH DE number 2104353 (Why is no real title available?)
• scientific article; zbMATH DE number 852532 (Why is no real title available?)
• scientific article; zbMATH DE number 967073 (Why is no real title available?)
• A Gauss-Newton Approach to Solving Generalized Inequalities
• A Kantorovich-type convergence analysis for the Gauss-Newton-method
• A Newton method for systems of \(m\) equations in \(n\) variables.
• A Newton-Raphson method for the solution of systems of equations
• A Rapidly Convergent Descent Method for Minimization
• Analysis and implementation of a dual algorithm for constrained optimization
• Convergence of Newton-like methods for singular operator equations using outer inverses
• Convexity of nonlinear image of a small ball with applications to optimization
• Convexity of quadratic transformations and its use in control and optimization
• Extension of Newton's method to nonlinear functions with values in a cone
• Gradient methods for solving equations and inequalities
• Historical developments in convergence analysis for Newton's and Newton-like methods
• Implicit Functions and Solution Mappings
• Iterative Solution of Nonlinear Equations in Several Variables
• Modified Gauss–Newton scheme with worst case guarantees for global performance
• Newton's method for the solution of systems of equalities and inequalities
• Newton's method, differential equations, and the Lagrangian principle for necessary extremum conditions
• Newton-Kantorovich method and its global convergence
• On local convexity of quadratic transformations
• On the existence of solutions to nonlinear equations involving singular mappings with non-zero \(p\)-kernel
• Solving Nonlinear Equations with Newton's Method
• Some mapping theorems
• Sparse solutions of optimal control via Newton method for under-determined systems
• Variational analysis of regular mappings. Theory and applications

Cited in

(11)

• On the redundancy of Hessian nonsingularity for linear convergence rate of the Newton method applied to the minimization of convex functions
• A Bregman–Kaczmarz method for nonlinear systems of equations
• Investigation of feasible and marginal operating regimes of electric power systems
• Some properties of smooth convex functions and Newton's method
• A Newton method for systems of \(m\) equations in \(n\) variables.
• A short note on an adaptive damped Newton method for strongly monotone and Lipschitz continuous operator equations
• Stopping rules for gradient methods for non-convex problems with additive noise in gradient
• Improvements to the cluster Newton method for underdetermined inverse problems
• Distributed adaptive greedy quasi-Newton methods with explicit non-asymptotic convergence bounds
• A modified PRP-type derivative-free projection algorithm for constrained nonlinear equations with applications
• Error bound conditions and convergence of optimization methods on smooth and proximally smooth manifolds

Describes a project that uses

Uses Software

• NewtonLib

This page was built for publication: New versions of Newton method: step-size choice, convergence domain and under-determined equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5859005)