Search

Orientadores: Sandra Augusta Santos, Maria Aparecida Diniz Ehrhardt Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica Resumo: Neste trabalho propusemos o algoritmo PSIFA, do inglês Pattern Search and Implicit Filtering Algorithm, que é um algoritmo sem derivadas desenvolvido para resolver problemas de otimização com restrições lineares e ruído na função objetivo, e que combina elementos do método de busca padrão de Lewis e Torczon (2000) e do método de filtragem implícita de Kelley (2011). Apresentamos a teoria de convergência global para o método, com enfraquecimento de hipóteses, a qual engloba o caso degenerado. Realizamos experimentos numéricos com problemas da literatura e problemas com restrições lineares degeneradas, obtidos definindo o conjunto viável a partir de cones poliedrais 3D com diversos graus de degeneração na solução. O algoritmo também foi testado com uma função objetivo cujo ruído não satisfaz as hipóteses teóricas de convergência do método. Como uma aplicação com ruído inerente foi abordado um problema de identificação de parâmetros, para o qual restrições lineares podem ser consideradas na formulação do problema. Os resultados obtidos pelo PSIFA em todos os experimentos foram comparados com os dos métodos de busca padrão e filtragem implícita, sendo o desempenho da nossa proposta bastante promissor em todas as instâncias testadas Abstract: In this work we have introduced the algorithm PSIFA - Pattern Search and Implicit Filtering Algorithm - which is a derivative-free algorithm that has been designed for linearly constrained problems with noise in the objective function, combining some elements of the pattern search approach of Lewis and Torczon (2000) with ideas from the method of implicit filtering of Kelley (2011). The global convergence analysis is presented, encompassing the degenerate case, under mild assumptions. Numerical experiments with linearly constrained problems from the literature and also with the feasible set defined by polyhedral 3D-cones with several degrees of degeneration at the solution were performed, including noisy functions that are not covered by the theoretical hypotheses. Furthermore, an instance of a parameter identification problem was considered as an application with inherent noise on the objective function for which linear constraints are present in the model. To put PSIFA in perspective, comparative tests with the Pattern Search and the Implicit Filtering algorithms have been prepared, with encouraging results Doutorado Matemática Aplicada Doutora em Matemática Aplicada FAPESP 2013/12964-4