Algebraic Algorithm for Positive-Definite Quadratic Programming Models (QPM) with Linear and Quadratic Constraints

Authors

  • Roberto Padua Liceo de Cagayan University
  • Noel Lacpao Bukidnon State University
  • Elmer Castillano Mindanao University of Science and Technology
  • Quilano Lasco Jose Rizal Memorial State University

Keywords:

simplex, quadratic, quadratic programming, quadrex, NP-hard AMS-2020134

Abstract

The paper develops a quadrex algorithm for quadratic programming problems (n=2) under linear and quadratic constraints. The quadrex algorithm centers on the behavior of the quadratic function at the origin and performs a series of translations and orthogonal rotations to obtain the extremum of the objective function. The method works for n > 2 provided that the eigenvalues of the quadratic form part of the objective function is strictly positive or that Q is strictly positive-definite. The quadrex algorithm is the quadratic counterpart of the simplex algorithm for linear programming models (LP).

References

Nocedal, Jorge; Wright, Stephen J. (2006). Numerical Optimization (2nd ed.). Berlin, New York: Springer-Verlag. p. 449.

Murty, K. G. (1988). Linear complementarity, linear and nonlinear programming. Sigma Series in Applied Mathematics. 3. Berlin: Heldermann Verlag. pp. xlviii+629

F. Delbos, J.Ch. Gilbert (2005). Global linear convergence of an augmented Lagrangian algorithm for solving convex quadratic optimization problems. Journal of Convex Analysis, 12, 45-69.

Murty, K. G. (1988). Linear complementarity, linear and nonlinear programming. Sigma Series in Applied Mathematics. 3. Berlin: Heldermann Verlag. pp. xlviii+629 pp.. ISBN 3-88538-403-5. (Available for download at the website of Professor Katta

G. Murty.) MR949214

Nocedal, Jorge (2000), On the Solution of Equality Constrained Quadratic Programming Problems Arising in Optimization, SIAM Journal of Scientific Computing

Kozlov, M. K.; S. P. Tarasov and Leonid G. Khachiyan (1979). "[Polynomial solvability of convex quadratic programming]". Doklady Akademii Nauk SSSR 248: 1049 1051. Translated in: Soviet Mathematics - Doklady 20: 1108–1111.

Sahni, S. "Computationally related problems," in SIAM Journal on Computing, 3, 262-279, 1974.

Panos M. Pardalos and Stephen A. Vavasis(1991). Quadratic programming with one negative eigenvalue is NP-hard, Journal of Global Optimization, Volume 1, Number 1, pp.15-22.

Cottle, Richard W.; Pang, Jong-Shi; Stone, Richard E. (1992). The linear complementarity problem. Computer Science and Scientific Computing. Boston, MA: Academic Press, Inc.. pp. xxiv+762 .

Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. pp.245.

Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. (2006). Numerical optimization: Theoretical and practical aspects. Universitext (Second revised ed. of translation of 1997 French ed.). Berlin: Springer-Verlag. pp. xiv+490

Downloads

Published

2013-12-01

Issue

Vol. 8 No. 1 (2013): The Threshold

Section

Articles

License

Copyright (c) 2013 The Treshhold

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.