Search

An alternative strategy to solve the subproblems of the Method of Moving Asymptotes (MMA) is presented, based on a trust-region scheme applied to the dual of the MMA subproblem. At each iteration, the objective function of the dual problem is approximated by a regularized spectral model. A globally convergent modification to the MMA is also suggested, in which the conservative condition is relaxed by means of a summable controlled forcing sequence. Another modification to the MMA previously proposed by the authors [Optim. Methods Softw., 25 (2010), pp. 883-893] is recalled to be used in the numerical tests. This modification is based on the spectral parameter for updating the MMA models, so as to improve their quality. The performed numerical experiments confirm the efficiency of the indicated modifications, especially when jointly combined.

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