A New Hybrid Preconditioner for the Interior Point Method
DOI:
https://doi.org/10.5540/tema.2019.020.02.359Palavras-chave:
Interior Point Method, Controlled Cholesky Factorization, Splitting preconditionerResumo
This study aims to improve the computation of the search direction in the primal-dual Interior Point Method through preconditioned iterative methods. It is about a hybrid approach that combines the Controlled Cholesky Factorization preconditioner and the Splitting preconditioner. This approach has shown good results, however, in these preconditioners there are factors that reduce their efficiency, such as faults on the diagonal when performing the Cholesky factorization, as well as a demand for excessive memory, among others. Thus, some modifications are proposed in these preconditioners, as well as a new phase change, in order to
improve the performance of the hybrid preconditioner. In the Controlled Cholesky Factorization, the parameters that control the filling and the correction of the faults which occur on the diagonal are modified. It considers the relationship between the components from Controlled Cholesky Factorization obtained before and after the fault on the diagonal. In the Splitting preconditioner, in turn, a sparse base is constructed through an appropriate ordering of the columns from constrained matrix optimization problem. In addition, a theoretical result is presented, which shows that, with the proposed ordering, the condition number of the preconditioned Normal Equation matrix with the Splitting preconditioner is uniformly limited by an amount that depends only on the original data of the problem and not on the iteration of the Interior Point Method. Numerical experiments with large scale problems, corroborate the robustness and computational efficiency from this approach.
Referências
S. J. Wrigth, Primal-dual Interior-Point Methods:. SIAM e-books, Society for Industrial and Applied Mathematics (SIAM), 1997.
J. Gondzio, “Interior point methods 25 years later,” European Journal of Operational Research, vol. 218, no. 3, pp. 587–601, 2012.
J. Gondzio, “Multiple centrality corrections in a primal-dual method for linear programming,” Computational Optimization and Applications, vol. 6, pp. 137–156, Sep 1996.
G. Al-Jeiroudi, J. Gondzio, and J. Hall, “Preconditioning indefinite systems in interior point methods for large scale linear optimisation,” Optimization Methods and Software, vol. 23, no. 3, pp. 345–363, 2008.
S. Bocanegra, F. F. Campos, and A. R. L. Oliveira, “Using a hybrid preconditioner for solving large-scale linear systems arising from interior point methods,” Computational Optimization and Applications, vol. 36, no. 2-3, pp. 149–164, 2007.
F. F. Campos, Analysis of conjugate gradients-type methods for solving linear equations. PhD thesis, University of Oxford, 1995.
J. Gondzio, “Matrix-free interior point method,” Computacional Optimization and Applications, vol. 51, pp. 457–480, 2012.
A. R. L. Oliveira and D. Sorensen, “A new class of preconditioners for large-scale linear systems from interior point methods for linear programming,” Linear Algebra and its applications, vol. 394, pp. 1–24, 2005.
T. A. Maunteuffel, “An incomplete factorization technique for positive definite linear systems,” Mathematics of computation, vol. 34, no. 150, pp. 473–497, 1980.
M. I. Velazco, A. R. L. Oliveira, and F. F. Campos, “A note on hybrid preconditioners for large-scale normal equations arising from interior-point methods,” Optimization Methods Software, vol. 25, pp. 321–332, Apr. 2010.
I. J. Lustig, R. E. Marsten, and D. F. Shanno, “On implementing mehrotras s predictor–corrector interior-point method for linear programming,” SIAM Journal on Optimization, vol. 2, no. 3, pp. 435–449, 1992.
L. M. Silva and A. R. L. Oliveira, “Melhoria do desempenho da fatoração controlada de Cholesky no precondicionamento de sistemas lineares oriundos dos métodos de pontos interiores,” in Proceeding Series of the Brazilian Society of Computational and Applied Mathematics, vol. 3, pp. 1–7, SBMAC, 2015.
S. Bellavia, V. Simone, D. Serafino, and B. Morini, “A preconditioning frame-work for sequences of diagonally modified linear systems arising in optimization,” SIAM Journal on Numerical Analysis, vol. 50, no. 6, pp. 3280–3302, 2012.
P. Suñagua and A. R. L. Oliveira, “A new approach for finding a basis for the splitting preconditioner for linear systems from interior point methods,” Computational Optimization and Applications, vol. 67, no. 1, pp. 111–127, 2017.
L. Casacio, C. Lyra, A. R. L. Oliveira, and C. O. Castro, “Improving the
preconditioning of linear systems from interior point methods,” Comput. Oper. Res., vol. 85, pp. 129–138, Sept. 2017.
R. D. Monteiro, J. W. O’Neal, and T. Tsuchiya, “Uniform boundedness of a preconditioned normal matrix used in interior-point methods,” SIAM Journal on Optimization, vol. 15, no. 1, pp. 96–100, 2004.
J. Czyzyk, S. Mehrotra, M. Wagner, and S. J. Wright, “PCx an interior
point code for linear programming,” Optimization Methods & Software, vol. 11, pp. 397–430, 1999.
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.