A New Approach to the Splitting Factor Preconditioner Applied to Linear Programming Problems

Authors

DOI:

https://doi.org/10.5540/tcam.2022.023.02.00349

Keywords:

Preconditioner, Linear Programming, Signal Processing, Compressive Sensing.

Abstract

In this paper, we present the results of a new approach to the splitting factor preconditioner, which is a preconditioner based on the Incomplete Cholesky factorization and the splitting preconditioner. In previous work for small linear programming problems, the preconditioner was applied in all iterations of the interior point method and compared with the splitting preconditioner also applied in all iterations. In this paper, we will do a hybrid approach, in which in the first iterations the preconditioner is the Incomplete Cholesky Factorization, and in the last iterations, the preconditioner used is the splitting factor preconditioner or the splitting preconditioner. The results obtained show that even in the hybrid approach, the splitting factor preconditioner achieved better performance.

References

M. S. Bazaraa, J. J. Jarvis, and H. D. Sherali, Linear programming and network flows. Hoboken, NJ: John Wiley & Sons, 2011.

M. A. G. Ruggiero and V. L. d. R. Lopes, Cálculo numérico. São Paulo, SP: Makron Books do Brasil, 1997.

N. Karmarkar, “A new polynomial-time algorithm for linear programming,” in Proceedings of the sixteenth annual ACM symposium on Theory of computing, (Washington D. C.), pp. 302–311, ACM, 1984.

S. J. Wright, Primal-dual interior-point methods. Philadelphia, PA: SIAM, 1997.

S. Mehrotra, “On the implementation of a primal-dual interior point method,” SIAM Journal on optimization, vol. 2, no. 4, pp. 575–601, 1992.

P. A. Kikuchi, Novos pré-condicionadores aplicados a problemas de programação linear e ao problema compressive sensing. PhD thesis, University of Campinas, 2017. In portuguese.

S. J. Wright, Primal-dual interior-point methods, vol. 54. Philadelphia, PA: Society for Industrial and Applied Mathematics, 1987.

L. N. Trefethen and D. BAU III, Numerical linear algebra, vol. 50. Philadelphia, PA: Siam, 1997.

G. H. Golub and C. F. Van Loan, Matrix computations. Baltimore, MD: JHU Press, 3 ed., 2012.

Y. Saad and H. A. Van Der Vorst, “Iterative solution of linear systems in the 20th century,” Journal of Computational and Applied Mathematics, vol. 123, no. 1, pp. 1–33, 2000.

L. Cesari, “Sulla risoluzione dei sistemi di equazioni lineari per approssimazioni successive,” Atti Accad. Naz. Lincei. Rend. Cl. Sci. Fis. Mat. Nat., vol. 25, no. 6a, pp. 422–428, 1937.

A. R. Oliveira and D. C. Sorensen, “A new class of preconditioners for largescale linear systems from interior point methods for linear programming,” Linear Algebra and its applications, vol. 394, pp. 1–24, 2005.

J. Meijerink and H. A. Van Der Vorst, “An iterative solution method for linear systems of which the coefficient matrix is a symmetric M-matrix,” Mathematics of computation, vol. 31, no. 137, pp. 148–162, 1977.

M. Benzi, “Preconditioning techniques for large linear systems: a survey,” Journal of computational Physics, vol. 182, no. 2, pp. 418–477, 2002.

M. T. Jones and P. E. Plassmann, “An improved incomplete Cholesky factorization,” ACM Transactions on Mathematical Software (TOMS), vol. 21, no. 1, pp. 5–17, 1995.

P. A. Kikuchi and A. R. L. Oliveira, “New preconditioners applied to linear programming and the compressive sensing problems,” SN Oper. Res. Forum, vol. 1, no. 36, 2020.

S. Bocanegra, F. Campos, and A. R. Oliveira, “Using a hybrid preconditioner for solving large-scale linear systems arising from interior point methods,” Computational Optimization and Applications, vol. 36, no. 2, pp. 149–164, 2007.

Downloads

Published

2022-06-27

How to Cite

Kikuchi, P. A., & Oliveira, A. R. L. (2022). A New Approach to the Splitting Factor Preconditioner Applied to Linear Programming Problems. Trends in Computational and Applied Mathematics, 23(2), 349–361. https://doi.org/10.5540/tcam.2022.023.02.00349

Issue

Vol. 23 No. 2 (2022)

Section

Original Article

License

Authors who publish in this journal agree to the following terms: 

  1. 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.

  2. 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.
     

  3. 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).

  4. 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.