[en] ITERATIVE METHODS FOR LINEAR COMPLEMENTARITY PROBLEMS AND LEAST NORM - JOSE MARCOS LOPES (2006)
[pt] Apresentamos nesta dissertação novos métodos interativos para resolver o Problema de Complementaridade Linear (PCL) e Problemas de Norma Mínima. Após uma revisão geral sobre métodos interativos para o PCL, apresentaremos no Capítulo 2, uma forma de aceleração aplicada a métodos clássicos para o PCL simétrico, através de uma decomposição (Splitting) conveniente da matriz associada ao problema. A aceleração para os novos métodos consiste em calcular uma direção de avanço usando o método básico mais uma minimização unidimensional que respeite as condições de não negatividade, provas de convergência forte são apresentadas. No Capítulo 3 comparamos algoritmos do tipo seqüencial e paralelo para solução de um Problema de Programação Linear e Problemas de Norma Mínima em l 1: para o segundo problema os métodos iterativos são aplicados no dual do problema original penalizado com um termo quadrático. Introduzimos um novo método paralelo para o Problema de Norma mínima em l 1 e provamos sua convergência. Propomos no capítulo 4, novos métodos iterativos paralelos para Problemas de Norma Mínima, convenientes para problemas de grande porte, provas de convergência são fornecidas. Finalmente, no capítulo 5 baseados sobre uma combinação da iteração de ponto proximal e métodos iterativos clássicos, propomos novos métodos iterativos para a solução de um PCL monótono não simétrico. Ilustramos todos os algoritmos apresentados, em diferentes versões, com um extensa experimentação numérica.