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

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

Boris T. Polyak, A. A. Tremba

Publication date: 15 April 2021

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

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.

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)

Cites Work

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

Cited In (9)

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

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)