2.4. Направление убывания и методы спуска

Многие методы мини­мизации относятся к числу методов спуска. В методах спуска на­правление движения к минимуму на каждом шаге выбирается из числа направлений убывания минимизируемой функции.

Говорят, что вектор h задает направление убывания функции f в точке x, если f(x + h) < f(x) при всех достаточно малых  > 0. Сам вектор h также называют иногда направлением убывания. Мно­жество всех направлений убывания функции f в точке х будем обо­значать через U(х, f).

Таким образом, если любой достаточно малый сдвиг из х в на­правлении вектора h приводит к уменьшению значения функции f, то h  U(x, f).

Заменив неравенство, фигурирующее в определении направления убывания, на противоположное, получим определение направления возрастания.

В дальнейшем нам понадобятся следующие достаточный и необ­ходимый признаки направления убывания.

Лемма 2.1. Пусть функция f дифференцируема в точке х  Rⁿ. Если вектор h удовлетворяет условию

f'(х),h < 0, (2.13)

то h U(х, f). Если h U(х, f), то

f'(х),h  0, (2.14)

Геометрически условие (2.13) означает, что вектор h составляет тупой угол с градиентом f'(х).

Метод (2.3) называется методом спуска, если вектор h^k задает направление убывания функции f в точке x^k:

h^k U(х^k, f), k = 0, 1, 2, ...,

а число _k положительно и таково, что

f(x^k+1) < f(x^k), k = 0, 1, 2, ...

Простейшим примером метода спуска является градиентный метод, в котором h^k = –f'(х^k) (если f'(х)  0, то –f'(х)  U(х, f) в силу леммы 2.1).

2.5. Выбор длины шага из условия минимизации функции вдоль заданного направления

Коэффициенты _k в методе (2.3) можно оп­ределять из условия

, (2.15)

где для методов спуска, т. е. при h^k U(х^k, f), минимум берется по   0. Такой способ выбора _k является в некотором смысле наилучшим, ибо он обеспечивает достижение наименьшего значения функции вдоль заданного направления. Однако он требует решения на каждом шаге одномерной задачи минимизации. Эти задачи ре­шаются, как правило, приближенно с помощью численных методов, что приводит к значительному объему вычис­лений.

В простейших случаях величины _k, удается найти в явном виде.

Адаптивный способ отыскания коэффициентов _k, не требую­щий дополнительных вычислений характеристик целевой функции

Ранее рассмотрен способ выбора коэф­фициентов _k, требующий решения вспомогательных одномерных задач. В процессе их решения приходится, как правило, произво­дить дополнительные вычисления характеристик целевой функции f в точках, отличных от x⁰, х¹, ..., x^k.

Ниже приводятся явные формулы для _k. В них используются лишь значения f'(x^k) и некоторые константы, характеризующие глобальные свойства функции f. Эти формулы выбраны с целью обеспечить при соответствующих предположениях о f выполнение неравенства

, (2.17)

где   (0, 1), направление h^k таково, что f'(x^k), h^k < 0 и, стало быть, h^k U(х^k, f). Неравенство (2.17) необходимо для обоснования сходимости многих методов минимизации. Из него, в частности, сле­дует, что f(x^k+1) < f(х^k), и соответствующий метод минимизации является, таким образом, методом спуска.

Лемма 2.2. Пусть функция f дифференцируема на Rⁿ, а ее градиент удовлетворяет условию Липшица

||f'(x) – f'(x')||  M||x – x'||, x, x' Rⁿ, (2.18)

где М > 0.

Тогда для произвольных x^k Rⁿ,   (0, 1) и x^k, удовлетворяю­щего неравенству f'(x^k), h^k < 0, условие (2.17) выполнено при

. (2.19)