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

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

Будем говорить, что метод (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)

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

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

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

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

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

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

, (2.7)

, (2.8)

, (2.9)

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

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

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

, (2.10)

, (2.11)

, (2.12)

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