Solução iterativa dos sistemas lineares do método de pontos interiores
DOI:
https://doi.org/10.5540/tema.2014.015.03.0275Abstract
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.
References
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
Published
How to Cite
Issue
Section
License
Copyright
Authors of articles published in the journal Trends in Computational and Applied Mathematics retain the copyright of their work. The journal uses Creative Commons Attribution (CC-BY) in published articles. The authors grant the TCAM journal the right to first publish the article.
Intellectual Property and Terms of Use
The content of the articles is the exclusive responsibility of the authors. The journal uses Creative Commons Attribution (CC-BY) in published articles. This license allows published articles to be reused without permission for any purpose as long as the original work is correctly cited.
The journal encourages Authors to self-archive their accepted manuscripts, publishing them on personal blogs, institutional repositories, and social media, as long as the full citation is included in the journal's website version.
