Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/332334
Type: TESE DIGITAL
Degree Level: Doutorado
Title: Aperfeiçoamento da abordagem híbrida de precondicionamento para métodos de pontos interiores
Title Alternative: Improvement of the hybrid preconditioning approach for interior point methods
Author: Cadena Madrid, Kelly
Advisor: Ghidini, Carla Taviane Lucke da Silva, 1976-
Abstract: Resumo: A etapa mais importante do método de pontos interiores preditor-corretor para solução de problemas de programação linear de grande porte, consiste em resolver sistemas de equações lineares para determinar as direções de busca. Esse é o passo que requer maior esforço computacional do método e, dessa forma, é fundamental realizá-lo da maneira mais eficiente possível. Uma abordagem que pode ser utilizada consiste em reduzir o sistema linear em um sistema de equações normais equivalente, cuja matriz é simétrica e definida positiva e aplicar o método iterativo dos gradientes conjugados precondicionado para resolvê-lo. Encontrar um único precondicionador que funcione bem em todas iterações do método preditor-corretor não é uma tarefa simples, pois os sistemas vão se tornando cada vez mais mal condicionados. Na literatura, foi proposta uma abordagem híbrida de precondicionamento que combina dois precondicionadores especialmente adaptados para esses sistemas, a qual apresentou bons resultados e que consiste em nas primeiras iterações do preditor-corretor utilizar o precondicionador Fatoração Controlada de Cholesky e depois de certo número de iterações realizar a troca e o precondicionador Separador passa a ser utilizado. Algumas heurísticas simples para determinar o momento ideal para trocar de precondicionador já foram desenvolvidas. Porém, motivados pela importância dessa etapa, desenvolvemos e testemos novas heurísticas que utilizam estimativas do número de condição da matriz do sistema, uma vez que calcular o valor exato para matrizes de grande porte é caro computacionalmente e torna-se inviável na prática, e análise da dispersão dos autovalores da matriz. Além disso, com o intuito de proporcionar outras melhorias para a abordagem híbrida de precondicionamento e, consequentemente, obter um método de pontos interiores ainda mais eficiente e robusto, outro critério para a atualização do parâmetro de preenchimento utilizado na Fatoração Controlada de Cholesky foi proposto com base numa característica do problema, que é a densidade da matriz. Diversos experimentos computacionais foram realizados com problemas pertencentes à coleções com acesso livre para testar todas as heurísticas desenvolvidas e compará-las com as existentes. De acordo com os resultados obtidos podemos afirmar que os objetivos deste trabalho foram alcançados, uma vez que algumas das heurísticas propostas contribuíram para determinar um melhor momento de trocar de precondicionador e tornaram o precondicionador Fatoração Controlada de Cholesky mais adequado

Abstract: The most important step of the predictor-corrector interior point method for large linear programming problems is to solve linear systems to determine the search directions. This is the most costly computational step of the method and therefore it is essential to perform it in the most efficient way possible. One approach that can be used is to reduce the linear system in a system of equivalent normal equations, which matrix is symmetric and positive definite and apply the preconditioned conjugate gradient method to solve it. Finding a single preconditioner that works well in all iterations of the interior point method is not a simple task as the systems become increasingly ill conditioned. In the literature, it was proposed a hybrid preconditioning approach that combines two preconditioners specially adapted for these systems, which presented good results and that consists in using the Controlled Cholesky Factorization preconditioner in the first iterations of the predictor-corrector making the exchange after a certain number of iterations, and adopting Separator preconditioner thereafter. Some simple heuristics to determine the ideal time to change preconditioner have already been developed. However, motivated by the importance of this step, we develop and test new heuristics that use estimates of the condition number of the system matrix, since calculating the exact value for large matrices is computationally expensive and becomes prohibitibe in practice, and investigate the eigenvalues ??dispersion. In addition, in order to provide other improvements to the hybrid pre-conditioning approach and consequently to obtain an even more efficient and robust interior point method, another criterion for updating the fill parameter used in Controlled Cholesky Factoring was proposed based on a characteristic of the problem, which is the density of the matrix. Several computational experiments were carried out with problems belonging to the collections with free access in order to test all developed heuristics and to compare them with existing ones. According to the results obtained we can affirm that the objectives of this work were reached, since some of the proposed heuristics contributed to determine a better instant to change preconditioner and made Controlled Cholesky Factorization Preconditioner more suitable
Subject: Programação linear
Métodos de pontos interiores
Sistemas lineares
Métodos de gradiente conjugado
Pré-condicionador híbrido
Language: Português
Editor: [s.n.]
Date Issue: 2018
Appears in Collections:IMECC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Madrid_KellyCadena_D.pdf2.77 MBAdobe PDFView/Open


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