A Fast and Simple Modification of Newton’s Method Avoiding Saddle Points

Tuyen Trung Truong (), Tat Dat To (), Hang-Tuan Nguyen (), Thu Hang Nguyen (), Hoang Phuong Nguyen () and Maged Helmy ()
Additional contact information
Tuyen Trung Truong: University of Oslo
Tat Dat To: Ecole Nationale de l’Aviation Civile
Hang-Tuan Nguyen: Axon AI Research
Thu Hang Nguyen: Torus Actions SAS
Hoang Phuong Nguyen: Torus Actions SAS
Maged Helmy: University of Oslo

Journal of Optimization Theory and Applications, 2023, vol. 199, issue 2, No 14, 805-830

Abstract: Abstract We propose in this paper New Q-Newton’s method. The update rule is conceptually very simple, using the projections to the vector subspaces generated by eigenvectors of positive (correspondingly negative) eigenvalues of the Hessian. The main result of this paper roughly says that if a sequence $$\{x_n\}$$ { x n } constructed by the method from a random initial point $$x_0$$ x 0 converges, then the limit point is a critical point and not a saddle point, and the convergence rate is the same as that of Newton’s method. A subsequent work has recently been successful incorporating Backtracking line search to New Q-Newton’s method, thus resolving the global convergence issue observed for some (non-smooth) functions. An application to quickly find zeros of a univariate meromorphic function is discussed, accompanied with an illustration on basins of attraction.

Keywords: Backtracking line search; Newton-type method; Rate of convergence; Roots of univariate meromorphic functions; Saddle points; 37N40; 49M15; 49M37; 65Exx; 65Hxx; 65K05; 90C26 (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-023-02270-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:199:y:2023:i:2:d:10.1007_s10957-023-02270-9

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-023-02270-9

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().