Trust-Region Methods without using Derivatives: Worst-Case Complexity and the Non-Smooth Case

Abstract

Os métodos de região de confiança formam uma classe geral de métodos para optimização contínua que encontram aplicação numa variedade de problemas e contextos. Em particular, estes métodos têm sido estudados e aplicados a problemas sem recurso a derivadas.

A análise dos métodos de região de confiança sem derivadas tem incidido em convergência global, mostrando que estes métodos geram sequências de pontos convergindo para pontos estacionários, independentemente do ponto inicial. Uma grande parte desta análise é feita no caso suave, sabendo-se pouco sobre a complexidade ou taxa global destes métodos. Nesta tese, começamos por analisar a complexidade no pior dos casos de métodos de região de confiança sem derivadas para funções suaves (recorrendo a uma modificação da metodologia geral existente), limitando o número de iterações e de avaliações de função necessárias para atingir uma determinada proximidade a estacionaridade de primeira ou segunda ordem.

Para o caso não suave, propomos uma abordagem de suavização, para a qual provamos convergência global e limitamos a complexidade no pior dos casos. Para o caso especial de funções não suaves resultantes da composicção de funções suaves com funções não suaves e convexas, mostramos como melhorar os resultados existentes na literatura utilizando a metodologia geral modificada do caso suave.

Trust-region methods are a broad class of methods for continuous optimization that found application in a variety of problems and contexts. In particular, they have been studied and applied for problems without using derivatives.

The analysis of trust-region derivative-free methods has focused on global convergence, and they have been proved to generate a sequence of iterates converging to stationarity independently of the starting point. Most of such an analysis is carried out in the smooth case, and, moreover, little is known about the complexity or global rate of these methods. In this thesis, we start by analyzing the worst case complexity of trust-region derivative-free methods for smooth functions (based on a modification of the existent general methodology), bounding the number of iterations and function evaluations to reach a certain threshold of first or second order stationarity.

For the non-smooth case, we propose a smoothing approach, for which we prove global convergence and bound the worst case complexity effort. For the special case of non-smooth functions that result of the composition of smooth and non-smooth/convex components, we show how to improve the existing results of the literature using the general modified methodology of the smooth case.

Trust-region methods are a broad class of methods for continuous optimization that found application in a variety of problems and contexts. In particular, they have been studied and applied for problems without using derivatives. The analysis of trust-region derivative-free methods has focused on global convergence, and they have been proved to generate a sequence of iterates converging to stationarity independently of the starting point. Most of such an analysis is carried out in the smooth case, and, moreover, little is known about the complexity or global rate of these methods. In this thesis, we start by analyzing the worst case complexity of trust-region derivative-free methods for smooth functions (based on a modification of the existent general methodology), bounding the number of iterations and function evaluations to reach a certain threshold of first or second order stationarity. For the non-smooth case, we propose a smoothing approach, for which we prove global convergence and bound the worst case complexity effort. For the special case of non-smooth functions that result of the composition of smooth and non-smooth/convex components, we show how to improve the existing results of the literature using the general modified methodology of the smooth case.