A new approach for finding a base for the splitting preconditioner for linear system from interior point methods

dc.creatorSuñagua Salgado, Porfirio, 1963-
dc.date2014
dc.date2014-07-02T00:00:00Z
dc.date2017-04-02T00:46:55Z
dc.date2017-06-21T18:39:05Z
dc.date2017-04-02T00:46:55Z
dc.date2017-06-21T18:39:05Z
dc.date.accessioned2018-03-29T03:01:34Z
dc.date.available2018-03-29T03:01:34Z
dc.identifierSUÑAGUA SALGADO, Porfirio. Uma nova abordagem para encontrar uma base do precondicionador separador para sistemas lineares no método de pontos interiores. 2014. 156 p. Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica, Campinas, SP.
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/306744
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1324984
dc.descriptionOrientador: Aurelio Ribeiro Leite de Oliveira
dc.descriptionTese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica
dc.descriptionResumo: Uma abordagem do método preditor-corretor de Mehrotra para resolver problemas de programação linear de grande porte, que utiliza uma classe do precondicionador separador, para resolver sistemas lineares envolvidos por métodos iterativos precondicionados, necessita de uma base que é encontrada por um sofisticado processo de fatoração LU retangular da matriz de restrições. O precondicionador separador tem bom desempenho perto de uma solução ótima, onde as matrizes envolvidas ficam muito mal condicionadas. Neste trabalho, primeiro desenvolvemos o método preditor-corretor com o parâmetro de penalização a fim de reduzir o mau condicionamento da matriz de equações normais. O sucesso desta abordagem é garantido pela demonstração do teorema de convergência de penalização mista com o parâmetro de barreira. Em seguida, implementamos uma nova abordagem para encontrar uma base para o precondicionador separador mediante um processo de fatoração LU retangular padrão aplicada à matriz transposta de restrições escalada. Na maioria das vezes, esta base encontrada é melhor condicionada que a base do método de fatoração retangular anterior. Testes computacionais comprovam uma redução da média do número de iterações do método de gradientes conjugados precondicionado. Também, a eficácia e a robustez da nova abordagem é comprovada por conseguir uma melhor curva de desempenho
dc.descriptionAbstract: The class of splitting preconditioners for the iterative solution of linear systems arising from Mehrotra's predictor-corrector method for large-scale linear programming problems needs to find a base by a sophisticated process based upon applying a rectangular LU factorization. The class of splitting preconditioners works better near a solution of the linear programming problems when the matrices are highly ill-conditioned. In this work, we develop the penalty parameter in Mehrotra's predictor-corrector method in order to reduce the ill-conditioning of the normal equations matrix. The success of this approach is guaranteed by the proof of the theorem of convergence of mixed penalty with the barrier parameter. In addition, we develop and implement a new approach to find a basis for the splitting preconditioner, based upon standard rectangular LU factorization with partial permutation of the transpose of the scaled linear programming constraint matrix. In most cases, the basis is better conditioned than the existing one. Computational tests show a reduction in the average number of iterations of the preconditioned conjugate gradient method. Also, the efficiency and robustness of the new approach is demonstrated by achieving better performance profile
dc.descriptionDoutorado
dc.descriptionMatematica Aplicada
dc.descriptionDoutor em Matemática Aplicada
dc.format156 p. : il.
dc.formatapplication/pdf
dc.publisher[s.n.]
dc.subjectProgramação linear
dc.subjectMétodo preditor-corretor
dc.subjectPré-condicionadores
dc.subjectLinear programming
dc.subjectPredictor-corrector methods
dc.subjectPreconditioners
dc.titleUma nova abordagem para encontrar uma base do precondicionador separador para sistemas lineares no método de pontos interiores
dc.titleA new approach for finding a base for the splitting preconditioner for linear system from interior point methods
dc.typeTesis


Este ítem pertenece a la siguiente institución