Acceleration of optimization algorithms

Abstract

El trabajo de tesis est´a enfocado en el estudio de la convergencia y desempe˜no de algoritmos de optimizaci´on combinando mecanismos de aceleraci´on y estabilizaci´on. En particular, nos enfocamos en dos t´ecnicas: un esquema de reinicio para una din´amica continua, y la inclusi´on de inercia en iteraciones de Krasnoselskii-Mann. El cap´ıtulo 2 presenta un resultado sobre la convergencia de esquema de reinicio para funci´on convexa a trav´es de las soluciones de una ecuaci´on diferencial con amortiguamiento definido por la curvatura. Esta din´amica en particular puede ser interpretada como la versi´on continua del m´etodo acelerado de Nesterov con un t´ermino que depende del Hessiano de una funci´on convexa. La inclusi´on del t´ermino de segundo orden muestra, en la pr´actica, una reducci´on en las oscilaciones de los valores de la funci´on, resultando en una convergencia m´as estable. Los resultados obtenidos en este cap´ıtulo pueden ser vistos como una extensi´on del esquema de reinicio propuesto por Su, Boyd y Cand`es en [83]. Se presentan tambi´en experimentos num´ericos, mostrando el desempe˜no del esquema de reinicio, en su versi´on continua y sus consecuencias algor´ıtmicas, y un teorema de existencia para las soluciones de la ecuaci´on diferencial. El cap´ıtulo 3 se enfoca en la inclusi´on de inercia en iteraciones del tipo KrasnoselskiiMann (KM), gobernadas por una familia de operadores quasi-no expansivos sobre un espacio de Hilbert. Las iteraciones KM pueden ser vistas como una versi´on relajada de las iteraciones de Banach-Picard, y bajo hip´otesis habituales, convergen a un punto fijo en com´un para la familia de operadores. Las iteraciones de punto fijo juegan un importante rol al definir algoritmos de optimizaci´on para una variada gama de problemas. En particular, se presentan resultados sobre la convergencia d´ebil de las iteraciones hacia el punto fijo, junto con estimaciones para la tasa de convergencia no asint´otica para los residuos. Se obtienen resultados sobre convergencia fuerte y lineal en el caso quasi-contractante, y se presentan simulaciones num´ericas para versiones inerciales de un algoritmo primal dual y otro gobernado por tres operadores. En ambos casos, se observan mejoras en el desempe˜no con respecto a sus contrapartes no inerciales. Este cap´ıtulo tambi´en presenta resultados de una investigaci´on en curso sobre el problema de estimaci´on de desempe˜no (PEP) para iteraciones KM inerciales, lo cual nos lleva a conjeturar sobre las tasas de convergencia.

This thesis is focused on studying the convergence and performance of optimization algorithms combining acceleration and stabilization mechanisms. In particular, we focus on two techniques: a restart scheme for a continuous dynamics, and the inclusion of inertia on Krasnoselskii-Mann iterations. Chapter 2 contains a result on the convergence of a restarting scheme for a convex function through the solution trajectories of a differential equation with curvature-defined damping. This particular dynamics can be interpreted as the continuous setting for Nesterov’s accelerated method with a term that depends on the Hessian of the convex function. The inclusion of the Hessian term shows, in practice, a reduction in the oscillations of the values of the function, leading to a more stable convergence. The results displayed on this chapter can be interpreted as an extension of the restart scheme proposed by Su, Boyd and Cand`es in [83]. Numerical experiments are displayed, showing the performance of the restart routine both in the continuous setting and its algorithmic consequences, and an existence theorem for the solutions of the differential equation. Chapter 3 focuses on the inclusion of inertia on Krasnoselskii-Mann iterations, governed by a family of quasi-nonexpansive operators defined over a Hilbert space. Krasnoselskii-Mann iterations can be seen as a relaxed setting for Banach-Picard iterations, and under standard hypotheses, they converge towards a common fixed point of the family of operators. Fixed point iterations play a central role on defining optimization algorithms for a wide range of problems. In particular, we provide results on the weak convergence of KM iterations towards a common fixed point of the famility of operators, along with estimates for the nonasymptotic rate at which the residuals vanish. Strong and linear convergence are obtained in the quasi-contractive setting, and numerical illustrations are displayed for an inertial primaldual method and an inertial three-operator splitting algorithm, whose performance is superior to that of their non-inertial counterparts. Also this chapter presents some results of an ongoing research about the performance estimation problem (PEP) for inertial KM iterations, leading us to conjecture about rates of convergence.