A New Hybrid Preconditioner for the Interior Point Method

Authors

  • Manolo Rodriguez Heredia "Universidade Federal do Sul e Sudeste do Pará"
  • Cecilia Orellana Castro "Universidade Federal do Sul e Sudeste do Pará"
  • Aurélio Ribeiro Leitte Oliveira "Universidade Estadual de Campinas"

DOI:

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

Keywords:

Interior Point Method, Controlled Cholesky Factorization, Splitting preconditioner

Abstract

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.

References

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

Published

2019-07-29

How to Cite

Heredia, M. R., Castro, C. O., & Oliveira, A. R. L. (2019). A New Hybrid Preconditioner for the Interior Point Method. Trends in Computational and Applied Mathematics, 20(2), 359. https://doi.org/10.5540/tema.2019.020.02.359

Issue

Section

Original Article