×

Modified controlled Cholesky factorization for preconditioning linear systems from the interior-point method. (English) Zbl 1476.90186

Summary: The interior-point method solves large linear programming problems in a few iterations. Each iteration requires computing the solution to one or more linear systems. This constitutes the most expensive step of the method and reducing the time to solve these linear systems is a way of improving the method’s performance. Iterative methods such as the preconditioned conjugate gradient method can be used to solve them. Incomplete Cholesky factorization can be used as a preconditioner to the problem. However, breakdowns may occur during incomplete factorizations and corrections on the diagonal may be required. This correction is accomplished by adding a positive number to diagonal elements of the linear system matrix and the factorization of the new matrix is restarted. In this work, we propose modifications to controlled Cholesky factorization to avoid or decrease the number of refactorizations of diagonally modified matrices. Computational results show that the proposed techniques can reduce the time needed for solving linear programming problems by the interior-point method.

MSC:

90C05 Linear programming
90C51 Interior-point methods
65F08 Preconditioners for iterative methods
15A23 Factorization of matrices

Software:

PCx; QAPLIB
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bellavia, S.; de Simone, V.; di Serafino, D.; Morini, B., Efficient preconditioner updates for shifted linear systems, SIAM J Sci Comput, 4, 1785-1809 (2011) · Zbl 1236.65029 · doi:10.1137/100803419
[2] Bellavia, S.; de Simone, V.; di Serafino, D.; Morini, B., A preconditioning framework for sequences of diagonally modified linear systems arising in optimization, SIAM J Numer Anal, 6, 3280-3302 (2012) · Zbl 1267.65035 · doi:10.1137/110860707
[3] Benzi, M.; Golub, GH; Liesen, J., Numerical solution of saddle point problems, Acta Numer, 14, 1-137 (2005) · Zbl 1115.65034 · doi:10.1017/S0962492904000212
[4] Bergamaschi L, Gondzio J, Venturin Mand Zilli G (2007) Inexact constraint preconditioners for linear system arising interior point methods. Comput Optim Appl 36:137-147 · Zbl 1148.90349
[5] Bocanegra S, Campos FF, Oliveira ARL (2007) Using a hybrid preconditioner for solving large-scale linear systems arising from interior point methods 36:149-164 · Zbl 1148.90350
[6] Burkard, RE; Karisch, S.; Rendl, F., QAPLIB-A quadratic assignment problem library, Eur J Oper Res, 55, 115-119 (1991) · Zbl 0729.90993 · doi:10.1016/0377-2217(91)90197-4
[7] Campos, FF; Birkett, NRC, An efficient solver for multi-right hand side linear systems based on the CCCG \(( \eta )\) method with applications to implicit time-dependent partial differential equations, SIAM, J Sci Comput, 19, 126-138 (1998) · Zbl 0917.65030
[8] Czyzyk, J.; Mehrotra, S.; Wagner, M.; Wright, SJ, PCx: an interior-point code for linear programming, Optim Methods Softw, 11, 397-430 (1999) · Zbl 0970.90118 · doi:10.1080/10556789908805757
[9] Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math Program, 91, 201-213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263
[10] Ghidini, CTLS; Oliveira, ARL; Silva, J.; Velazco, MI, Combining a hybrid preconditioner and a optimal adjustment algorithm to accelerate the convergence of interior point methods, Linear Algebra Appl, 436, 1267-1284 (2012) · Zbl 1236.65065 · doi:10.1016/j.laa.2011.08.023
[11] Ghidini, CTLS; Oliveira, ARL; Sorensen, DC, Computing a hybrid preconditioner approach to solve the linear systems arising from interior point methods for linear programming using the conjugate gradient method, Ann Manag Sci, 3, 44-66 (2014) · doi:10.24048/ams3.no1.2014-43
[12] Gondzio, J., Interior point methods 25 years later, Eur J Oper Res, 218, 587-601 (2012) · Zbl 1244.90007 · doi:10.1016/j.ejor.2011.09.017
[13] Jones, MT; Plassmann, PE, An improved incomplete Cholesky factorization, ACM Tran Math Softw, 21, 5-17 (1995) · Zbl 0886.65024 · doi:10.1145/200979.200981
[14] Kershaw, DS, The incomplete Cholesky - conjugate gradient method for the iterative solution of systems of linear equations, J Comput Phys, 26, 43-65 (1978) · Zbl 0367.65018 · doi:10.1016/0021-9991(78)90098-0
[15] Manteuffel, TA, An incomplete factorization technique for positive definite linear systems, Math Comput, 34, 473-497 (1980) · Zbl 0422.65018 · doi:10.1090/S0025-5718-1980-0559197-0
[16] Mehrotra, S., On the implementation of a primal-dual interior point method, SIAM J Optim, 2, 575-601 (1992) · Zbl 0773.90047 · doi:10.1137/0802028
[17] Oliveira, ARL; Sorensen, DC, A new class of preconditioners for large-scale linear systems from interior point methods for linear programming, Linear Algebra Appl, 394, 1-24 (2005) · Zbl 1071.65088 · doi:10.1016/j.laa.2004.08.019
[18] Resende, MGC; Veiga, G., An efficient implementation of a network interior point method, DIMACS Ser Discr Math Theoret Comput Sci, 12, 299-348 (1993) · Zbl 0787.90028 · doi:10.1090/dimacs/012/12
[19] Velazco, MI; Oliveira, ARL; Campos, FF, A note on hybrid preconditioners for large-scale normal equations arising from interior-point methods, Optim Methods Softw, 25, 321-332 (2010) · Zbl 1190.65055 · doi:10.1080/10556780902992829
[20] Wright SJ (1997) Primal-Dual Interior-Point Methods, 289. Society for Industrial and Applied Mathematics, Philadelphia · Zbl 0863.65031
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.