Utilize este identificador para referenciar este registo:
https://hdl.handle.net/10316/29109
Título: | Trust-Region Methods without using Derivatives: Worst-Case Complexity and the Non-Smooth Case | Autor: | Júdice, Diogo Corte Real Alarcão | Orientador: | Vicente, Luís Nunes | Palavras-chave: | Optimização sem Derivadas | Data: | 9-Dez-2015 | Citação: | JÚDICE, Diogo Corte Real Alarcão - Trust-region methods without using derivatives : worst-case complexity and the non-smooth case. Coimbra : [s.n.], 2015. Tese de doutoramento. Disponível na WWW: http://hdl.handle.net/10316/29109 | Resumo: | 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. |
Descrição: | Tese de doutoramento em Programa de Doutoramento em Matemática, apresentada ao Departamento de Matemática da Faculdade de Ciências e Tecnologia da Universidade de Coimbra | URI: | https://hdl.handle.net/10316/29109 | Direitos: | openAccess |
Aparece nas coleções: | FCTUC Matemática - Teses de Doutoramento |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
Trust-Region Methods without using Derivatives.pdf | 850.61 kB | Adobe PDF | Ver/Abrir |
Visualizações de página 20
781
Visto em 27/ago/2024
Downloads
259
Visto em 27/ago/2024
Google ScholarTM
Verificar
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.