Orientador: José Mario Martínez Pérez

Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica

Resumo: Os problemas de otimização sem derivadas surgem de modelos para os quais as derivadas das funções e das restrições envolvidas, por alguma razão, não estão disponíveis. Os motivos variam desde usuários que não querem programar as derivadas até funções excessivamente complexas e caixas-pretas,...

Resumo: Os problemas de otimização sem derivadas surgem de modelos para os quais as derivadas das funções e das restrições envolvidas, por alguma razão, não estão disponíveis. Os motivos variam desde usuários que não querem programar as derivadas até funções excessivamente complexas e caixas-pretas, oriundas de simulações só possíveis graças ao crescimento na capacidade de processamento dos computadores. Acompanhando esse crescimento, o número de algoritmos para resolver problemas de otimização sem derivadas aumentou nos últimos anos. Porém, poucos são aqueles que conseguem lidar de forma eficiente com problemas cujos domínios são magros, como, por exemplo, quando há restrições de igualdade. Neste trabalho, apresentamos a teoria e implementação de dois algoritmos capazes de trabalhar com domínios magros em problemas de otimização sem derivadas. Ambos partem da premissa de que a parte mais custosa na resolução é a avaliação da função objetivo. Com isso em mente, o processo de resolução é dividido em duas fases. Na fase de restauração, buscamos por pontos menos inviáveis sem utilizar avaliações da função objetivo. Na fase de minimização, ou otimização, o objetivo é reduzir a função objetivo com o uso de algoritmos bem estabelecidos para problemas sem derivadas com restrições simples. O primeiro algoritmo utiliza ideias de Restauração Inexata associadas a uma tolerância decrescente à inviabilidade. Utilizando hipóteses simples e usuais dos métodos de busca direta direcional, mostramos propriedades de convergência a minimizadores globais. O segundo algoritmo recupera totalmente os resultados teóricos de um algoritmo recente de Restauração Inexata com busca linear e aplica-se a problemas nos quais apenas as derivadas da função objetivo não estão disponíveis. Testes numéricos mostram as boas propriedades dos dois algoritmos, em particular quando comparados com algoritmos baseados em penalidades

Abstract: Derivative-free optimization problems arise from models whose derivatives of some functions are not available. This information is unavailable due to extremely complex and black-box functions, originated from simulation procedures, or even to user inability. Following the growth in the...

Abstract: Derivative-free optimization problems arise from models whose derivatives of some functions are not available. This information is unavailable due to extremely complex and black-box functions, originated from simulation procedures, or even to user inability. Following the growth in the number of applications, the number of derivative-free algorithms has increased in the last years. However, few algorithms are able to handle thin feasible domains efficiently, for example, in the presence of equality nonlinear constraints. In the present work, we describe the theory and implementation of two algorithms capable of dealing with thin-constrained derivative-free problems. Their definition considers that the objective function evaluation is the most expensive part of the problem. Based on this principle, the process of solving a problem is split into two phases. In the restoration phase, we try to improve the feasibility without evaluating the objective function. In the minimization phase, the aim is to decrease the objective function value by using well-established algorithms in order to solve derivative-free problems with simple constraints. The _rst algorithm uses Inexact Restoration ideas together with a decreasing infeasibility tolerance. Under the usual hypotheses of direct search methods, we show global minimization results. The second algorithm extends to the derivative-free case all the theoretical results obtained in a recent line-search Inexact Restoration algorithm. In this approach, only the derivatives of the objective function are not available. We perform numerical experiments to show the advantages of each algorithm, in particular when comparing with penalty-like algorithms