Quadratic programming as an extension of linear programming

In the past two decades Mathematical Programming has come to occupy a place of importance in Economic Studies and in Operations Research. Roughly speaking, Mathematical Programming is the analysis of problems of the type: "Find the maximum of a function, when the variables are subject to inequality and equality constraints". The term "Linear Programming" corresponds to the case where, the function to be maximized (the so called objective function) and the equality and inequality constraints are linear. The term "Non-Linear Programming" should then become self-defined. With the introduction of Dantzig's Simplex Method, Linear Programming has become an everyday technique. The same, we regret to say, is not true for Nonlinear Programming because this subject is broader and much more difficult to unify than that of Linear Programming. In fact at present there does exist any unifying theory for Nonlinear Programming. However, we feel that research on this field is gathering tremendous momentum and that in the not too distant future Nonlinear Programming will become both a practical and fundamental tool in many spheres of Science. One of the subject matters of Nonlinear Programming is what we came to call "Quadratic Programming". This name is restricted to the specific problem of maximizing or minimizing a quadratic objective function f(X) = CX + X'DX, where CX is a linear form and X'DX a quadratic form, subject to linear constraints. Historically, Quadratic Programming was the first venture into the theory of Nonlinear Programming. More specifically it is the purpose of this thesis to: (i) Present a unified and simple treatment of the Theory of Concave (Convex) Quadratic Programming (in no way will mathematical rigour be sacrificed for simplicity). (ii) Present a collection of "Simplicial Methods" for solving quadratic programming problems, which are but extensions of the Simplex Method ( for Linear Programming, whose "accuracy" and "convergence" make them completely self-sufficient for the solution of any type of concave (convex) quadratic programming problems.

Grantor dc:publisher.institution

Department of Statistical Sciences

Year dc:date.issued

1968

Author dc:creator

• Teixeira, Rui L

Advisor dc:contributor.advisor

• Troskie, Casper G

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/11427/12597

OAI identifier oai:identifier

oai:open.uct.ac.za:11427/12597