Abstract
An efficient and numerically stable dual algorithm for positive definite quadratic programming is described which takes advantage of the fact that the unconstrained minimum of the objective function can be used as a starting point. Its implementation utilizes the Cholesky and QR factorizations and procedures for updating them. The performance of the dual algorithm is compared against that of primal algorithms when used to solve randomly generated test problems and quadratic programs generated in the course of solving nonlinear programming problems by a successive quadratic programming code (the principal motivation for the development of the algorithm). These computational results indicate that the dual algorithm is superior to primal algorithms when a primal feasible point is not readily available. The algorithm is also compared theoretically to the modified-simplex type dual methods of Lemke and Van de Panne and Whinston and it is illustrated by a numerical example.
Similar content being viewed by others
References
R.H. Bartels, G.H. Golub, and M.A. Saunders, “Numerical techniques in mathematical programming”. in: J.B. Rosen, O.I. Mangasarian and K. Ritter, eds.,Nonlinear programming (Academic Press, New York, 1970) pp. 123–176.
E.M.L. Beale, “On minimizing a convex function subject to linear inequalities,”Journal of the Royal Statistical Society Series B 17 (1955) 173–184.
E.M.L. Beale, “On quadratic programming,”Naval Research Logistics Quarterly 6 (1959) 227–243.
M.G. Biggs, “Constrained minimization using recursive quadratic programming: some alternative subproblem formulations,” in: L.C.W. Dixon and G.P. Szego, eds.,Towards global optimization (North-Holland, Amsterdam, 1975) pp. 341–349.
J.W. Bunch and L. Kaufman, “Indefinite quadratic programming,” Computing Science Technical Report 61, Bell. Labs, Murray Hill. NJ (1977).
A.R. Conn and J.W. Sinclair, “Quadratic programming via a nondifferentiable penalty function,” Department of Combinatorics and Optimization Research Report CORR 75-15, University of Waterloo, Waterloo, Ont. (1975).
R.W. Cottle and G.B. Dantzig, “Complementary pivot theory of mathematical programming,” in: G.B. Dantzig and A.F. Veinott, eds.Lectures in applied mathematics II, Mathematics of the decision sciences, Part 1 (American Mathematical Society, Providence, RI, 1968) pp 115–136.
J.W. Daniel, W.B. Graggs, L. Kaufman and G.W. Stewart, “Reorthogonalization and stable algorithms for updating the Gram-Schmidt QR factorizations,”Mathematics of Computation 30 (1976) 772–795.
A. Dax “The gradient projection method for quadratic programming,” Institute of Mathematics Report, The Hebrew University of Jerusalem (Jerusalem, 1978).
G.B. Dantzig,Linear programming and extensions (Princeton University Press, Princeton, NJ, 1963) Chapter 24, Section 4.
R. Fletcher, “The calculation of feasible points for linearly constrained optimization problems”.
R. Fletcher, “A FORTRAN subroutine for quadratic programming”, UKAEA Research Group Report. AERE R6370 (1970).
R. Fletcher, “A general quadratic programming algorithm”,Journal of the Institute of Mathematics and Its Applications (1971) 76–91.
P.E. Gill, G.H. Golub, W. Murray and M.A. Saunders, “Methods for modifying matrix factorizations,”Mathematics of Computation 28 (1974) 505–535.
P.E. Gill and W. Murray, “Numerically stable methods for quadratic programming,”Mathematical programming 14 (1978) 349–372.
D. Goldfarb, “Extension of Newton's method and simplex methods for solving quadratic programs,” in: F.A. Lootsma, ed.,Numerical methods for nonlinear optimization (Academic Press, London, 1972) pp. 239–254.
D. Goldfarb, “Matrix factorizations in optimization of nonlinear functions subject to linear constraints,”Mathematical Programming 10 (1975) 1–31.
D. Goldfarb and A. Idnani, “Dual and primal-dual methods for solving strictly convex quadratic programs,” in: J.P. Hennart, ed.,Numerical Analysis, Proceedings Cocoyoc, Mexico 1981, Lecture Notes in Mathematics 909 (Springer-Verlag, Berlin, 1982) pp. 226–239.
A.S. Goncalves, “A primal-dual method for quadratic programming with bounded variables,” in F.A. Lootsma, ed.,Numerical methods for nonlinear optimization (Academic Press, London, 1972) pp. 255–263.
M.D. Grigoriadis and K. Ritter, “A parametric method for semidefinite quadratic programs,”SIAM Journal of Control 7 (1969) 559–577.
S-P. Han, “Superlinearly convergent variable metric algorithms for general nonlinear programming problems,”Mathematical Programming 11 (1976) 263–282.
S-P. Han, “Solving quadratic programs by an exact penalty function,” MRC Technical Summary Report No. 2180, M.R.C., University of Wisconsin (Madison, WI, 1981).
A.U. Idnani, “Extension of Newton's method for solving positive definite quadratic programs— A computational experience,” Master's Thesis, City College of New York, Department of Computer Science (New York, 1973).
A.U. Idnani, “Numerically stable dual projection methods for solving positive definite quadratic programs,” Ph.D. Thesis. City College of New York. Department of Computer Science, (New York, 1980).
C.L. Lawson and R.J. Hanson,Solving least squares problems (Prentice-Hall, Engelwood Cliffs, N.J., 1974).
C.E. Lemke, “A method of solution for quadratic programs,”Management Science 8 (1962) 442–453.
R. Mifflin, “A stable method for solving certain constrained least squares problems,”Mathematical Programming 16 (1979) 141–158.
W. Murray “An algorithm for finding a local minimum of an indefinite quadratic program”, NPL NAC Report No. 1 (1971).
B.A. Murtagh and M.A. Saunders, “Large-scale linearly constrained optimization,”Mathematical Programming 14 (1978) 41–72.
M.J.D. Powell, “A fast algorithm for nonlinearly constrained optimization calculations,” in:Numerical analysis, Dundee, 1977, Lecture Notes in Mathematics 630 (Springer Verlag, Berlin, 1978) pp. 144–157.
M.J.D. Powell, “An example of cycling in a feasible point algorithm”,Mathematical Programming 20 (1981) 353–357.
K. Ritter, “Ein Verfahren zur Lösung parameter-abhängiger, nichtlinearer Maximum-Probleme”,Unternehmensforschung 6 (1962) 149–166: English transl.,Naval Research Logistics Quarterly 14 (1967) 147–162.
J.B. Rosen, “The gradient projection method for nonlinear programming. Part 1. Linear constraints,”SIAM Journal of Applied Mathematics 8 (1960) 181–217.
J.B. Rosen and S. Suzuki, “Construction of nonlinear programming test problems”,Communications of the ACM (1965) 113.
K. Schittkowski,Nonlinear programming codes—Information, tests, performance. Lecture Notes in Economics and Mathematical Systems, No. 183 (Springer-Verlag, Berlin, 1980).
K. Schittkowski and J. Stoer, “A factorization method for the solution of constrained linear least squares problems allowing subsequent data changes,”Numerische Mathematik 31 (1979) 431–463.
J. Stoer, “On the numerical solution of constrained least squares problems”,SIAM Journal on Numerical Analysis 8 (1971) 382–411.
H. Theil and C. Van De Panne, “Quadratic programming as an extension of conventional quadratic maximization,”Management Science 7 (1960) 1–20.
C. Van de Panne and A. Whinston, “The simplex and the dual method for quadratic programming,”Operations Research Quarterly 15 (1964) 355–389.
R.B. Wilson, “A simplicial algorithm for concave programming,” Dissertation, Garduate School of Business Administration, Harvard University (Boston, MA, 1963).
P. Wolfe, “The simplex method for quadratic programming,”Econometrica 27 (1959) 382–398.
Author information
Authors and Affiliations
Additional information
This research was supported in part by the Army Research Office under Grant No. DAAG 29-77-G-0114 and in part by the National Science Foundation under Grant No. MCS-6006065.
Rights and permissions
About this article
Cite this article
Goldfarb, D., Idnani, A. A numerically stable dual method for solving strictly convex quadratic programs. Mathematical Programming 27, 1–33 (1983). https://doi.org/10.1007/BF02591962
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02591962