New second-order and tensor methods in convex optimization

In the recent years, we can see that the interest for new optimization methods keeps growing. The modern problems are usually ill-conditioned and high-dimensional. As a consequence, it is hard to solve them by using only the classical techniques. At the same time, the first-order or the gradient methods very often suffer from slow convergence, reaching their theoretical limitations. One of the natural ideas for improving the performance of the numerical algorithms is to use higher derivatives of the objective. The classical second-order optimization scheme is called Newton’s method. It has very fast local quadratic convergence, provided that the starting point is sufficiently close to the optimum. However, contrary to first-order algorithms, the classical Newton’s method with unit step size does not possess any global convergence guarantees in the general case. The main goal of this thesis is to develop and analyse second-order and high-order optimization methods for solving composite convex optimization problems, together with the different problem classes, for which we can establish the global iteration complexity bounds. We are interested in studying implementable algorithms with explicitly stated convergence rates, aiming to have both theoretical and practical justification of the methods.(FSA - Sciences de l'ingénieur) -- UCL, 202