5) В тех случаях, когда заранее известна нижняя грань , в (8) можно принять

- это абсцисса точки пересечения прямой с касательной к кривой в точке .

Допустим, что какой-либо способ выбора в (8) уже выбран. Тогда на практике итерации (8) продолжают до тех пор, пока не выполнится некоторый критерий окончания счета. Здесь часто используются условие (7), а также критерий , где - фиксированная точность вычислений. Иногда заранее задают число итераций; возможны различные сочетания этих и других критериев. Разумеется, к этим критериям окончания счета надо относиться критически, поскольку они могут выполняться и вдали от искомой точки минимума. К сожалению, надежных критериев окончания счета, которые гарантировали бы получение решения задачи минимизации с требуемой точностью, и применимых к широкому классу задач, пока нет. Сделанное замечание о критериях окончания счета относится и к другим излагаемым методам.

В теоретических вопросах, когда исследуется сходимость метода, предполагается, что процесс (8) продолжается неограниченно и приводит к последовательности . Здесь возникают вопросы, будет ли полученная последовательность минимизирующей для задачи минимизации, будет ли она сходиться к множеству точек минимума

,

Или, иначе говоря, выполняются ли соотношения

, ?

Для положительного ответа на эти вопросы на функцию , кроме условия непрерывной дифференцируемости на , приходится накладывать дополнительные более жесткие ограничения.

Блок-схема метода наискорейшего спуска

3.2. Подробнее рассмотрим эти вопросы для методов 2 и 3 (наискорейшего спуска).

Пусть функция ограничена снизу, непрерывно дифференцируема на и ее градиент удовлетворяет условию Липшица:

для всех , ,

где - некоторая фиксированная константа. Кроме того, пусть выбор величины шага производится на основе условия (9) или (10). Тогда, какова бы ни была начальная точка , оба градиентных метода приводят к построению последовательности , обладающей свойством .

Если, кроме того, функция дважды непрерывно дифференцируема и существуют такие числа , что

для всех , , (12)

То для обоих указанных градиентных методов последовательность будет сходиться к точке глобального минимума.

Первая часть утверждения гарантирует сходимость лишь в смысле , т.е. сходимость по функции либо к точной нижней грани , либо к значению функции в некоторой стационарной точке . При этом сама точка не обязательно является точкой локального минимума; она может быть точкой седлового типа. Однако на практике подобная ситуация маловероятна и применение градиентных методов, как правило, позволяет получить приближенное значение минимума целевой функции.

3.3. Рис. 4 а) и б) показывают, а теоретические исследования и численные эксперименты подтверждают, что метод наискорейшего спуска и другие варианты градиентного метода медленно сходятся в тех случаях, когда поверхности уровня функции сильно вытянуты и функция имеет так называемый «овражный» характер. Это означает, что небольшое изменение некоторых переменных приводит к резкому изменению значений функции – эта группа переменных характеризует «склон оврага», а по остальным переменным, задающим направление «дна оврага», функция меняется незначительно (на рис. 4 б) изображены линии уровня «овражной» функции двух переменных). Если точка лежит на «склоне оврага», то направление спуска из этой точки будет почти перпендикулярным к направлению «дна оврага», и в результате приближения , получаемые градиентным методом, будут поочередно находиться то на одном, то на другом «склоне оврага». Если «склоны оврага» достаточно круты то такие скачки «со склона на склон» точек могут сильно замедлить сходимость градиентного метода.

Рис. 4.

Для ускорения сходимости этого метода при поиске минимума «овражной» функции можно предложить следующий эвристический прием, называемый овражным методом. Сначала опишем точки , , из которых производят спуск с помощью какого-либо варианта градиентного метода, и получают две точки , на «дне оврага». Затем полагают