Abstract
We propose an exterior Newton method for strictly convex quadratic programming (QP) problems. This method is based on a dual formulation: a sequence of points is generated which monotonically decreases the dual objective function. We show that the generated sequence converges globally and quadratically to the solution (if the QP is feasible and certain nondegeneracy assumptions are satisfied). Measures for detecting infeasibility are provided. The major computation in each iteration is to solve a KKT-like system. Therefore, given an effective symmetric sparse linear solver, the proposed method is suitable for large sparse problems. Preliminary numerical results are reported.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
A.V. Aho, J.E. Hopcroft, and J.D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley Publishing Company, 1974.
A.B. Berkelaar, C. Roos, and T. Terlaky, “The optimal set and optimal partition approach to linear and quadratic programming,” Chapter 6 in Advances in Sensitivity Analysis and Parametric Programming, H.J. Greenberg and T. Gal (Eds.), Kluwer Academic Publishers: Dordrecht, 1997.
T.J. Carpenter and D.F. Shanno, “An interior point method for quadratic programs based on conjugate projected gradients,” Computational Optimization and Applications, vol. 2, pp. 5-28 (1993).
T.F. Coleman and L.A. Hulbert, “A globally and superlinearly convergent algorithm for convex quadratic programming with simple bounds,” SIAM Journal on Optimization, vol. 3, pp. 298-321 (1993).
J.E. Dennis, Jr. and R.B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice-Hall: Englewood Cliffs, NJ, 1983.
I.I. Dikin, “Iterative solution of problems of linear and quadratic programming,” Soviet Mathematics Doklady, vol. 8, pp. 674-675 (1967).
R. Fletcher, Practical Methods of Optimization, 2nd edition, John Wiley and Sons: New York, 1987.
P.E. Gill, W. Murray, and M.H. Wright, Practical Optimization, Academic Press: London, 1981.
D. Goldfarb, “Extensions of Newton's method and simplex methods for solving quadratic programs,” in Numerical Methods for Nonlinear Optimization, F.A. Lootsman (Ed.), Academic Press: London, 1972.
D. Goldfarb and S. Liu, “An O(n 3 L) primal interior point algorithm for convex quadratic programming,” Mathematical Programming, vol. 49, pp. 325-340 (1991).
G.H. Golub and C.F. Van Loan, Matrix Computations, 2nd edition, The Johns Hopkins University Press, 1989.
E.V. Haynsworth, “Determination of the inertia of a partitioned Hermitian matrix,” Linear Algebra and its Applications, vol. 1, pp. 73-81 (1968).
D. Hertog, C. Roos, and T. Terlaky, “A polynomial method of weighted centers for convex quadratic programming,” J. Inform. Optim. Sci., vol. 12, pp. 187-205 (1991).
W. Li and J. Swetits, “A new algorithm for solving strictly convex quadratic programs,” SIAM Journal on Optimization, to appear.
K. Madsen, H. Nielsen, and M. Pinar, “A new finite continuation algorithm for bound constrained quadratic programming,” Tech. Report, IMM-REP-1995-22, Institute of Mathematical Modeling, Technical University of Denmark, 1995.
S. Mehrotra and J. Sun, “An algorithm for convex quadratic programming that requires O.n 3:5 L) arithmetic operations,” Math. Oper. Res., vol. 15, pp. 342-363 (1990).
R. Monteiro and I. Adler, “Interior path-following primal-dual algorithms, part II: Convex quadratic programming,” Mathematical Programming, vol. 44, pp. 43-66 (1989).
J.J. Moré and D. Sorensen, “Computing a trust region step,” SIAM Journal on Scientific and Statistical Computing, vol. 4, pp. 553-572 (1983).
J.J. Moré and G. Toraldo, “Algorithms for bound constrained quadratic programming problems,” Numerische Mathematik, vol. 55, pp. 377-400 (1989).
R.T. Rockafellar, Convex Analysis, Princeton University Press, 1970.
D. Sorensen, “Trust region methods for unconstrained optimization,” SIAM Journal on Numerical Analysis, vol. 19, pp. 409-426 (1982).
T. Tsuchiya, “Affine scaling algorithm,” Interior Point Methods of Mathematical Programming, T. Terlaky (Ed.), Kluwer Academic Publishers: Dordrecht, 1996.
D.G. Wilson, “A brief introduction to the IBM optimization subroutine library,” SIAG/OPT Views and News, vol. 1, pp. 9-10 (1992).
P. Wolfe, “The simplex method for quadratic programming,” Econometrica, vol. 27, pp. 382-398 (1959).
Y. Ye, “Interior point algorithms for quadratic programming,” in Recent Developments in Mathematical Programming, S. Kumar (Ed.), Gordon & Beach Scientific Publishers: Philadelphia, 1991.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Coleman, T.F., Liu, J. An Exterior Newton Method for Strictly Convex Quadratic Programming. Computational Optimization and Applications 15, 5–32 (2000). https://doi.org/10.1023/A:1008773230148
Issue Date:
DOI: https://doi.org/10.1023/A:1008773230148