The Simplex and the Dual Method for Quadratic Programming

Abstract

The paper presents a straightforward generalization of the Simplex and the dual method for linear programming to the case of convex quadratic programming. The two algorithms, called the Simplex and the dual method for quadratic programming, are applicable when the matrix of the quadratic part of the objective function, in case this function is to be maximized, is negative definite, negative semi-definite or zero; in the last case the two methods are equivalent to an application of the similar methods for linear programming. The paper gives an exposition of the methods as well as examples and interpretations. The relations with linear programming methods are considered and some starting procedures in case no initial feasible solution is available are presented.

¹International Centre for Management Science, Rotterdam

^†Now at the University of Birmingham.

^‡Now at the University of Virginia.

¹International Centre for Management Science, Rotterdam

^†Now at the University of Birmingham.

^‡Now at the University of Virginia.