New Methods in Mathematical Programming—Some Simplex-Like Nonlinear Programming Procedures

This paper surveys certain recent procedures for the computational solution of convex nonlinear programming problems, related to one another through being based on the simplex method of linear programming. The first procedure, the simplex method for quadratic programming, is a terminating algorithm for the extremization of a quadratic function under linear constraints. The next two procedures employ efficient techniques for the development of a grid on which nonlinear objectives and constraints can be represented by linear functions, the separable programming method is applicable to problems involving separable functions, and the decomposition method to those in which a simpler subproblem can readily be solved. Finally, the cutting-plane method employs an efficient sequential means of approximating to the nonlinear functions involved through first-order Taylor's series approximations.