Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/306742
Type: TESE DIGITAL
Title: Experimentos numéricos com um sistema linear alternativo para o pré-condicionador separador aplicado a métodos de pontos interiores
Title Alternative: Numerical experiments with an alternative linear system for the splitting preconditioner applied to interior point methods
Author: Silva, Fábio Rodrigues, 1990-
Advisor: Oliveira, Aurelio Ribeiro Leite de, 1962-
Abstract: Resumo: Neste trabalho, realizamos experimentos numéricos com um sistema linear alternativo para o pré-condicionador separador aplicado ao método iterativo de Gradientes Conjugados pré-condicionado, no contexto da solução iterativa de problemas de programação linear via método de pontos interiores. Consideramos o método preditor-corretor proposto por Mehrotra, que obtém a solução do problema de programação linear aplicando o método de Newton nas condições de otimalidade de Karunsh-Kuhn-Tucker perturbadas. O método de Gradientes Conjugados pré-condicionado é usado para obter a solução dos sistemas lineares. Em trabalhos anteriores, uma estratégia híbrida de pré-condicionamento foi proposta e experimentos computacionais revelaram que seu desempenho é superior ao uso de métodos diretos na solução dos sistemas lineares para algumas classes de problemas de programação linear. Seu funcionamento ocorre em duas fases: a fase 1 utiliza um tipo de pré-condicionador de fatoração incompleta de Cholesky com preenchimento adaptativo em função da memória disponível no computador; a fase 2 utiliza um pré-condicionador baseado na fatoração LU, especializado para as últimas iterações dos métodos de pontos interiores. Nestes trabalhos, heurísticas para promover a troca de fases foram apresentadas e novas estratégias para o reordenamento das colunas da matriz de coeficientes foram exibidas. Na fase 2, a matriz pré-condicionada é indefinida e pode ser reduzida para um sistema linear definido positivo de uma das dimensões do complemento de Schur. Estes trabalhos basearam-se em resultados numéricos sobre a matriz quadrada de dimensão igual ao número de linhas da matriz de restrições. Realizamos experimentos computacionais com a matriz quadrada de dimensão igual à diferença entre o número de colunas e linhas da matriz de restrições, objetivando aferir o desempenho das versões desenvolvidas para este fim. Foram propostas duas estratégias de recuperação da solução do sistema aumentado pré-condicionado. Exibimos os resultados em função de quatro métricas de desempenho: o número de iterações de pontos interiores e de gradientes conjugados, tempo total de solução e número de vezes que a fase 2 calcula uma nova matriz não singular. Comparamos as versões propostas com a versão híbrida apresentada em trabalhos anteriores, resolvendo um conjunto de 35 problemas teste selecionados de diferentes bibliotecas de problemas de programação matemática. Apenas uma das versões desenvolvidas neste trabalho resolveu todos problemas propostos. Os resultados mostram que, de maneira geral, as versões desenvolvidas apresentam melhor comportamento computacional em relação à versão híbrida, no que se refere às métricas de desempenho consideradas, para todos os problemas que foram resolvidos com sucesso

Abstract: In this work, we carried out numerical experiments with an alternative linear system for the splitting preconditioner applied to preconditioned Conjugate Gradient iterative method, in the context of iterative solution of linear programming problems by interior point methods. We consider the Mehrotra's predictor-corrector method, that search the solution of the linear programming problem by applying Newton's method in the perturbed Karunsh-Kuhn-Tucker's optimality conditions. The preconditioned Conjugate Gradients method is used for the solution of the linear systems. In previous works, a hybrid preconditioning strategy was proposed and computational experiments show its superior performance against direct methods in solving linear systems for some linear programming problems classes. Such approach takes place in two phases: phase 1 uses a kind of incomplete Cholesky preconditioner with an adaptive fill-in as a function of the available memory in the computer; phase 2 uses a preconditioner based on LU factorization, specialized for the latest iterations of interior point methods. In these works, heuristics to promote the exchange of phases were presented and new strategies for the reordering of the columns of the coefficient matrix were presented. In phase 2, the preconditioned matrix is indefinite and can be reduced to a positive definite linear system of one of the sizes of Schur complement. These studies were based on numerical results on the square matrix of dimension equals to the number of constraints matrix lines. We perform computational experiments with a square matrix of size equals to the difference between the number of columns and rows of constraints matrix, aiming to benchmark the versions developed for this purpose. It was proposed two strategies for the preconditioned augmented system recovery solution. We show the results in terms of four performance metrics: the number of interior point and conjugate gradient iterations, solution time and number of times that the phase 2 computes a new non-singular matrix. We compared the proposed versions with the hybrid version presented in previous works, solving a set of 35 selected test problems from different mathematical programming problems libraries. Only one of the developed versions in this work solved all the chosen problems. The results show that, in general, the developed versions present better computational performance over the hybrid version, regarding the performance metrics considered, for all the successful solveds problems
Subject: Programação linear
Métodos de pontos interiores
Pré-condicionadores
Sistemas lineares
Métodos do gradiente conjugado
Editor: [s.n.]
Date Issue: 2016
Appears in Collections:IMECC - Dissertação e Tese

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


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