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
Authors who publish in this journal agree to the following terms:
Authors retain copyright and grant the journal the right of first publication, with the work simultaneously licensed under the Creative Commons Attribution License that allows the sharing of the work with acknowledgment of authorship and initial publication in this journal.
Authors are authorized to assume additional contracts separately, for non-exclusive distribution of the version of the work published in this journal (eg, publish in an institutional repository or as a book chapter), with acknowledgment of authorship and initial publication in this journal.
Authors are allowed and encouraged to publish and distribute their work online (eg, in institutional repositories or on their personal page) at any point before or during the editorial process, as this can generate productive changes as well as increase impact and the citation of the published work (See The effect of open access).
This is an open access journal which means that all content is freely available without charge to the user or his/her institution. Users are allowed to read, download, copy, distribute, print, search, or link to the full texts of the articles, or use them for any other lawful purpose, without asking prior permission from the publisher or the
author. This is in accordance with the BOAI definition of open access
Intellectual Property
All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License under attribution BY.