Abstract
For the general quadratic programming problem (including an equivalent form of the linear complementarity problem) a new solution method of branch and bound type is proposed. The branching procedure uses a well-known simplicial subdivision and the bound estimation is performed by solving certain linear programs.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
H.P.Benson, “Concave optimization: Theory, application and algorithms,” in Handbook of Global Optimization, R.Horst and P.M.Pardalos (Eds.), Kluwer Academic Publishers: Dordrecht, 1994.
I.M.Bomze and G.Danninger, “A finite algorithm for solving general quadratic problems,” Journal of Global Optimization, vol. 4, pp. 1–16, 1994.
J.E.Falk and K.Hoffman, “A successive underestimation method for concave minimization problems,” Mathematics of Operations Research, vol. 1, pp. 251–259, 1976.
C.A.Floudas and V.Visweswaran, “Quadratic optimization,” in Handbook of Global Optimization, R.Horst and P.M.Pardalos (Eds.), Kluwer Academic Publishers: Dordrecht, 1994.
R. Horst and N.V. Thoai, “A decomposition approach for the global minimization of biconcave functions over polytopes,” Forschungsbericht Nr. 92-23, University of Trier, Department of Mathematics and Informatics, 1993, forthcoming in Journal of Optimization Theory and Applications, vol. 8, no. 3, 1996.
R.Horst and H.Tuy, Global Optimization: Deterministic Approaches, 2nd revised edition, Springer-Verlag: Berlin, 1993.
R.Horst, P.M.Pardalos, and N.V.Thoai, Introduction to Global Optimization, Kluwer Academic Publishers: Dordrecht, 1995.
L.D.Muu and W.Oettli, “An algorithm for indefinite quadratic programming with convex constraints,” Operations Research Letters, vol. 10, pp. 323–327, 1991.
P.M.Pardalos and J.B.Rosen, Constrained Global Optimization: Algorithms and Applications, Lecture Notes in Computer Science, 268, Springer-Verlag: Berlin, 1987.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Horst, R., Van Thoai, N. A new algorithm for solving the general quadratic programming problem. Comput Optim Applic 5, 39–48 (1996). https://doi.org/10.1007/BF00429750
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00429750