Research ArticleOpen AccessGoogle Scholar indexed
A New Heuristic for the Convex Quadratic Programming Problem
Graduate School of Business and Leadership, University of KwaZulu-Natal, Westville Campus, Durban, South Africa
Department of Mathematics and Statistics, University of Melbourne, Parkville, Australia
- 1 Graduate School of Business and Leadership, University of KwaZulu-Natal, Westville Campus, Durban, South Africa
- 2 Department of Mathematics and Statistics, University of Melbourne, Parkville, Australia
American Journal of Operations Research·Volume 05 (2015)·Pages 373–383·Published 24 July 2015·DOI10.4236/ajor.2015.55031
Copy link · social · email
Abstract
This paper presents a new heuristic to linearise the convex quadratic programming problem. The usual Karush-Kuhn-Tucker conditions are used but in this case a linear objective function is also formulated from the set of linear equations and complementarity slackness conditions. An unboundedness challenge arises in the proposed formulation and this challenge is alleviated by construction of an additional constraint. The formulated linear programming problem can be solved efficiently by the available simplex or interior point algorithms. There is no restricted base entry in this new formulation. Some computational experiments were carried out and results are provided.
KeywordsConvex Quadratic ProgrammingLinear ProgrammingKarush-Kuhn-Tucker ConditionsSimplex MethodInterior Point Method
- Gupta, O.K. (1995) Applications of Quadratic Programming. Journal of Information and Optimization Sciences, 16, 177-194. http://dx.doi.org/10.1080/02522667.1995.10699213
- Horst, R., Pardalos, P.M. and Thoai, N.V. (2000) Introduction to Global Optimization: Non-Convex Optimization and Its Applications. Kluwer Academic Publishers, Dordrecht. http://dx.doi.org/10.1007/978-1-4615-0015-5
- McCarl, B.A., Moskowitz, H. and Furtan, H. (1977) Quadratic Programming Applications. Omega, 5, 43-55. http://dx.doi.org/10.1016/0305-0483(77)90020-2
- Burer, S.D. and Vandenbussche, D. (2008) A Finite Branch and Bound Algorithm for Non-Convex Quadratic Programs with Semidefinite Relaxations. Mathematical Programming Series A, 113, 259-282. http://dx.doi.org/10.1007/s10107-006-0080-6
- Burer, S.D. and Vandenbussche, D. (2009) Globally Solving Box-Constrained Non Convex Quadratic Programs with Semidefinite-Based Finite Branch-and-Bound. Computational Optimisation and Applications, 43, 181-195.
- Freund, R.M. (2002) Solution Methods for Quadratic Optimization. Lecture Notes, Massachusetts Institute of Technology, Cambridge, MA.
- Gondzio, J. (2012) Interior Point Methods 25 Years Later. European Journal of Operational Research, 218, 587-601. http://dx.doi.org/10.1016/j.ejor.2011.09.017
- More, J.J. and Toraldo, G. (1989) Algorithms for Bound Constrained Quadratic Programming Problems. Numerische Mathematik, 55, 377-400. http://dx.doi.org/10.1007/BF01396045
- Liu, S.T. and Wang, R.T. (2007) A Numerical Solution Method to Interval Quadratic Programming. Applied Mathematics and Computations, 189, 1274-1281. http://dx.doi.org/10.1016/j.amc.2006.12.007
- Maes, C. and Saunders, M. (2012) A Regularized Active-Set Method for Sparse Convex Quadratic Programming. 21st International Symposium on Mathematical Programming, Berlin, 19-24 August 2012.
- Jensen, P.A. and Bard, J.F. (2012) Operations Research Models and Methods. John Wiley & Sons Inc., Hoboken.
- Lee, C.R. (2011) Unit 8: Quadratic Programming Active set Method and Sequential Quadratic Programming. http://www.cs.nthu.edu.tw/~cherung/teaching/2011cs5321/handout8.pdf
- Winston, W.L. (2004) Operations Research Applications and Algorithms. 4th Edition, Duxbury Press, Pacific Grove, CA.
- Maros, I. and Meszaros, C. (1999) A Repository of Convex Quadratic Programming Problems. Optimization Methods and Software, 11-12, 671-681.