×

zbMATH — the first resource for mathematics

Symmetric indefinite systems for interior point methods. (English) Zbl 0791.90033
Summary: We present a unified framework for solving linear and convex quadratic programs via interior point methods. At each iteration, this method solves an indefinite system whose matrix is \(\left[{-D^{-2}\atop A}{A^ T\atop 0}\right]\) instead of reducing to obtain the usual \(AD^ 2 A^ T\) system. This methodology affords two advantages: (1) it avoids the fill created by explicitly forming the product \(AD^ 2 A^ T\) when \(A\) has dense columns; and (2) it can easily be used to solve nonseparable quadratic programs since it requires only that \(D\) be symmetric. We also present a procedure for converting nonseparable quadratic programs to separable ones which yields computational savings when the matrix of quadratic coefficients is dense.

MSC:
90C05 Linear programming
90C25 Convex programming
90C20 Quadratic programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
Software:
ALPO; symrcm; MINOS
PDF BibTeX Cite
Full Text: DOI
References:
[1] I. Adler, N.K. Karmarkar, M.G.C. Resende and G. Veiga, ”An implementation of Karmarkar’s algorithm for linear programming,”Mathematical Programming 44 (1989) 297–335. · Zbl 0682.90061
[2] E.R. Barnes, ”A variation on Karmarkar’s algorithm for solving linear programming problems,”Mathematical Programming 36 (1986) 174–182. · Zbl 0626.90052
[3] 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
[4] T. J. Carpenter, I.J. Lustig, J.M. Mulvey and D.F. Shanno, ”Separable quadratic programming via a primal-dual interior point method and its use in a sequential procedure,” to appear in:ORSA Journal on Computing. · Zbl 0777.90038
[5] I.I. Dikin, ”Iterative solution of problems of linear and quadratic programming,”Soviet Mathematics Doklady 8 (1967) 674–675. · Zbl 0189.19504
[6] R. Fourer and S. Mehrotra, ”Performance of an augmented system approach for solving least-squares problems in an interior point method for linear programming,”Mathematical Programming Society COAL Newsletter 19 (1991) 26–31.
[7] D.M. Gay, ”Electronic mail distribution of linear programming test problems,”Mathematical Programming Society COAL Newsletter 13 (1985) 10–12.
[8] A. George and J. Liu,Computer Solution of Large Sparse Positive Definite Systems (Prentice-Hall, Englewood Cliffs, NJ, 1981). · Zbl 0516.65010
[9] P.E. Gill, W. Murray, D.B. Ponceleón and M.A. Saunders, ”Preconditioners for indefinite systems arising in optimization,” Technical Report SOL 90-8, Systems Optimization Laboratory, Stanford University (Stanford, CA, 1990). · Zbl 0749.65037
[10] P.E. Gill, W. Murray and M.H. Wright,Numerical Linear Algebra and Optimization, Vol. 1 (Addison-Wesley, Redwood City, CA, 1991). · Zbl 0714.65063
[11] N.K. Karmarkar, ”A new polynomial time algorithm for linear programming,”Combinatorica 4 (1984) 373–395. · Zbl 0557.90065
[12] H. Konno and K. Suzuki, ”A fast algorithm for solving large scale mean-variance models by compact factorization of covariance matrices,” Report IHSS 91-32, Institute of Human and Social Sciences, Tokyo Institute of Technology (Tokyo, 1991). · Zbl 0763.90004
[13] I.J. Lustig, ”Feasibility issues in a primal–dual interior point method for linear programming,”Mathematical Programming 49 (1991) 145–162. · Zbl 0726.90050
[14] I.J. Lustig, R. Marsten and D.F. Shanno, ”Computational experience with a primal–dual interior point method for linear programming,”Linear Algebra and its Applications 152 (1991) 191–222. · Zbl 0731.65049
[15] 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
[16] H.M. Markowitz,Portfolio Selection: Efficient Diversification of Investments (Wiley, New York, 1959).
[17] R.E. Marsten, M.J. Saltzman, D.F. Shanno, G.S. Pierce and J.F. Ballintijn, ”Implementation of a dual affine interior point algorithm for linear programming,”ORSA Journal on Computing 1 (1989) 287–297. · Zbl 0752.90046
[18] S. Mehrotra, ”On the implementation of a (primal-dual) interior point method,” Technical Report 90-03, Department of Industrial Engineering and Management Sciences, Northwestern University (Evanston, IL, 1990). · Zbl 0773.90047
[19] S. Mehrotra, ”Handling free variables in interior point methods,” Technical Report 91-06, Department of Industrial Engineering and Management Sciences, Northwestern University (Evanston, IL, 1991). · Zbl 0737.65050
[20] R.D.C. Monteiro and I. Adler, ”Interior path following primal–dual algorithms. Part I: Linear programming,”Mathematical Programming 44 (1989) 27–42. · Zbl 0676.90038
[21] R.D.C. Monteiro and I. Adler, ”Interior path following primal–dual algorithms. Part II: Convex quadratic programming,”Mathematical Programming 44 (1989) 43–66. · Zbl 0676.90039
[22] B.A. Murtagh and M.A. Saunders, ”MINOS 5.1 user’s guide,” Technical Report SOL 83-20R, Systems Optimization Laboratory, Stanford University (Stanford, CA, 1987).
[23] D.B. Ponceléon, ”Barrier methods for large-scale quadratic programming,” Ph.D. Thesis, Stanford University (Stanford, CA, 1990).
[24] R.J. Vanderbei, ”ALPO: Another linear program optimizer,” Technical Report, AT&T Bell Laboratories (Murray Hill, NJ, 1990). · Zbl 0777.90031
[25] R.J. Vanderbei, ”A brief description of ALPO,” Technical Report, AT&T Bell Laboratories (Murray Hill, NJ, 1990). · Zbl 0744.90056
[26] R.J. Vanderbei, ”Symmetric quasi-definite matrices,” Technical Report SOR-91-10, Department of Civil Engineering and Operations Research, Princeton University (Princeton, NJ, 1991).
[27] R.J. Vanderbei, M.S. Meketon and B.F. Freedman, ”A modification of Karmarkar’s linear programming algorithm,”Algorithmica 1 (1986) 395–407. · Zbl 0626.90056
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.