zbMATH — the first resource for mathematics

An interior point method for quadratic programs based on conjugate projected gradients. (English) Zbl 0778.90048
Summary: We propose an interior point method for large-scale convex quadratic programming where no assumptions are made about the sparsity structure of the quadratic coefficient matrix \(Q\). The interior point method we describe is a doubly iterative algorithm tha invokes a conjugate projected gradient procedure to obtain the search direction. The effects is that \(Q\) appears in a conjugate direction routine rather than in a matrix factorization. By doing this, the matrices to be factored have the same nonzero structure as those in linear programming. Further, one variant of this method is theoretically convergent with only one matrix factorization throughout the procedure.

90C20 Quadratic programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
90C25 Convex programming
Full Text: DOI
[1] E.R. Barnes, ?A variation on Karmarkar’s algorithm for solving linear programming problems,?Math. Programming,36 (1986) 174-182. · Zbl 0626.90052 · doi:10.1007/BF02592024
[2] A. Brooke, D. Kendrick, and A. Meeraus,GAMS: A User’s Guide, The Scientific Press, Redwood City, CA, 1988.
[3] 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, Technical Report SOR-90-2, Department of Civil Engineering and Operations Research, Princeton University, Princeton, NJ, 1990. · Zbl 0777.90038
[4] R.S. Dembo and T. Steihaug, ?Truncated-Newton algorithms for large-scale unconstrained optimization,?Math. Programming 26 (1983), 190-212. · Zbl 0523.90078 · doi:10.1007/BF02592055
[5] I.I. Dikin, ?Iterative solution of problems of linear and quadratic programming,?Soviet Math. Doklady 8 (1967) 674-675. · Zbl 0189.19504
[6] R. Fletcher,Practical Methods of Optimization, John Wiley and Sons, Chichester, England, 1987. · Zbl 0905.65002
[7] R. Fourer and S. Mehrotra, ?Performance of an augmented system approach for solving least-squares problems in an interior point method for linear programming,?COAL Newsletter,19 (1991) 26-30.
[8] P.E. Gill, W. Murray, D.B. Ponceleón, and M.A. Saunders,Solving reduced KKT systems in barrier methods for linear for quadratic programming, Technical Report SOL 91-7, Department of Operations Research, Stanford University, Stanford, CA, 1991.
[9] P.E. Gill, W. Murray, M.A. Saunders, J.A. Tomlin and M.H. Wright, ?On projected Newton methods for linear programming and equivalence to Karmarkar’s projective method,?Math. Programming 36 (1986) 183-209. · Zbl 0624.90062 · doi:10.1007/BF02592025
[10] P.E. Gill, W. Murray, and M.H. Wright,Practical Optimization, Academic Press, New York, NY, 1981. · Zbl 0503.90062
[11] D. Goldfarb and S. Liu, ?AnO(n 3 L) primal interior point algorithm for convex quadratic programming,?Math. Programming 49 (1991) 325-340. · Zbl 0717.90055 · doi:10.1007/BF01588795
[12] G.H. Golub and C.F. Van Loan,Matrix Computations, The Johns Hopkins University Press, Baltimore, MD, 1983. · Zbl 0559.65011
[13] C.C. Gonzaga, ?Large step path-following methods for linear programming, Part I: Barrier function method,?SIAM J. on Optimization,1 (1991) 268-279. · Zbl 0754.90035 · doi:10.1137/0801018
[14] M.A. Jenkins, ?DOMINO-An APL primitive function for matrix inversion-Its implementation and applications,?APL Quote-Quad 4 (1972) 4-15.
[15] N.K. Karmarkar, ?A new polynomial time algorithm for linear programming,?Combinatorica,4 (1984) 373-395. · Zbl 0557.90065 · doi:10.1007/BF02579150
[16] D.G. Luenberger,Linear and Nonlinear Programming, Addison-Wesley Publishing Company, Reading, MA, 1984. · Zbl 0571.90051
[17] I.J. Lustig, R.E. Marsten, and D.F. Shanno, ?On implementing Mehrotra’s predictor-corrector interior point method,?SIAM J. on Optimization,2 (1992) 435-449. · Zbl 0771.90066 · doi:10.1137/0802022
[18] I.J. Lustig, R.E. Marsten, and D.F. Shanno,Starting and restarting the primal-dual interior point method, Technical Report SOR-90-14, Department of Civil Engineering and Operations Research, Princeton University, Princeton, NJ, 1990. · Zbl 0726.90055
[19] I.J. Lustig, R.E. 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 · doi:10.1016/0024-3795(91)90275-2
[20] H.M. Markowitz,Portfolio Selection: Efficient Diversification of Investments, John Wiley, New York, NY, 1959.
[21] K.A. McShane, C.L. Monma, and D.F. Shanno, ?An implementation of a primal-dual interior point method for linear programming,?ORSA J. on Computing,1 (1989) 70-83. · Zbl 0752.90047
[22] 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
[23] R.D.C. Monteiro and I. Adler, ?Interior path following primal-dual algorithms. Part I: Linear programming,?Math. Programming,44 (1989) 27-42. · Zbl 0676.90038 · doi:10.1007/BF01587075
[24] R.D.C. Monteiro and I. Adler, ?Interior path following primal-dual algorithms. Part II: Convex quadratic programming,?Math. Programming,44 (1989) 43-66. · Zbl 0676.90039 · doi:10.1007/BF01587076
[25] B.A. Murtaugh and M.A. Saunders,Minos 5.1 User’s Guide, Technical Report SOL-83-20R, Systems Optimization Laboratory, Stanford University, Stanford, CA, 1983.
[26] J.L. Nazareth, ?Pricing criteria in linear programming,? in N. Megiddo, editor,Progress in Mathematical Programming: Interior Point and Related Methods, Springer-Verlag, New York, NY, 1989, 105-129. · Zbl 0678.90053
[27] D.B. Ponceleón,Barrier methods for large-scale quadratic programming, PhD thesis, Department of Computer Science, Stanford University, Standord, CA, 1990.
[28] R. Tapia, Y. Zhang, M. Saltzman, and A. Weiser,The predictor-corrector interior-point method as a composite Newton method, Technical Report 90-6, Department of Mathematical Sciences, Rice University, Houston, TX, 1990. · Zbl 0846.65024
[29] R.J. Vanderbei,ALPO: Another Linear Program Optimizer, Technical Report, AT&T Bell Laboratories, Murray Hill, NJ, 1990. · Zbl 0777.90031
[30] R.J. Vanderbei,Symmetric quasi-definite matrices, Technical Report SOR-91-10, Department of Civil Engineering and Operations Research, Princeton University, Princeton, NJ, 1991.
[31] 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
[32] 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 · doi:10.1007/BF01840454
[33] Y. Ye and E. Tse, ?An extension of Karmarkar’s projective algorithm for convex quadratic programming,?Math. Programming,44 (1989) 157-179. · Zbl 0674.90077 · doi:10.1007/BF01587086
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.