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

Условия остановки (критерии окончания счета)

Сходимость методов оптимизации

Важной характеристикой бесконечношаговых методов является сходимость.

Будем говорить, что метод (2.3) сходится, если х^k® х* при k ® ¥,где х* – решение задачи (2.1). Если f(х^k) ® f(х*), то иногда также говорят, что метод (2.3) сходится (по функции), при этом последо­вательность х^k называют минимизирующей. Минимизирующая после­довательность может и не сходиться к точке минимума. Так, для функции, график которой изображен на рис. 2.1, минимизирующая последовательность x^k = k не сходится к точке минимума х* = 0.

В случае, когда точка минимума х* не единственна, под сходи­мостью метода понимается сходимость последовательности х* к мно­жеству X* точек минимума функции f.

Эффективность сходящегося метода можно охарактеризовать с помощью понятия скорости сходимости.

Пусть х^k® х* при k ® ¥. Говорят, что последовательность х^k сходится к х* линейно (с линейной скоростью, со скоростью геоме­трической прогрессии), если существуют такие константы q Î (0, 1) и k⁰, что

при k ³ k⁰. (2.4)

Говорят, что х^k сходится к х* сверхлинейно (со сверхлинейной ско­ростью), если

при k ® ¥. (2.5)

Наконец, говорят о квадратичной сходимости, если существуют такие константы С ³ 0 и k⁰, что

при k ³ k⁰. (2.6)

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

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

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

Условие оста­новки может определяться имеющимися в наличии вычислительными ресурсами. Например, может быть задано число вычислений преду­смотренных алгоритмом характеристик минимизируемой функции f.

На практике часто используются следующие условия остановки:

, (2.7)

, (2.8)

, (2.9)

До начала вычислений выбирается одно из условий (2.7)-(2.9) и соответствующее ему малое положительное число e_i. Вычисления прекращаются после (k+1)-го шага, если впервые оказывается вы­полненным выбранное условие остановки. На практике также исполь­зуются критерии, состоящие в одновременном выполнении двух из условий (2.7)-(2.9) или всех трех условий.

Критерий (2.9) относится лишь к задачам безусловной оптимизации. Его выполнение означает, что в точке х^k+1 с точностью e₃ выполнено условие стационарности. В задаче условной оптимизации критерий (2.9) следует заменить на критерий «e-стационарности», соответствующий данной задаче.

Вместо критериев (2.7)-(2.9), основанных на понятии абсо­лютной погрешности, можно использовать аналогичные критерии, основанные на понятии относительной погрешности:

, (2.10)

, (2.11)

, (2.12)

Отметим, что выполнение указанных критериев и других подоб­ных им эвристических условий остановки, вообще говоря, не гаран­тирует достижения необходимой точности решения задачи.

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

Говорят, что вектор h задает направление убывания функции f в точке x, если f(x + ah) < f(x) при всех достаточно малых a > 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, ...,

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

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

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