[home] [lexicon] [problems] [tests] [courses] [auxiliaries] [notes] [staff]

Mathematics-Online lexicon:

# Steepest Descent

 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z overview

The method of steepest descent is used to minimize multivariate functions . In one step of the iteration, first, the negative gradient

is computed, which is the best local search direction. Then, the next approximation is determined by minimizing in the direction :

As shown in the figure, the search direction is orthogonal to the level set through and touches the level set for a smaller function value in .

The convergence of the sequence , generated by the the method of steepest descent, can be shown under fairly general assumptions. It is sufficient that is bounded from below and is Lipschitz continuous in a neighborhood of the set , i.e.,

These hypotheses imply that

In particular, tends to zero, and it follows that each accumulation point of the sequence is a critical point of . While, statistically, convergence to a local minimum is almost certain, exceptional cases cannot be excluded.

To ensure convergence of the algorithm, it is not necessary to find the exact one-dimensional minimium in the direction of . It is sufficient to use a non-optimal decent direction and obtain merely a reduction of the current function value which is proportional to .