Descent, method of
A method for solving the minimization problem
![]() |
where is some function of the variables
. The iterative sequence
of the method of descent is computed by the formula
![]() |
where is a vector indicating some direction of decrease of
at
, and
is an iterative parameter, the value of which indicates the step-length in the direction
. If
is a differentiable function and
is not an extremal point of it, then the vector
must satisfy the inequality
![]() | (*) |
where is the gradient of
at
.
If is a sufficiently smooth function (e.g. twice continuously differentiable) and if the sequence
satisfies inequality (*), then there exists a sequence
such that
![]() |
Under certain restrictions (see [3]) on the function and on the method of choosing the parameters
and the vectors
, the sequence
converges to a solution
of the initial problem.
The gradient method, in which the vectors are in some way expressed in terms of the vectors
, is a method of descent. One of the most common cases is when
![]() |
where is a symmetric matrix satisfying
![]() |
for any two vectors and
, with certain constants
. Under additional restrictions (see [3]) on
and by a special selection of
, the gradient method ensures the convergence of
to a solution
of the initial problem with the rate of an arithmetical progression with ratio
. A special case of the gradient method is the method of steepest descent (cf. Steepest descent, method of), in which the matrix
is the unit matrix.
References
[1] | L.V. Kantorovich, G.P. Akilov, "Functionalanalysis in normierten Räumen" , Akademie Verlag (1964) (Translated from Russian) |
[2] | G. Zoutendijk, "Methods of feasible directions" , Elsevier (1970) |
[3] | B.N. Pshenichnyi, Yu.M. Danilin, "Numerical methods in extremal problems" , MIR (1978) (Translated from Russian) |
[4] | B.T. Polyak, "Gradient methods for the minimization of functionals" USSR Comp. Math. Math. Physics , 3 : 4 (1963) pp. 864–878 Zh. Vychisl. Mat. i Mat. Fiz. , 3 : 4 (1963) pp. 643–654 |
Comments
See also Coordinate-wise descent method.
References
[a1] | J.M. Ortega, W.C. Rheinboldt, "Iterative solution of non-linear equations in several variables" , Acad. Press (1970) |
Descent, method of. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Descent,_method_of&oldid=11500