Abstract
We present a general active set algorithm for the solution of a convex quadratic programming problem having a parametrized Hessian matrix. The parametric Hessian matrix is a positive semidefinite Hessian matrix plus a real parameter multiplying a symmetric matrix of rank one or two. The algorithm solves the problem for all parameter values in the open interval upon which the parametric Hessian is positive semidefinite. The algorithm is general in that any of several existing quadratic programming algorithms can be extended in a straightforward manner for the solution of the parametric Hessian problem.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
E.W. Barankin and R. Dorfman, On quadratic programming, University of California Publications in Statistics 2(1958)285.
M.J. Best, Equivalence of some quadratic programming algorithms, Math. Progr. 30 (1984) 71.
M.J. Best, An algorithm for the solution of the parametric quadratic programming problem, CORR Report 82-24, University of Waterloo, Ontario (1982).
M.J. Best and K. Ritter, An effective algorithm for quadratic minimization problems, MRC Technical Summary Report No. 1691, University of Wisconsin, Madison (1976).
R.B. Bland, New finite pivoting rules for the simplex method, Mathematics of Operations Research 2(1977)103.
J.C.G. Boot, On sensitivity analysis in convex quadratic programming problems, Oper. Res. 11(1963)771.
R.J. Caron, A parametrized Hessian quadratic programming problem, Ph.D. Thesis, Dept. of Combinatories and Optimization, University of Waterloo, Ontario (1983).
R. Fletcher, A general quadratic programming algorithm, Journal of the Institute of Mathematics and its Applications 7(1971)76.
P.E. Gill and W. Murray, Numerically stable methods for quadratic programming, Math. Progr. 14(1978)349.
D. Goldfarb and A. Idnani, Dual and primal-dual methods for solving strictly convex quadratic programs, in:Lecture Notes in Mathematics, Vol. 909, ed. J.P. Hennart (Springer-Verlag, Berlin 1982) p. 226.
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, Faculty of Mathematics, University of Waterloo, Ontario (1983).
O.L. Mangasarian,Nonlinear Programming (McGraw-Hill, New York, 1969).
J.D. Pearson, Variable metric methods of minimisation, The Computer Journal 12(1969)171.
K. Ritter, A method for solving nonlinear maximum-problems depending on parameters (translated by M. Meyer) Naval Research Logistics Quarterly 14(1967)147.
K. Ritter, On parametric linear and quadratic programming problems, MRC Technical Summary Report No. 2197, University of Wisconsin, Madison (1981).
J. Sherman and W.J. Morrison, Adjustment of an inverse matrix corresponding to changes in the elements of a given column or a given row of the original matrix, Ann. of Mathematical Statistics 20(1949)621.
C. van de Panne and A. Whinston, The symmetric formulation of the simplex method for quadratic programming, Econometrica 37(1969)507.
M. Woodbury, Inverting modified matrices, Memorandum Report 42, Statistical Research Group, Princeton University, New Jersey (1950).
Author information
Authors and Affiliations
Additional information
This research was supported by the Natural Sciences and Engineering Research Council under Grant No. A8189 and under a Postgraduate Scholarship, by an Ontario Graduate Scholarship, and by the University of Windsor Research Board under Grant No. 9432.
Rights and permissions
About this article
Cite this article
Best, M.J., Caron, R.J. A parameterized hessian quadratic programming problem. Ann Oper Res 5, 371–394 (1986). https://doi.org/10.1007/BF02022081
Issue Date:
DOI: https://doi.org/10.1007/BF02022081