×

A quadratic programming algorithm for large and sparse problems. (English) Zbl 0746.90048

This paper describes a primal feasible algorithm for quadratic programming problems. It is specially designed to cope with the large and sparse instances of this type with their structural and numerical algorithmic specialities. The reduced gradient methods in an active set framework are used. The algorithmic scheme makes use of some principles that have not been used for the general large and sparse quadratic programming so far.

MSC:

90C20 Quadratic programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
90C06 Large-scale problems in mathematical programming

Software:

NLPNET; CONOPT; MINOS
PDF BibTeX XML Cite
Full Text: EuDML Link

References:

[1] R. G. Bland: New finite pivoting rules for the simplex method. Math. Oper. Res. 2 (1977), 103-107. · Zbl 0408.90050
[2] P. H. Calamai, J. J. More: Projected gradient methods for linearly constrained problems. Math. Programming 39 (1987), 93-116. · Zbl 0634.90064
[3] T. F. Coleman: Large Sparse Numerical Optimization. (Lecture Notes in Computer Science 165.) Springer-Verlag, Berlin-Heidelberg-New York-Tokyo 1984. · Zbl 0536.65047
[4] R. S. Dembo: NLPNET - User’s Guide and System Documentation. School of Organiza- tion and Management Working Paper Series B # 70, Yale University, New Haven, CT 1983.
[5] R. S. Dembo: A primal truncated Newton algorithm with application to large-scale nonlinear network optimization. Math. Programming Study 31 (1987), 43-71. · Zbl 0635.90072
[6] R. S. Dembo S. C. Eisenstat, T. Steihaug: Inexact Newton methods. SIAM J. Numer. Anal. 79(1982), 400-408. · Zbl 0478.65030
[7] R. S. Dembo, J. G. Klincewicz: Dealing with degeneracy in reduced gradient algorithms. Math. Programming 31 (1985), 357-363. · Zbl 0573.90083
[8] R. S. Dembo, T. Sahi: A convergent active-set strategy for linearly-constrained optimization. School of Organization and Management Working Paper Series B # 80, Yale University 1984.
[9] R. S. Dembo, T. Steihaug: Truncated-Newton algorithms for large-scale unconstrained optimization. Math. Programming 26 (1983), 190-212. · Zbl 0523.90078
[10] A. Drud: CONOPT: A GRG code for large sparse dynamic nonlinear optimization problems. Math. Programming 31 (1985), 153-191. · Zbl 0557.90088
[11] L. F. Escudero: An Algorithm for Large-scale Quadratic Programming and its Extensions to the Linearly Constrained Case. IBM Scientic Centre Report SCR-01.81, Madrid 1981.
[12] Y. Fan L. Lasdon, S. Sarkar: Experiments with successive quadratic programming algorithms. J. Optim. Theory Appl. 56 (1988), 359-383. · Zbl 0619.90056
[13] R. Fletcher: Practical Methods of Optimization. Vol. 2: Constrained Optimization. J. Wiley, New York-Chichester-Brisbane-Toronto 1981. · Zbl 0474.65043
[14] P. E. Gill, W. Murray: Newton-type methods for unconstrained and linearly constrained optimization. Math. Programming 28 (1974), 311 - 350. · Zbl 0297.90082
[15] P. E. Gill, W. Murray: The Computation of Lagrange Multiplier Estimates for Constrained Minimization. Rep. NAC 77, National Physical Laboratory, England 1976. · Zbl 0423.90073
[16] W. Hock, K. Schittkowski: Test Examples for NLP Codes. Springer-Verlag, Berlin-Heidelberg-New York 1981. · Zbl 0452.90038
[17] L. Luksan: System UFO. User’s Guide-version 1989(in Czech). Res. Rep. V-441, SVT CSAV, Prague, 1989.
[18] H. M. Markowitz: The elimination form of the inverse and its applications to linear programming. Management Sci. 3 (1957), 225-269. · Zbl 0995.90592
[19] B. A. Murtagh: Advanced Linear Programming: Computation and Practice. McGraw Hill New York 1981. · Zbl 0525.90062
[20] B. A. Murtagh, M. A. Saunders: Large-scale linearly constrained optimization. Math. Programming 14 (1978), 41 - 72. · Zbl 0383.90074
[21] B. A. Murtagh, M. A. Saunders: A projected Lagrangian algorithm and its implementation for sparse nonlinear constraints. Math. Programming Study 16 (1982), 84-117. · Zbl 0477.90069
[22] B. A. Murtagh, M. A. Saunders: MINOS 5.1 User’s Guide. Tech. Rep. SOL 83-20 R, Dept. Oper. Res., Stanford University, Stanford, CA, 1983, revised 1987.
[23] O. Osterby, Z. Zlatev: Direct methods for sparse matrices. (Lecture Notes in Computer Science 157.) Springer-Verlag, Berlin -Heidelberg-New York-Tokyo 1983. · Zbl 0516.65011
[24] S. Pissanetzky: Sparse Matrix Technology. Academic Press, London-Orlando-San Die- go-New York-Austin-Toronto-Montreal-Sydney-Tokyo 1984. · Zbl 0536.65019
[25] J. K. Reid: On the method of conjugate gradients for the solution of large sparse systems of linear equations. Large Sparse Sets of Linear Equations (J. K. Reid, Academic Press, London 1971, pp. 231 - 254.
[26] J. K. Reid: Fortran Subroutines for Handling Sparse Linear Programming Bases. Rep. AERE Harwell, R. 8269. Harwell 1976.
[27] J. K. Reid: A sparsity-exploiting variant of the Bartels-Golub decomposition for linear programming bases. Math. Programming 24 (1982), 55-69. · Zbl 0492.90050
[28] P. S. Ritch: Discrete optimal control with multiple constraints I: Constraint separation and transformation technique. Automatica 9 (1973), 415-429. · Zbl 0256.49034
[29] M. Tůma: Large and Sparse Quadratic Programming (in Czech). Ph.D. Thesis, SVT CSAV, Prague 1989.
[30] M. Tůma: SPOPT-Program System for the Solution of Large Sparse Problems of Linear and Quadratic Programming (in Czech). Res. Rep. V-391, SVT CSAV, Praha 1989.
[31] Z. Zlatev: A survey of the advances in the exploitation of the sparsity in the solution of large problems. Internat. Congress on Comp. and Appl. Math., University of Leuven, Belgium 1986. · Zbl 0639.65020
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.