Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/322428
Type: TESE DIGITAL
Title: Estudo do número de condição para aprimorar o cálculo da base do precondicionador separador no método de pontos interiores
Title Alternative: Study of the condition number to improve the computation the splitting preconditioner's base in the method of interior points
Author: Orellana Castro, Cecilia, 1987-
Advisor: Oliveira, Aurelio Ribeiro Leite de, 1962-
Abstract: Resumo: O precondicionador Separador foi desenvolvido especialmente para reduzir o mal condicionamento dos sistemas lineares oriundos das últimas iterações dos métodos de Pontos Interiores. Ele necessita de uma base que é uma submatriz não singular da matriz de restrições do problema, esta base depende fortemente da iteração corrente do método de Pontos Interiores pois induz uma ordenação das colunas da matriz de restrições que pode ser aproveitada para reduzir o número de condição do sistema precondicionado. Portanto, a eficiência deste precondicionador depende de uma escolha adequada desta base. Propõem-se novos critérios para a escolha da base amparados em resultados teóricos que estudam o número de condição do sistema precondicionado. Adicionalmente, dado que o cálculo da base requer um alto custo computacional e uso de memória, uma vez que suas colunas são obtidas por meio de uma fatoração LU retangular, procura-se uma base com colunas esparsas. Outra maneira de acelerar o cálculo da base numa iteração do método de Pontos Interiores é aproveitar algumas colunas da iteração anterior. Em uma primeira abordagem é feita de uma ordenação das colunas de tal maneira que o n\'{u}mero de condiç\~ao da matriz precondicionada seja reduzido, além disso, foi possível mostrar que com esta ordenação, o número de condição é uniformemente limitado por uma quantidade que independe da iteração do método de Pontos Interiores. Uma segunda abordagem usa a ordenação da primeira abordagem, porém acrescenta um critério adicional, uma reordenação segundo a esparsidade das colunas que irão formar a base. Em uma terceira abordagem, propõe-se uma ordenação das colunas combinando estes dois requisitos simultaneamente; bom condicionamento e esparsidade para a base. Nestes casos é necessário um balanço entre esparsidade e bom condicionamento, para isso, apresentam-se resultados teóricos que permitem um controle sobre o equilíbrio entre estes dois requisitos. Finalmente, apresenta-se uma proposta de \textit{reciclagem} das colunas básicas de uma iteração para serem utilizadas na seguinte. Neste trabalho, abordam-se problemas de programação linear de grande porte usando o método preditor-corretor de Mehrotra. O precondicionamento dos sistemas lineares para encontrar a direção é feito em duas fases: na primeira fase, usa-se o precondicionador Fatora\c c\~ao Controlada de Cholesky, na segunda fase, o precondicionador Separador. O critério de mudança de fase atualmente utilizado foi sutilmente modificado, acrescentou-se um indicador que permite saber se o precondicionador Separador obterá um bom desempenho baseado nas diferenças abruptas que apresentam os elementos da matriz diagonal $D,$ particularmente nas últimas iterações do método de Pontos Interiores. Uma implementação destas novas abordagens e uma comparação com a vers\~ao atualmente utilizada, mostraram resultados competitivos

Abstract:The Splitting preconditioner has been specially developed to reduce the ill conditioning of linear systems from the latest Interior Point methods iterations. It needs a basis which is a non-singular submatrix of the constraint matrix, this basis strongly depends on the current iteration of the Interior Point method because it induces an ordering of the constraint matrix columns that can be used to reduce the condition number of the preconditioned system, therefore, its efficiency depends on a suitable choice of this basis. We proposed new approaches for choosing the basis supported by theoretical results that study the condition number of the preconditioned system. Additionally, finding the basis requieres a high computational cost and memory usage, since its columns are obtained through a rectangular LU factorization, a base with sparse columns is searched. Another way to speed up the computation basis of the Interior Point method iteration is to use some columns from the previous iteration. A first approach is an ordering to find basic columns such that the condition number of the preconditioned matrix is reduced, moreover, it is possible to show that this condition number is uniformly bounded by an amount that is independent of the Interior Point method iteration. A second approach uses the ordering of the first approach, but adds an additional criterion, a reordering according to the constraint matrix sparsity. In a third approach, it is proposed a ordering of columns of the constraint matrix by joining these both requirements simultaneously; well conditioning and sparsity for the basis. In these cases, a balance between sparsity and well conditioning is necessary, for this we present theoretical results that allow control over the balance between these both requirements. Finally, a last approach, we use a recycle basic column from one iteration to be used in the next iteration. In this work, large linear programming problems are solved using the Mehrotra's predictor-corrector method. Preconditioning of the linear systems to find the search direction is done in two phases: the first phase, we use the Controlled Cholesky Factorization preconditioner, in the second phase, the Splitting preconditioner. The change of phase criterion currently used was subtly modified by the addition of an indicator that shows whether the Splitting preconditioner is ready to have a well performance based on the sharp differences on the elements of the diagonal matrix $D,$ particularly in the last Interior Point method iterations. An implementation of these new approaches and a comparison with the version currently used, showed competitive results
Subject: Programação linear
Pré-condicionadores
Método preditor-corretor
Métodos de pontos interiores
Métodos iterativos (Matemática)
Métodos do gradiente conjugado
Editor: [s.n.]
Date Issue: 2017
Appears in Collections:IMECC - Dissertação e Tese

Files in This Item:
File SizeFormat 
Castro_CeciliaOrellana_M.pdf1.19 MBAdobe PDFView/Open


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