Orientadores: Aurélio Ribeiro Leite de Oliveira, Marta Ines Velazco Fontova / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-18T12:49:39Z (GMT). No. of bitstreams: 1
Coelho_AlessandroFonsecaEsteves_M.pdf: 2659631 bytes, checksum: fc1bec925179612ee07a4aaef7092d8a (MD5)
Previous issue date: 2011 / Resumo: Um método frequentemente utilizado para a solução de problemas de programação linear é o método de pontos interiores. Nestes métodos precisamos resolver sistemas lineares para calcular a direção de Newton a cada iteração. A solução desses sistemas consiste no passo de maior esforço computacional nos métodos de pontos interiores. A fatoração de Cholesky é a opção mais utilizada para resolver estes sistemas. Contudo, quando trabalhamos com problemas de grande porte, esta fatoração pode ser densa e torna-se inviável trabalhar com esses métodos. Nestes casos, uma boa opção consiste no uso de métodos iterativos precondicionados. Estudos anteriores utilizam o método dos gradientes conjugados precondicionado para obter uma solução destes sistemas. Particularmente, os sistemas originados dos métodos de pontos interiores, são, naturalmente, sistemas de equações normais. Porém, a versão padrão do método dos gradientes conjugados, não considera a estrutura de equações normais do sistema. Neste trabalho propomos a utilização de duas versões do método de gradientes conjugados precondicionado que consideram a estrutura de equações normais destes sistemas. Estas versões serão comparadas com a versão de gradientes conjugados precondicionada que não considera a estrutura de equações normais do sistema. Resultados numéricos com problemas de grande porte mostram que uma dessas versões é competitiva em relação à versão padrão / Abstract: An often used method for solving linear programming problems is the interior point method. In these methods we need to solve linear systems to compute the Newton search direction at each iteration. The solution of these systems is the procedure of most computational effort in interior point methods. The Cholesky factorization is the most often used method to solve these systems. However, when dealing with large scale problems, this factorization can be dense and it become impossible to apply such methods. In such cases, a good option is the use of preconditioned iterative methods. Previous studies have used the preconditioned conjugate gradient method to find the solution of these systems. Particularly, the systems arising from interior point methods are, naturally, systems of normal equations type. Nevertheless, the standard version of the conjugate gradient method, does not take into account the normal equations system structure. This study proposes the use of two versions of preconditioned conjugate gradient method considering the normal equations structure of these systems. These versions are compared with the preconditioned conjugate gradient version that does not consider that structure. Numerical results with large scale problems show that one of these versions is competitive with the standard one / Mestrado / Matematica Aplicada / Mestre em Matemática Aplicada
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.unicamp.br:REPOSIP/306759 |
| Date | 18 August 2018 |
| Creators | Coelho, Alessandro Fonseca Esteves |
| Contributors | UNIVERSIDADE ESTADUAL DE CAMPINAS, Velazco Fontova, Marta Ines, Oliveira, Aurelio Ribeiro Leite de, 1962-, Ruggiero, Márcia Aparecida Gomes, Santos, Rubia Mara de Oliveira |
| Publisher | [s.n.], Universidade Estadual de Campinas. Instituto de Matemática, Estatística e Computação Científica, Programa de Pós-Graduação em Matemática Aplicada |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | 53 f. : il., application/pdf |
| Source | reponame:Repositório Institucional da Unicamp, instname:Universidade Estadual de Campinas, instacron:UNICAMP |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.003 seconds