12 Численные методы безусловной минимизации

Будем рассматривать задачу f(x) ! min (x 2 X, X тождественно равно En) (0)

Для поиска экстремума можно не использовать необходимые условия. Экстремумы можно находить по-иному. Если найти способ пошагового определения точек x1; x2; . . . ; xn в которых значения целевой ф-и f(x) образуют убывающую сходящуюся последовательность, то можно надеятся, что тем самым удасться найти минимум ф-и, не прибегая к необходимым условиям. Такие способы называют прямыми методами решения задач оптимизации. Последовательности точек x0; x1; x2; :::; xn, удовлетворяющих условию

f(x0) > f(x1) > . . . > f(xn) (1)

называют релаксационными, а методы их построения принято называть методами спуска. Различные методы спуска отличаются друг от друга способами выбора направления спуска и длины шага вдоль этого направления. В этих методах точки последовательности x0; x1; x2; :::; xn вычисляются по формуле

xk+1 = xk + kpk (2)

pk некоторая линия спуска, k длина шага вдоль этого направления.

13 Общая схема градиентого спуска

Известно, что градиент скалярной ф-и f(x) в некоторой точке xk направлен в сторону наискорейшего возрастания ф-и и ортогонален линии уровня (поверхности постоянного значения) ф-и f(x), проходящей через точку xk. Вектор, противоположный градиенту и называемый антиградиентом направлен в сторону наискорейшего убывания ф-и f(x). Выбирая в кач-ве направления спуска pk в формуле (2) антиградиент ф-и f(x) в точке xk приходим к итерационному процессу вида

xk+1 = xk kf0(xk) (3)

k > 0 k = 1; 2; ::: - шаг. В координатной форме этот процесс записывается следующим образом

Все итерационные процессы, в которых направление движения на каждом шаге совпадает с антиградиентом (градиентом) называются градиентыми методами. Градиентые методы отличаются друг от друга способом выбора шага k.

13.1Градиентые методы с дроблением шага

Достаточно малый шаг обеспечивает убывание ф-и

f(xk kf0(xk)) < f(xk) (5)

но может привести к неприемлимо большому кол-ву итераций, необходимых для достижения точки минимума. С другой стороны, большой шаг может привести к невыполнению условия (5).

В методе градиентого спуска с дроблением шага величина k выбирается так, чтобы было выполнено следующее неравенство:

f(xk kf0(xk)) f(xk) 6 " kjjf0(xk)jj2 (6)

" - произвольно выбранная постоянная, одна и таже для всех итераций.

Процесс (3) с выбором шага, удовлетворяющему неравенству (6) протекает следующим образом: Выбираем > 0, одно и тоже для всех итераций на k-той итерации проверяем выполнение неравенства

(6) при k = , если оно выполнено, то и далее полагаем k = , и переходим к следующей итерации. Если условие (6) не выполняется, то шаг k дробим до тех пор пока не выполнится неравенство (6) (шаг делят пополам). На практике итерации (3) продолжают до тех пор, пока не выполнится некоторый критерий окончания счета, при этом часто используют следующие критерии

22