A New Hybrid Preconditioner for the Interior Point Method
DOI:
https://doi.org/10.5540/tema.2019.020.02.359Keywords:
Interior Point Method, Controlled Cholesky Factorization, Splitting preconditionerAbstract
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
How to Cite
Issue
Section
License
Copyright
Authors of articles published in the journal Trends in Computational and Applied Mathematics retain the copyright of their work. The journal uses Creative Commons Attribution (CC-BY) in published articles. The authors grant the TCAM journal the right to first publish the article.
Intellectual Property and Terms of Use
The content of the articles is the exclusive responsibility of the authors. The journal uses Creative Commons Attribution (CC-BY) in published articles. This license allows published articles to be reused without permission for any purpose as long as the original work is correctly cited.
The journal encourages Authors to self-archive their accepted manuscripts, publishing them on personal blogs, institutional repositories, and social media, as long as the full citation is included in the journal's website version.
