Solução iterativa dos sistemas lineares do método de pontos interiores

Autores

  • Carla Taviane Lucke da SIlva Ghidini IMECC - UNICAMP
  • Aurelio Ribeiro Leite Oliveira IMECC - UNICAMP
  • Marilene Silva IMECC - UNICAMP

DOI:

https://doi.org/10.5540/tema.2014.015.03.0275

Resumo

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 robustez
dos 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

2014-01-27

Como Citar

Ghidini, C. T. L. da S., Oliveira, A. R. L., & Silva, M. (2014). Solução iterativa dos sistemas lineares do método de pontos interiores. Trends in Computational and Applied Mathematics, 15(3), 275–291. https://doi.org/10.5540/tema.2014.015.03.0275

Edição

v. 15 n. 3 (2014)

Seção

Artigo Original

Licença

Direitos Autorais

Autores de artigos publicados no periódico Trends in Computational and Applied Mathematics mantêm os direitos autorais de seus trabalhos. O periódico utiliza a Atribuição Creative Commons (CC-BY) nos artigos publicados. Os autores concedem ao periódico o direito de primeira publicação.

Propriedade Intelectual e Termos de uso

O conteúdo dos artigos é de responsabilidade exclusiva dos autores. O periódico utiliza a Atribuição Creative Commons (CC-BY) nos artigos publicados. Esta licença permite que os artigos publicados sejam reutilizados sem permissão para qualquer finalidade, desde que o trabalho original seja corretamente citado.

O periódico encoraja os Autores a autoarquivar seus manuscritos aceitos, publicando-os em blogs pessoais, repositórios institucionais e mídias sociais acadêmicas, bem como postando-os em suas mídias sociais pessoais, desde que seja incluída a citação completa à versão do website da revista.