Minimizing Complementary Pivots in a Simplex-Based Solution Method for a Quadratic Programming Problem


The paper presents an approach for avoiding and minimizing the complementary pivots in a simplex based solution method for a quadratic programming problem. The linearization of the problem is slightly changed so that the simplex or interior point methods can solve with full speed. This is a big advantage as a complementary pivot algorithm will take roughly eight times as longer time to solve a quadratic program than the full speed simplex-method solving a linear problem of the same size. The strategy of the approach is in the assumption that the solution of the quadratic programming problem is near the feasible point closest to the stationary point assuming no constraints.

Share and Cite:

E. Munapo, "Minimizing Complementary Pivots in a Simplex-Based Solution Method for a Quadratic Programming Problem," American Journal of Operations Research, Vol. 2 No. 3, 2012, pp. 308-312. doi: 10.4236/ajor.2012.23037.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] S. Burer and D. Vandenbussche, “A Finite Branch-and- Bound Algorithm for Nonconvex Quadratic Programs with Semidefinite Relaxations,” Mathematical Programming, Series A, Vol. 113, No. 2, 2008, pp. 259-282. doi:10.1007/s10107-006-0080-6
[2] S. Burer and D. Vandenbussche, “Globally Solving Box- Constrained Nonconvex Quadratic Programs with Semi- definite-Based Finite Branch-and-Bound,” Computational Optimization and Applications, Vol. 43, No. 2, 2009, pp. 181-195.
[3] R. M. Freund, “Solution Methods for Quadratic Optimization: Lecture notes,” Massachussets Institute of Technology, 2002.
[4] S. T. Liu and R.-T. Wang, “A Numerical Solution Methods to Interval Quadratic Programming,” Applied Mathematics and Computation, Vol. 189, No. 2, 2007, pp. 1274-1281. doi:10.1016/j.amc.2006.12.007
[5] B. A. McCarl, H. Moskowitz and H. Furtan, “Quadratic Programming Applications,” Omega, Vol. 5, No. 1, 1977, pp. 43-55. doi:10.1016/0305-0483(77)90020-2
[6] J. J. Moré and G. Toraldo, “Algorithms for Bound Constrained Quadratic Programming Problems,” Numerische Mathematik, Vol. 55, No. 4, 1989, pp. 377-400. doi:10.1007/BF01396045
[7] G. B. Dantzig, “Linear Programming and Extensions,” Princeton University Press, Princeton, 1998.
[8] X.-W. Liu and Y.-X. Yuan, “A Null-Space Primal-Dual Interior-Point Algorithm for Nonlinear Optimization with Nice Convergence Properties,” Mathematical Programming, Vol. 125, No. 1, 2010, pp. 163-193. doi:10.1007/s10107-009-0272-y
[9] S. Carvalho and A. Oliveira, “Interior-Point Methods Applied to the Predispatch Problem of a Hydroelectric System with Scheduled Line Manipulations,” American Journal of Operations Research, Vol. 2, No. 2, 2012, pp. 266-271. doi:10.4236/ajor.2012.22032
[10] W.-Y. Sun and Y.-X. Yuan, “Optimization Theory and Methods: Nonlinear Programming,” Springer, New York, 2006.
[11] O.K. Gupta, “Applications of Quadratic Programming,” Journal of Information and Optimization Sciences, Vol. 16, No. 1, 1995, pp. 177-194.
[12] R. Horst, P. M. Pardalos and N. V. Thoai, “Introduction to Global Optimization: Nonconvex Optimization and its Applications,” 2nd Edition, Kluwer Academic Publishers, Dordrecht, 2000.
[13] H. A. Taha, “Operations Research: An Introduction,” 9th Edition, Pearson, 2011.
[14] W. L. Winston, “Operations Research: Applications and Algorithms,” 4th Edition, Thomson Brooks/Cole, Belmont, 2004.

Copyright © 2021 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.