×

zbMATH — the first resource for mathematics

Implementing Cholesky factorization for interior point methods of linear programming. (English) Zbl 0819.65097
Summary: Every iteration of an interior point method of large scale linear programming requires computing at least one orthogonal projection of the objective function gradient onto the null space of a linear operator defined by the problem constraint matrix \(A\). The orthogonal projection itself is in turn dominated by the inversion of the symmetric matrix of form \(A \theta A^ T\), where \(\theta\) is a diagonal weighting matrix.
In this paper several specific issues of implementation of the Cholesky factorization that can be applied for solving such equations are discussed. The code called CHFACT being the result of this work is shown to produce comparably sparse factors as the state-of-the-art implementation of the Cholesky decomposition of A. George and J. W. H. Liu [Computer solution of large sparse positive definite systems. Prentice-Hall Series in Computational Mathematics. Englewood Cliffs, New Jersey: Prentice Hall, Inc. XII. (1981; Zbl 0516.65010)]. It has been used for computing projections in an efficient implementation of a higher order primal-dual interior point method of A. Altman and J. Gondzio [Arch. Control. Sci. 2, No. 1-2, 23-40 (1993; Zbl 0799.90083); Eur. J. Oper. Res. 66, No. 1, 158-160 (1993; Zbl 0775.90285)].
Although primary aim of developing CHFACT was to include it into an LP optimizer, the code may equally well be used to solve general large sparse positive definite systems arising in different applications.

MSC:
65K05 Numerical mathematical programming methods
90C05 Linear programming
65F05 Direct numerical methods for linear systems and matrix inversion
90C06 Large-scale problems in mathematical programming
65F50 Computational methods for sparse matrices
Software:
HOPDM; MA27; symrcm; CHFACT; IPMLO
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] DOI: 10.1007/BF01587095 · Zbl 0682.90061
[2] Altman A. Gondzio J. 1992a An efficient implementation of a higher order primal-dual interior point method for large sparse linear programs Technical Report ZTSW-l/A214/92, Systems Research Institute, Polish Academy of Sciences, Warsaw, June 1992, revised in September 1992, to appear in: Archives of Control Sciences · Zbl 0799.90083
[3] Altman A., European Journal of Operations Research (1992)
[4] DOI: 10.1007/BF01389335 · Zbl 0678.65024
[5] Billionnet A., RAIRO Recherche Operationnelle 23 pp 289– (1989)
[6] Choi I.C., ORSA Journal on Computing 2 pp 304– (1990)
[7] DOI: 10.1016/0024-3795(87)90109-1 · Zbl 0644.65025
[8] Duff I.S., Direct methods for sparse matrices (1989) · Zbl 0666.65024
[9] Duff I.S., MA27–A set of FORTRAN subroutines for solving sparse symmetric sets of linear equations (1982)
[10] DOI: 10.1002/nme.1620180804 · Zbl 0492.65012
[11] DOI: 10.1007/BF02023049 · Zbl 0714.90064
[12] Gay D. M. Electronic mail distribution of linear programming test problems 1985 Mathematical Programming Society COAL Newsletter
[13] George A., User’s guide for SPARSPACK: Waterloo sparse linear equations package (1980)
[14] George A., Computer Solution of Large Sparse Positive Definite Systems (1981) · Zbl 0516.65010
[15] DOI: 10.1137/1031001 · Zbl 0671.65024
[16] DOI: 10.1137/0905041 · Zbl 0559.65042
[17] DOI: 10.1007/BF02592025 · Zbl 0624.90062
[18] DOI: 10.1016/S0927-0507(89)01003-0
[19] Golub G.H., Matrix Computations (1983) · Zbl 0559.65011
[20] DOI: 10.1080/02331939208843796 · Zbl 0814.65056
[21] Gondzio J. Tachat D. The design and application of IPMLO–a FORTRAN library for linear optimization with interior point methods University of Paris Dauphine Paris, France 1991 Technical Report No. 108, LAMSADE, January 1992, revised in November 1992. · Zbl 0860.90085
[22] DOI: 10.1016/0377-0427(87)90199-3 · Zbl 0627.65040
[23] DOI: 10.1007/BF01582905 · Zbl 0739.90042
[24] DOI: 10.1287/mnsc.3.3.255 · Zbl 0995.90592
[25] DOI: 10.1145/355887.355893 · Zbl 0438.65035
[26] DOI: 10.1145/355984.355989 · Zbl 0478.65016
[27] DOI: 10.1145/355993.356000
[28] DOI: 10.1007/BF01580753 · Zbl 0652.90069
[29] DOI: 10.1109/PROC.1967.6011
[30] Vanderbei, R.J. 1991. Dense columns in interior-point methods for LP, in. Proceedings of the IMACS’ 91 World Congress on Computation and Applied Mathematics. 1991, Dublin, Ireland.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.