×

zbMATH — the first resource for mathematics

Solving symmetric indefinite systems in an interior-point method for linear programming. (English) Zbl 0802.90069
Summary: We describe an implementation of a primal-dual path following method for linear programming that solves symmetric indefinite “augmented” systems directly by Bunch-Parlett factorization, rather than reducing these systems to the positive definite “normal equations” that are solved by Cholesky factorization in many existing implementations. The augmented system approach is seen to avoid difficulties of numerical instability and inefficiency associated with free variables and with dense columns in the normal equations approach. Solving the indefinite systems does incur an extra overhead, whose median is about 40% in our tests; but the augmented system approach proves to be faster for a minority of cases in which the normal equations have relatively dense Cholesky factors. A detailed analysis shows that the augmented system factorization is reliable over a fairly large range of the parameter settings that control the tradeoff between sparsity and numerical stability.

MSC:
90C05 Linear programming
Software:
ALPO
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] I. Adler, N. Karmarkar, M.G.C. Resende and G. Veiga, ”An implementation of Karmarkar’s algorithm for linear programming,”Mathematical Programming 44 (1989) 297–336. · Zbl 0682.90061 · doi:10.1007/BF01587095
[2] I. Adler, N. Karmarkar, M.G.C. Resende and G. Veiga, ”Data structures and programming techniques for the implementation Karmarkar’s algorithm,”ORSA Journal on Computing 1 (1989) 84–106. · Zbl 0752.90043
[3] M. Arioli, I.S. Duff and P.P.M. de Rijk, ”On the augmented system approach to sparse least-squares problems,”Numerische Mathematik 55 (1989) 667–684. · Zbl 0678.65024 · doi:10.1007/BF01389335
[4] R.E. Bixby, ”Implementing the simplex method: The initial basis,”ORSA Journal on Computing 4 (1992) 267–284. · Zbl 0759.90063
[5] P.T. Boggs, P.D. Domich, J.R. Donaldson and C. Witzgall, ”Optimal 3-dimensional methods for linear programming,” MISTIR 89-4225, Center for Computing and Applied Mathematics, National Institute of Standards and Technology (Gaithersburg, MD, 1989). · Zbl 0753.90040
[6] Å. Björck, ”Iterative refinement of linear least-squares solutions,”BIT 7 (1967) 257–278. · Zbl 0159.20404 · doi:10.1007/BF01939321
[7] J.R. Bunch and B.N. Parlett, ”Direct methods for solving symmetric indefinite systems of linear equations,”SIAM Journal on Numerical Analysis 8 (1971) 639–655. · Zbl 0222.65038 · doi:10.1137/0708060
[8] I.C. Choi, C.L. Monma and D.F. Shanno, ”Further development of a primal–dual interior point method,”ORSA Journal on Computing 2 (1990) 304–311. · Zbl 0757.90051
[9] I.S. Duff, N.I.M. Gould, J.K. Reid, J.A. Scott and K. Turner, ”The factorization of sparse symmetric indefinite matrices,”IMA Journal of Numerical Analysis 11 (1991) 181–204. · Zbl 0739.65018 · doi:10.1093/imanum/11.2.181
[10] I.S. Duff and J.K. Reid, ”The multifrontal solution of indefinite sparse symmetric linear equations,”ACM Transactions on Mathematical Software 9 (1983) 302–325. · Zbl 0515.65022 · doi:10.1145/356044.356047
[11] R. Fourer and S. Mehrotra, ”Solving Symmetric Indefinite Systems in an Interior-Point Method for Linear Programming,” Technical Report 92-01, Department of Industrial Engineering and Management Sciences, Northwestern University (Evanston, IL, 1992). · Zbl 0802.90069
[12] D.M. Gay, ”Electronic mail distribution of linear programming test problems,”Committee on Algorithms Newsletter 13 (1985) 10–12.
[13] P.E. Gill, W. Murray, D.B. Ponceleón and M.A. Saunders, ”Solving reduced KKT systems in barrier methods for linear and quadratic programming,” Technical Report SOL 91-7, Systems Optimization Laboratory, Stanford University (Stanford, CA, 1991).
[14] P.E. Gill, W. Murray, M.A. Saunders, J.A. Tomlin and M.H. Wright, ”On projected Newton barrier methods for linear programming,”Mathematical Programming 36 (1986) 183–209. · Zbl 0624.90062 · doi:10.1007/BF02592025
[15] N. Karmarkar, ”A new polynomial time algorithm for linear programming,”Combinatorica 4 (1984) 373–393. · Zbl 0557.90065 · doi:10.1007/BF02579150
[16] M. Kojima, S. Mizuno and A. Yoshise, ”A primal–dual interior point algorithm for linear programming,” in: N. Megiddo, ed.,Progress in Mathematical Programming: Interior-Point and Related Methods (Springer, New York, 1989) pp. 131–158. · Zbl 0708.90049
[17] I.J. Lustig, R.E. Marsten and D.F. Shanno, ”On implementing Mehrotra’s predictor-corrector interior-point method for linear programming,”SIAM Journal on Optimization 2 (1992) 435–449. · Zbl 0771.90066 · doi:10.1137/0802022
[18] I.J. Lustig, J.M. Mulvey and T.J. Carpenter, ”Formulating two-stage stochastic programs for interior point methods,”Operations Research 39 (1991) 757–770. · Zbl 0739.90048 · doi:10.1287/opre.39.5.757
[19] H.M. Markowitz, ”The elimination form of the inverse and its application to linear programming,”Management Science 3 (1957) 255–269. · Zbl 0995.90592 · doi:10.1287/mnsc.3.3.255
[20] K.A. McShane, C.L. Monma and D.F Shanno, ”An implementation of a primal–dual interior point method for linear programming,”ORSA Journal on Computing 1 (1989) 70–83. · Zbl 0752.90047
[21] S. Mehrotra, ”On the implementation of a primal–dual interior point method,”SIAM Journal on Optimization 2 (1992) 575–601. · Zbl 0773.90047 · doi:10.1137/0802028
[22] S. Mehrotra, ”Higher order methods and their performance,” Technical Report 90-16R1, Department of Industrial Engineering and Management Sciences, Northwestern University (Evanston, IL, 1991). · Zbl 0737.65050
[23] S. Mehrotra, ”Handling free variables in interior methods,” Technical Report 91-06, Department of Industrial Engineering and Management Sciences, Northwestern University (Evanston, IL, 1991). · Zbl 0737.65050
[24] S. Mehrotra and Y. Ye, ”On finding the optimal facet of linear programs,” Technical Report 91-10. Department of Industrial Engineering and Management Sciences, Northwestern University (Evanston, IL, 1991).
[25] R.D.C. Monteiro and I. Adler, ”Interior path following primal–dual algorithms. Part I: Linear programming,”Mathematical Programming 44 (1989) 27–41. · Zbl 0676.90038 · doi:10.1007/BF01587075
[26] R.D. Skeel, ”Scaling for numerical stability in Gaussian elimination,”Journal of the Association for Computing Machinery 26 (1979) 494–526. · Zbl 0435.65035
[27] K. Turner, ”Computing projections for the Karmarkar algorithm,”Linear Algebra and its Applications 152 (1991) 141–154. · Zbl 0729.65043 · doi:10.1016/0024-3795(91)90272-X
[28] R.J. Vanderbei, ”Splitting dense columns in sparse linear systems,” Manuscript, AT&T Bell Laboratories (Murray Hill, NJ, 1990). · Zbl 0727.65034
[29] R.J. Vanderbei, ”ALPO: another linear program solver,” Manuscript, AT&T Bell Laboratories (Murray Hill, NJ, 1990). · Zbl 0777.90031
[30] R.J. Vanderbei and T.J. Carpenter, ”Symmetric indefinite systems for interior-point methods,” Technical Report SOR-91-7, Department of Civil Engineering and Operations Research, Princeton University (Princeton, NJ, 1991). · Zbl 0791.90033
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.