The Gradient Projection Method for Nonlinear Programming. Part I. Linear Constraints

TLDR

The paper discusses nonlinear programming, contrasting linear and nonlinear objective functions, and notes that the gradient projection method can solve linear problems as a special case, building on foundational work by Dantzig and Kuhn–Tucker. It aims to present the gradient projection method for problems with linear constraints, setting the stage for its extension to nonlinear constraints in Part II. Part I demonstrates that the gradient projection method efficiently solves the less difficult linear‑constraint case, and subsequent work has produced computational procedures building on this result.

Abstract

more constraints or equations, with either a linear or nonlinear objective function. This distinction is made primarily on the basis of the difficulty of solving these two types of nonlinear problems. The first type is the less difficult of the two, and in this, Part I of the paper, it is shown how it is solved by the gradient projection method. It should be noted that since a linear objective function is a special case of a nonlinear objective function, the gradient projection method will also solve a linear programming problem. In Part II of the paper [16], the extension of the gradient projection method to the more difficult problem of nonlinear constraints and equations will be described. The basic paper on linear programming is the paper by Dantzig [5] in which the simplex method for solving the linear programming problem is presented. The nonlinear programming problem is formulated and a necessary and sufficient condition for a constrained maximum is given in terms of an equivalent saddle value problem in the paper by Kuhn and Tucker [10]. Further developments motivated by this paper, including a computational procedure, have been published recently [1]. The gradient projection method was originally presented to the American Mathematical Society