Newton-type Methods
by Titus Pinta
Date of Examination:2024-09-23
Date of issue:2025-09-17
Advisor:Prof. Dr. Russell Luke
Referee:Prof. Dr. Russell Luke
Referee:Prof. Dr. Max Wardetzky
Persistent Address:
http://dx.doi.org/10.53846/goediss-11505
Files in this item
Name:Newton-type Methods (eDiss).pdf
Size:759.Kb
Format:PDF
The following license files are associated with this item:
Abstract
English
Newton’s method has long been enjoying its position as the algorithm of choice for solving nonlinear equations and unconstrained optimization problems. In classical Euclidean settings, under strong smoothness assumptions, the local quadratic convergence has allowed for a reduced number of oracle calls. This efficiency has made Newton’s method the default option for engineers, economists, physicists, chemists, and other scientists whenever they require fitting a model to the available data. This thesis builds on this well established method by extending it to different contexts and by relaxing the traditional smoothness assumptions. This work covers a large array of topics, such as nonsmooth analysis, metric analysis, stochastic analysis, and algorithms for constrained optimization. The approach taken consists in framing all our results in the general language of Newton differentiability. This allows us to generalize numerous known results to a large class of nonsmooth objectives, and to derive linear and superlinear convergence results. The general setting of quasi-metric spaces provides the background for our fixed point convergence existence results, while the more structured setting of Euclidean spaces allows us to frame our work in the broader context of nonsmooth analysis. The analysis of first order methods led to the development of Kurdyka-Łojasiewicz inequalities. An interest in quantifying the regularity of generalized derivatives led to the introduction of metric regularity and sub-regularity. Our Newton differentiability approach manages to bring these similar ideas under the same roof. The notion of Newton differentiability helps us unify the analysis of numerous related methods, such as quasi-Newton and the chord method. All these methods have been introduced in order to ameliorate the computational drawbacks of inverting a possibly dense matrix at every iteration. Our framework helps to guarantee that, as long as the computational shortcuts are not too severe, the fast convergence behavior of Newton’s method can be recovered. Another difficulty encountered in practical implementation is the existence of random noise. Using the techniques of stochastic analysis, we establish a general Newton-type algorithmic framework. As many other aspects of analysis, Newton’s method can be easily lifted to the setting of Riemannian manifolds, thus providing a fast and well understood algorithm for constrained optimization. The hindrance to this approach lies in the difficult computation of geometric objects, thus in the last century, Sequential Quadratic Programming, has been the Newton-type workhorse of constrained optimization. This work develops a new method for constrained optimization. Our approach, though also stemming from the traditional Newton’s method, will differ conceptually, but not so much computationally from Sequential Quadratic Programming. Because feasibility problems can be seen as systems of equations, we can employ an operator splitting approach to create an algorithm for constrained optimization.
Keywords: Newton-type Methods; Non-smooth Optimization; Constrained Optimization; Stochastic Optimization; Optimization in Non-linear Spaces
