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
Authors who publish in this journal agree to the following terms:
Authors retain copyright and grant the journal the right of first publication, with the work simultaneously licensed under the Creative Commons Attribution License that allows the sharing of the work with acknowledgment of authorship and initial publication in this journal.
Authors are authorized to assume additional contracts separately, for non-exclusive distribution of the version of the work published in this journal (eg, publish in an institutional repository or as a book chapter), with acknowledgment of authorship and initial publication in this journal.
Authors are allowed and encouraged to publish and distribute their work online (eg, in institutional repositories or on their personal page) at any point before or during the editorial process, as this can generate productive changes as well as increase impact and the citation of the published work (See The effect of open access).
This is an open access journal which means that all content is freely available without charge to the user or his/her institution. Users are allowed to read, download, copy, distribute, print, search, or link to the full texts of the articles, or use them for any other lawful purpose, without asking prior permission from the publisher or the
author. This is in accordance with the BOAI definition of open access
Intellectual Property
All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License under attribution BY.