Solução iterativa dos sistemas lineares do método de pontos interiores
DOI:
https://doi.org/10.5540/tema.2014.015.03.0275Resumo
Nesse trabalho, consideramos o método preditor-corretor, que é uma das variantes mais importante do métodos de pontos interiores devido à sua eficiência e convergência rápida. No método preditor-corretor, é preciso resolver dois sistemas lineares a cada iteração para determinar a direção preditora-corretora. A resolução desses sistemas é o passo que requer mais tempo de processamento, devendo assim ser realizada de maneira eficiente. Para obter a solução dos sistemas lineares do método preditor-corretor consideramos dois métodos iterativos de Krylov: MINRES e método dos gradientes conjugados. Para que estes métodos convirjam mais rapidamente um pré-condicionador especialmente desenvolvido para os sistemas lineares oriundos dos métodos de pontos interiores é usado. Experimentos computacionais em um conjunto variado de problemas de programação linear foram realizados com o intuito de analisar a eficiência e robustezdos métodos de solução dos sistemas.
Referências
R. S. Burkard, S. Karisch e F. Rendl. Qaplib - a quadratic assignment problem library,
European Journal of Operations Research, 55, (1991), 115-119.
J.L. Kennington S. Niemi W.J. Carolan, J.E. Hill and S.J. Wichmann, An empirical evaluation of the korbx algorithms for military airlift applications, Oper. Res, 38, (1990), 240-248.
D. M. Gay, Electronic mail distribution of linear programming test problems, Mathematical Programming Society Committee on Algorithms COAL Newsletter (1985),
-12.
G. H. Golub e C. F. Van Loan, Matrix Computations. 3a ed. Baltimore, Md., London:
The Johns Hopkins University Press, 1996.
N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, 4 (1984) 373-395.
C. Lanczos, An iteration method for the solution of the eigenvalue problem of linear
differential and integral operators, J. Res. Nat. Bureau Standards, 45,4 (1950), 255-
S. Mehrotra, On the implementation of a primal-dual interior point method, SIAM
Journal on Optimization, 2, 4 (1992) 575-601.
C. D. Meyer, Matrix analysis and applied linear algebra, SIAM, 2000.
Miscellaneous lp models, Technical report, Hungarian Academy of Sciences OR Lab.
url, www.sztaki.hu/ meszaros/publicftp/lptestset/misc.
R. D. C. Monteiro, I. Adler e M. G. C.Resende, A polynomial-time primal-dual affine
scaling algorithm for linear and convex quadratic programming and its power series
extension, Mathematics of Operations Research 15 (1990) 191-214.
A. R. L. Oliveira, D. C. Sorensen, A new class of preconditioners for large-scale linear systems from interior point methods for linear programming, Linear Algebra and Its Applications, 394 (2005) 1–24.
D. C. Sorensen, Implicit application of polynomial filters in a k-step Arnoldi method,
SIAM Journal on Matrix Analysis and Applications, 13 (1992) 357-385.
Stochastic lp test sets, Technical report, Hungarian Academy of Sciences OR Lab. url, /www.sztaki.hu/ meszaros/publicftp/lptestset/stochlp.
S. J. Wright, Primal-dual interior-point methods, SIAM Publications, SIAM,
Philadelphia, PA, USA, 1997.
Downloads
Publicado
Como Citar
Edição
Seção
Licença
Política para Periódicos de Acesso Livre
Autores que publicam nesta revista concordam com os seguintes termos:
- Autores mantém os direitos autorais e concedem à revista o direito de primeira publicação, com o trabalho simultaneamente licenciado sob a Licença Creative Commons Attribution que permite o compartilhamento do trabalho com reconhecimento da autoria e publicação inicial nesta revista.
- Autores têm autorização para assumir contratos adicionais separadamente, para distribuição não-exclusiva da versão do trabalho publicada nesta revista (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento de autoria e publicação inicial nesta revista.
- Autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex.: em repositórios institucionais ou na sua página pessoal) a qualquer ponto antes ou durante o processo editorial, já que isso pode gerar alterações produtivas, bem como aumentar o impacto e a citação do trabalho publicado (Veja O Efeito do Acesso Livre).
- Esta é uma revista de acesso aberto, o que significa que todo o conteúdo é livremente disponível gratuitamente para o usuário ou sua instituição. Os usuários estão autorizados a ler, baixar, copiar, distribuir, imprimir, pesquisar ou vincular os textos completos dos artigos, ou usá-los para qualquer outro propósito legal, sem pedir permissão prévia do editor ou do autor. Isso está de acordo com a definição de acesso aberto do BOAI.
Todo o conteúdo do periódico está licenciado sob uma Licença Creative Commons do tipo atribuição BY.