Um algoritmo de filtro globalmente convergente sem derivadas da função objetivo para otimização restrita e algoritmos de pivotamento em blocos principais para problemas de complementaridade linear

Abstract

Resumo: Este trabalho engloba dois temas diferentes. Inicialmente, apresentamos um algoritmo para resolver problemas de otimizacao restrita que não faz uso das derivadas da funcao objetivo. O algoritmo mescla conceitos de restauração inexata com técnicas de filtro. Cada interação é decomposta em duas fases: uma fase de viabilidade e uma fase de otimalidade, as quais visam reduzir os valores da medida de inviabilidade e da funcao objetivo, respectivamente. A fase de otimalidade é computada por interações internas de região de confiança sem derivadas, sendo que seus modelos podem ser construídos por qualquer técnica, contanto que sejam aproximaçoes razoável para a função objetivo em torno do ponto corrente. Assumindo esta, e hipóteses clássicas, provamos que o algoritmo satisfaz certa condição de eficiência, a qual implica sua convergência global. Para a análise prática, são apresentados alguns resultados numéricos. O segundo tema refere-se a problemas de complementaridade linear. Nesta parte são discutidos alguns algoritmos de pivotamento em blocos principais, eficientes para solucionar este tipo de problema. Uma análise sobre algumas técnicas para garantia de convergência desses algoritmos _e realizada. Apresentamos alguns resultados numéricos para comparar a eficiencia e a robustez dos algoritmos discutidos. Além disso, são apresentadas duas aplicações para o método de pivotamento em blocos principais: decomposição em matrizes não negativas e métodos de gradiente projetados precondicionado. Para finalizar, nesta segunda aplicação, sugerimos uma matriz de precondicionamento.

Abstract: This work covers two diferent subjects. First we present an algorithm for solving constrained optimization problems that does not make explicit use of the objective function derivatives. The algorithm mixes an inexact restoration framework with filter techniques. Each iteration is decomposed in two phases: a feasibility phase that reduces an infeasibility measure; and an optimality phase that reduces the objective function value. The optimality step is computed by derivative-free trust-region internal iterations, where the models can be constructed by any technique, provided that they are reasonable approximations of the objective function around the current point. Assuming that this and classical hypotheses hold, we prove that the algorithm satisfes an eficiency condition, which provides its global convergence. Preliminar numerical results are presented. In the second subject, we discuss the linear complementarity problem. Some block principal pivoting algorithms, eficient for solving this kind of problem, are discussed. An analysis of some techniques to guarantee convergence results of these algorithms is made. We present some numerical results to compare the eficiency and the robustness of the algorithms. Moreover we discuss two applications of the block principal pivoting: nonnegative matrix factorization and preconditioned projected gradient methods. Furthermore, in this second application, we suggest a preconditioning matrix.