Métodos de região de confiança sem derivadas para otimização restrita

Abstract

Resumo: Otimização sem derivadas tem sido de grande interesse nos últimos anos, principalmente pela necessidade em se resolver problemas definidos por funções cujos valores sao calculados por simulaçao. Muitos metodos sem derivadas para problemas restritos ja foram desenvolvidos, alguns baseados em regiao de confianca, com bons resultados numericos. Metodos de região de confianca sem derivadas para o caso irrestrito tem consagradas provas de convergencia. No entanto, para o caso restrito, ate onde sabemos nao ha na literatura resultados teóricos de convergencia. Nesta tese apresentamos dois algoritmos sem derivadas para o problema de otimização não linear com restrições. O primeiro algoritmo é baseado em região de confiança sem derivadas aplicado a problemas com restricoes convexas. Em cada iteracao e construído um modelo quadrútico da função objetivo que deve ser minimizado na intersecção da regiao de confiança com o conjunto viavel. Com hipoteses razoaveis em otimizacao sem derivadas, provamos que todo ponto de acumulaçao da sequencia gerada pelo algoritmo e estacionário de primeira ordem. O segundo algoritmo úe desenvolvido e aplicado a problemas com restricoes gerais. Tambem com a estrutura de regiao de confianca, o algoritmo e baseado em interpolacão polinomial e utiliza ideias propostas por Michael Powell nas atualizações dos modelos. Experimentos numericos mostram a eficiencia e robustez do algoritmo proposto, cuja complexidade algorítmica em numero de operacoes permite resolver problemas de grandes dimensões quando tratamos de otimizacao sem derivadas.

Abstract: In this work we discuss trust-region derivative-free algorithms for constrained problems. In the first part of the work we propose a trust-region algorithm for the problem of minimizing a function within a convex closed domain. We assume that the objective function is differentiable but no derivatives are available. The algorithm has a very simple structure and allows a great deal of freedom in the choice of the models. Under reasonable assumptions for derivative-free schemes, we prove global convergence, that is to say, that all accumulation points of the sequence generated by the algorithm are stationary. In the second part we develop a trust-region derivative-free algorithm for problems with general constraints. The models are constructed by polynomial interpolation and updated using ideas proposed by Powell in his many works on this subject. Numerical experiments show the efficiency and robustness of the algorithm, whose good performance allows to solve problems considered large in the context of derivative-free optimization.