Uma nova abordagem para o cálculo do precondicionador separador
DOI:
https://doi.org/10.5540/03.2025.011.01.0501Keywords:
Precondicionador, Método de Pontos Interiores, Programação LinearAbstract
Os métodos de pontos interiores são ferramentas eficientes para a resolução de problemas de programação linear de grande porte. Como este método pode ter um alto custo computacional, métodos iterativos precondicionados são usados para resolver os sistemas lineares oriundos do método de pontos interiores. O precondicionador separador é utilizado nas iterações finais do método, onde os sistemas lineares se tornam muito mal condicionados. Mas pode ser caro calcular esse precondicionador, cuja implementação depende, dentre outros aspectos, de uma escolha adequada de colunas linearmente independentes da matriz original para construir a base do mesmo. Por isso, neste trabalho, é proposta uma nova abordagem para o cálculo da base do precondicionador separador, com o objetivo de reduzir o custo computacional do método. Além disso, a abordagem proposta é comparada com a abordagem já existente, a fim de mostrar que a base obtida é a mesma que foi encontrada pelos métodos anteriores.
Downloads
References
S. Bocanegra, F. F. Campos e A. R. L. Oliveira. “Using a Hybrid Preconditioner for Solving Large-Scale Linear Systems arising from Interior Point Methods”. Em: Computational Optimization and Applications 36.1–2 (2007), pp. 149–164.
F.F. Campos. “Analysis of Conjugate Gradients - type methods for solving linear equations”. Tese de doutorado. Oxford University Computing Laboratory, 1995.
C.O. Castro, M.R. Heredia e A. R. L. Oliveira. “Recycling basic columns of the splitting preconditioner in interior point methods”. Em: Computational Optimization and Applications 86 (2023), pp. 49–78. doi: https://doi.org/10.1007/s10589-023-00492-13.
D.M. Gay. “Electronic Mail Distribution of Linear Programming Test Problems”. Em: Mathematical Programming Society COAL Newsletter 13 (1985), pp. 10–12. doi: https://doi.org/10.1007/s10589-023-00492-13.
C.T.L.S. Ghidini, A. R. L. Oliveira e D. C. Sorensen. “Computing a hybrid preconditioner approach to solve the linear systems arising from interior point methods for linear programming using the conjugate gradient method”. Em: Annals of Management Science 3.1 (2014), pp. 45–66. doi: 10.24048/ams3.no1.2014-43.
J. Gondzio. “Interior Point Methods 25 Years Later”. Em: European Journal of Operational Research 218 (2012), pp. 587–601.
S. Mehrotra. “On the implementation of a primal-dual interior point method”. Em: SIAM Journal on Optimization 2.4 (1992), pp. 575–601. doi: 10.1137/0802028.
A. R. L. Oliveira e D. C. Sorensen. “A new class of preconditioners for large-scale linear systems from interior point methods for linear programming”. Em: Linear Algebra and Its Applications 394 (2005), pp. 1–24. doi: https://doi.org/10.1016/j.laa.2004.08.019.
S. J. Wright. Primal-Dual Interior-Point Methods. Philadelphia: Society for Industrial e Applied Mathematics (SIAM), 1997. isbn: 9781611971453.
