On practical conditions for the existence and uniqueness of solutions to the general equality quadratic programming problem. (English) Zbl 0591.90068

This paper deals with a quadratic programming problem with equality constraints (full rank of the constraint matrix is assumed). The purpose of the paper is to present a set of conditions which characterizes the existence and uniqueness of stationary points. The main result of this paper is with respect to the Lagrangian method of solving a QP, in which the Kuhn-Tucker equations are solved directly. The characterization given in this paper is in terms of the inertia (the number of positive, negative and zero eigenvalues), which is readily available when in the solution of the QP any of the symmetric factorization methods is used to solve the Kuhn-Tucker equations.
Reviewer: I.Kaneko


90C20 Quadratic programming
65K05 Numerical mathematical programming methods
Full Text: DOI


[1] S. Afriat, ”The quadratic form positive definite on a linear manifold”,Proceedings of the Cambridge Philosophical Society 47 (1951) 1–6. · Zbl 0042.01402
[2] J.R. Bunch and L.C. Kaufman, ”Some stable methods for calculating inertia and solving symmetric linear equations”,Mathematics of Computation 31 (1977) 163–179. · Zbl 0355.65023
[3] J.R. Bunch and L.C. Kaufman, ”A computational method for the indefinite quadratic programming problem”,Linear Algebra and its Applications 34 (1980) 341–370. · Zbl 0473.65036
[4] J.R. Bunch and B.N. Parlett, ”Direct methods for solving symmetric indefinite systems of linear equations”,SIAM Journal of Numerical Analysis 8 (1971) 639–655. · Zbl 0222.65038
[5] A.R. Conn and N.I.M. Gould, ”On the location of directions of infinite descent for non-linear programming algorithms”, Technical Report CS-83-21 (1983), University of Waterloo (To appear SIAM Journal on Numerical Analysis).
[6] R.W. Cottle, ”Manifestations of the Schur complement”,Linear Algebra and its Applications 8 (1974) 189–211. · Zbl 0284.15005
[7] A. Dax, Partial pivoting strategies for symmetric Gaussian elimination”,Mathematical Programming 22 (1982) 288–303. · Zbl 0476.90039
[8] G. Debreu, ”Definite and semidefinite quadratic forms”,Econometrica 20 (1952) 295–300. · Zbl 0046.24401
[9] R.S. Dembo, contribution 3.5 in: M.J.D. Powell, ed.,Nonlinear optimization 1981 (Academic Press, London and New York, 1982) pp. 161–162.
[10] D. Djang, ”Algorithmic equivalence in quadratic programming”, Ph.D. Thesis, Stanford University (Stanford, CA, 1979). · Zbl 0387.90084
[11] I.S. Duff and J.K. Reid, ”The multi-frontal solution of indefinite sparse symmetric linear systems”, Report CSS122 (1982) A.E.R.E., Harwell, England.
[12] I.S. Duff, J.K. Reid, N. Munksgaard and H.B. Nielsen, ”Direct solutions of linear equations whose matrix is sparse, symmetric and indefinite”,Journal of the Institute of Mathematics and its Applications 23 (1979) 235–250. · Zbl 0402.65018
[13] R. Fletcher, ”Factorizing symmetric indefinite matrices”,Linear Algebra and its Applications 14 (1956) 257–272. · Zbl 0336.65022
[14] R. Fletcher,Practical methods of optimization, vol. 2: Constrained optimization (John Wiley & Sons, New York, 1981). · Zbl 0474.65043
[15] R. Fletcher and T.L. Freeman, ”A modified Newton method for minimization”,Journal of Optimization Theory and Applications 23 (1977) 357–372. · Zbl 0348.65058
[16] P.E. Gill, N.I.M. Gould, W. Murray, M.A. Saunders and M.H. Wright, ”Range-space methods for convex quadratic programming”, SOL Report SOL82-14 Department of Operations Research, Stanford University (Stanford, CA, 1982).
[17] P.E. Gill and W. Murray, ”Numerically stable methods for quadratic programming”,Mathematical Programming 14 (1978) 349–372. · Zbl 0374.90054
[18] P.E. Gill, W. Murray and M.H. Wright,Practical optimization (Academic Press, London and New York, 1981). · Zbl 0503.90062
[19] D. Goldfarb, ”Curvilinear path steplength algorithms for minimization which use directions of negative curvature”,Mathematical Programming 18 (1980) 31–40. · Zbl 0428.90068
[20] G.H. Golub and C.F. Van Loan,Matrix computations (Johns Hopkins University Press, Baltimore, 1983). · Zbl 0559.65011
[21] N.I.M. Gould, ”The existence and uniqueness of solutions to general equality quadratic programming problems by range-space methods”, Research Report CORR 83-1 University of Waterloo (Waterloo, Ontario, 1983).
[22] E.V. Haynsworth, ”Determination of the inertia of a partitioned Hermitian matrix”,Linear Algebra and its Applications 1 (1968) 73–81. · Zbl 0155.06304
[23] H.W. Kuhn and A.W. Tucker, ”Nonlinear programming”, in J. Neyman, ed.,Proceedings of the second Berkeley symposium on mathematical statistics and probability (University of California Press, Berkeley and Los Angeles, 1951) pp. 481–492. · Zbl 0044.05903
[24] H.B. Mann, ”Quadratic forms with linear constraints”,American Mathematical Monthly 50 (1943) 430–433. · Zbl 0060.04101
[25] J.J. More and D.C. Sorensen, ”On the use of directions of negative curvature in a modified Newton method”,Mathematical Programming 16 (1979) 1–20. · Zbl 0394.90093
[26] J. Orden, ”Stationary points of quadratic functions under linear constraints”,Computer Journal 7 (1974) 238–242. · Zbl 0132.40104
[27] D.C. Sorensen, ”Updating the symmetric indefinite factorization with applications in a modified Newton”, Report ANL 77-49 Argonne National Laboratory (Argonne, IL, 1977).
[28] H. Väliaho, ”On the definity of quadratic forms, subject to linear constraints”,Journal of Optimization Theory and Applications 38 (1982) 143–145. · Zbl 0492.90063
[29] J. H. Wilkinson,The algebraic eigenvalue problem (Clarendon Press, Oxford, 1965). · Zbl 0258.65037
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.