Abstract
Because of the many important applications of quadratic programming, fast and efficient methods for solving quadratic programming problems are valued. Goldfarb and Idnani (1983) describe one such method. Well known to be efficient and numerically stable, the Goldfarb and Idnani method suffers only from the restriction that in its original form it cannot be applied to problems which are positive semi-definite rather than positive definite. In this paper, we present a generalization of the Goldfarb and Idnani method to the positive semi-definite case and prove finite termination of the generalized algorithm. In our generalization, we preserve the spirit of the Goldfarb and Idnani method, and extend their numerically stable implementation in a natural way.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
N. Boland, C.J. Goh and A.I. Mees, An algorithm for solving quadratic network flow problems,Applied Mathematics Letters 4 (1991) 61–64.
N. Boland, C.J. Goh and A.I. Mees, An algorithm for non-linear network programming: implementation, results and comparisons,Journal of the Operational Research Society 43 (1992) 979–992.
N. Boland, Some problems in network optimization and quadratic programming, PhD Thesis, Department of Mathematics, University of Western Australia (1992).
D. Burton and Ph.L. Toint, On an instance of the inverse shortest paths problem,Mathematical Programming 53 (1992) 45–61.
A.R. Conn, N.I.M. Gould, M. Lescrenier and Ph.L. Toint, Performance of a multifrontal scheme for partially separable optimization, Research Report CS-88-04, Computer Science Department, University of Waterloo (1988).
A.R. Conn, N.I.M. Gould and Ph.L. Toint, An introduction to the structure of large scale nonlinear optimization problems and the LANCELOT project, Research Report CS-89-63, Computer Science Department, University of Waterloo (1989).
A.R. Conn, N. Gould and Ph.L. Toint, Large-scale nonlinear constrained optimization, Research Report RAL-92-066, Rutherford Appleton Laboratory (1992).
J. Demmel, Jacobis method is more accurate than QR,SIAM Journal on Matrix Analysis and Applications 13 (1992) 1204–1245.
R. Fletcher,Practical Methods of Optimization (Wiley, Chichester, 1987).
A.T. Ernst, X.Q. Yang and N.L. Boland, Exterior point methods for quadratic cost multicommodity flow, submitted for publication, 1996.
P.E. Gill and W. Murray, Numerically stable methods for quadratic programming,Mathematical Programming 14 (1978) 349–372.
P.E. Gill, W. Murray and M. Wright,Practical Optimization (Academic Press, London, 1981).
P.E. Gill, W. Murray and M. Wright,Numerical Linear Algebra and Optimization (Addison-Wesley, Reading, MA, 1991).
D. Goldfarb and A. Idnani, A numerically stable dual method for solving strictly convex quadratic programs,Mathematical Programming 27 (1983) 1–33.
G.H. Golub and C.F. Van Loan,Matrix Computations (Johns Hopkins University Press, Baltimore, MD, 1989).
S.P. Han, Superlinearly convergent variable metric algorithms for general nonlinear programming problems,Mathematical Programming 11 (1976) 263–282.
S.P. Han, A globally convergent method for nonlinear programming,Journal of Optimization Theory and Applications 22 (1977) 297–309.
Y.Y. Lin and J.S. Pang, Iterative methods for large convex quadratic programs: a survey,SIAM Journal on Control and Optimization 25 (1987) 383–411.
W. Murray and F.J. Prieto, A sequential quadratic programming algorithm using incomplete solution of the subproblem, Technical Report SOL90-12, Operations Research Department, Stanford University (1990).
B.N. Parlett,The Symmetric Eigenvalue Problem (Prentice-Hall, Englewood Cliffs, NJ, 1980).
M.J.D. Powell, A fast algorithm for nonlinearly constrained optimization calculations, in: G.A. Watson, ed.,Numerical analysis Dundee 1977, Lecture Notes in Mathematics 630 (Springer, Berlin, 1977) 144–157.
M.J.D. Powell, The convergence of variable metric methods for nonlinearly constrained optimization calculations, in: O.L. Magasarian, R.R. Meyer and S.M. Robinson, eds.,Nonlinear Programming 3 (Academic Press, New York, 1978) 27–63.
M.J.D. Powell, Variable metric methods for constrained optimization, in: A. Bachen, M. Grotschel and B. Korte, eds.,Mathematical Programming: The State of the Art (Springer, Berlin, 1983) 288–311.
M.J.D. Powell, ZQPCVX: a Fortran subroutine for convex quadratic programming, Report DAMTP/1983/NA17, University of Cambridge (1983).
M.J.D. Powell, On the quadratic programming algorithm of Goldfarb and Idnani,Mathematical Programming Study 25 (1985) 46–61.
K. Schittkowski, The nonlinear programming method of Wilson, Han, and Powell with an augmented Lagrangian type line search function, Part I: convergence analysis,Numerische Mathematik 38 (1981) 83–114.
K. Schittkowski, On the convergence of a sequential quadratic programming method with an augmented Lagrangian line search function,Mathematische Operationsforschung und Statistik, Ser. Optimization 14 (1983) 197–216.
J. Stoer, A dual algorithm for solving degenerate linearly constrained linear least squares problems,Journal of Numerical Linear Algebra with Applications 1 (1992) 103–131.
Ph.L. Toint and D. Tuyttens, On large scale nonlinear network optimization,Mathematical Programming 48 (1990) 125–159.
R.B. Wilson, A simplicial algorithm for concave programming, Ph.D. Dissertation, Graduate School of Business Administration, Harvard University, Boston (1963).
Author information
Authors and Affiliations
Additional information
Supported in part by ATERB, NSERC and the ARC.
Much of this work was done in the Department of Mathematics at the University of Western Australia and in the Department of Combinatorics and Optimization at the University of Waterloo.
Rights and permissions
About this article
Cite this article
Boland, N.L. A dual-active-set algorithm for positive semi-definite quadratic programming. Mathematical Programming 78, 1–27 (1996). https://doi.org/10.1007/BF02614503
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02614503