Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/321278
Type: TESE DIGITAL
Title: Valores de Ritz aplicados a troca de fase do precondicionador híbrido para métodos de pontos interiores
Title Alternative: Ritz values applied to phase exchange in the hybrid preconditioner to interior point method
Author: Bartmeyer, Petra Maria, 1990-
Advisor: Bocanegra, Silvana
Bocanegra, Silvana
Abstract: Resumo: O método preditor corretor de Mehrotra é uma variante dos métodos de pontos interiores para programação linear onde a cada iteração é necessária a resolução de dois sistemas lineares: o primeiro determina a direção preditora e o segundo a direção corretora. O cálculo desses sistemas lineares detém a maior parte do custo computacional, assim o método de resolução deve ser cuidadosamente escolhido. O método de gradientes conjugados precondicionado é utilizado para resolver tais sistemas lineares. O precondicionamento é realizado de forma híbrida, nas primeiras iterações usa-se o precondicionador fatoração controlada de Cholesky e nas iterações finais o precondicionador separador. O ponto chave do precondicionador híbrido é determinar o momento para a troca. O número de condição, estimado por meio dos valores de Ritz, é utilizado em uma heurística para troca dos precondicionadores. Testes computacionais foram realizados para avaliar a qualidade da heurística quando comparada com a literatura

Abstract: The Mehrotra predictor corrector method is a variant of interior point methods for linear programming where at each iteration it is necessary to solve two linear systems: the first determines the predictor direction and the second the corrector direction. Solving these linear systems represents most of the computational cost. For this reason, the solution method must be carefully chosen. In this work the conjugate gradients method is applied, it depends on the convergence of the matrix condition number making it necessary a preconditioner. The preconditioning is performed by the hybrid preconditioner, where in the first iterations, the preconditioner controlled Cholesky factorization is applied and in later iterations, the splitting preconditioner is applied. The key point of the hybrid preconditioner approach is to determine the moment for the phase exchange. Ritz values are used to estimate the condition number and to develop a heuristic to the change of phases. Computational experiments were performed to evaluate the heuristic quality when compared with the literature
Subject: Ritz, Valores de
Métodos de pontos interiores
Programação linear
Métodos iterativos (Matemática)
Pré-condicionador híbrido
Editor: [s.n.]
Date Issue: 2016
Appears in Collections:IMECC - Dissertação e Tese

Files in This Item:
File SizeFormat 
Bartmeyer_PetraMaria_M.pdf666.91 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.