The Method of Steepest Descent for Non-Linear Minimization Problems
Abstract¶
The problem considered here is that of minimizing a function of n real variables, G(x_1, ..., x_n). The object is to find a practical method for evaluating, approximately at least, a stationary point for G. This problem includes as a special case that of solving a set of simultaneous equations f_i(x_1, ..., x_n) = 0 (i = 1, 2, ..., m), because the function G(x_1, ..., x_n) = sum_{k=1}^m f_k^2 has a minimum at a solution of (1). It also includes that of determining the parameters x_1, ..., x_n of a function f(u; x_1, ..., x_n) so as to get the best approximation, in a least square sense, to a function F(u) for certain values of u; the G in this case is of the form given by G(x_1, ..., x_n) = sum_{k=1}^p [F(u_k) - f(u_k; x_1, ..., x_n)]^2. Certain engineering applications of the latter sort of problem arose in the work of the Engineering Research Section, Fire Control Design Division, at Frankford Arsenal. In these applications, the function f(u; x_1, ..., x_n) was sufficiently complicated so that the standard method for dealing with non linear least square problems failed to converge. Two techniques for dealing with this situation were developed by the section under the direction of J. G. Tappert. One of these was an original suggestion of my associate K. Levenberg. The second method is the subject of this note. This method is not new. Levenberg found it set forth in a paper by Cauchy dated 1847. That it has become a standard procedure in analysis is clear from a recent paper by Courant. Nevertheless it does not appear to be well known to authorities on numerical computation. It was used for the case of linear equations by G. Temple; but he gave no reference to Cauchy's work nor indeed to any previous use of the method. Accordingly there is room for an exposition of the method with emphasis on its practical aspects. This note also contains an outline of a convergence proof. Cauchy stated that the process converged but gave no proof, at least in the paper cited. Temple's convergence proof applied only to the linear case. Courant gives references to papers dealing with the method; but some of these were not accessible to me under wartime conditions. The convergence proof, as outlined here, is an elementary one and gives a weak result.
Summary¶
Curry gives a practical numerical-computation exposition of Cauchy's method of steepest descent for minimizing nonlinear functions, motivated especially by nonlinear least-squares problems where more standard methods failed in Frankford Arsenal fire-control applications. The note describes the basic iteration of moving along the negative gradient and choosing a step by a one-dimensional search, explains the geometric right-angle behavior of successive exact line-search directions, and sketches conditions under which limit points of the resulting broken-line path are stationary points. Its comparison with Levenberg's contemporaneous method is useful historically: steepest descent avoids second derivatives and normal-equation solves, but the paper already recognizes its sensitivity to scaling and its uncertain practical advantage over more problem-specific least-squares methods.