[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. / [en] We present in this dissertation new iterative methods for
solving Linear Complementarity (LCP) and Least Norm (LNP)
Problems. After a general overview on iterative methods
for the LCP, in chapter 2 we present an acceleration
techinique applied to classic methods for symmetric LCP
generated by considering appropriate splittings of the
associated matrix. The acceleration gives rise to new
methods consisting of computing a search direction using
the basic method plus a one dimensional minimization
taking into account the nonnegative constraints. Strong
convergence proofs are given.
In chapter 3 we compare sequential and parallel algorithms
for solving Linear Programming and least 1-Norm Problems
obtained by applying iterative methods to a dual of the
original problem penalized with a quadratic term. We
introduce a new parallel method for the Least 1-Norm
Problem, proving its convergence.
In chapter 4, we present new parallel iterative methods
for solving large LNP, giving convergence proofs.
Finally, in chapter 5 we propose new iterative methods for
solving monotone nonsymmetric LCp based on a combination
of proximal point iterations and classic iterative methods.
All the algorithms, in their different versions are
illustrated and compared through many numerical
experiments.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:8250 |
| Date | 04 May 2006 |
| Creators | JOSE MARCOS LOPES |
| Contributors | ALVARO R DE PIERRO |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.0167 seconds