Методы оптимизации. Рейзлин В.И. - 15 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

Составители: 

Рубрика: 

очередность изменения координат
n
xxx ,...,,
21
, совпадающая с очередностью их
индексов 1, 2, …, n. Сначала изменяем одну координату
1
x , сохраняя все
остальные координаты постоянными, на некоторую величину
x
и определяем
величину приращения
f
. Если
0
f
, то, следовательно, шаг сделан в ложном
направлении. Изменяем направление и движемся до тех пор, пока
0
f
не
изменит знак на противоположный. Тогда переходим к изменению другой
координаты
2
x и т.д. до тех пор, пока не будет найдена с некоторой заданной
точностью точка минимума. При реализации метода возможны другие
вычислительные схемы.
Метод отличается простотой реализации. Однако по сравнению с другими
методами требует большего времени на поиск минимума функции.
1.2. Метод Ньютона
Рассмотренные выше методы основаны на последовательной линейной
аппроксимации целевой функции и требуют вычисления значений целевой
функции и ее производных на каждом шаге, число которых может быть очень
велико /1, 3/. Для построения более общей стратегии необходимо привлечь
информацию о вторых производных
)
(
x
f
. Эта информация может быть получена
при квадратичной аппроксимации функции, когда при ее разложении в ряд
Тейлора учитываются члены ряда до второго порядка включительно.
Использование результатов аппроксимации приводит к реализации метода
Ньютона по формуле
)()(
)(1)(2)()1( kkkk
xfxfxx
, (4)
где )(
2
xf - гессиан (матрица Гессе).
Метод Ньютона обнаруживает квадратичную скорость сходимости, т. е.
выполняется неравенство
2
)()1( kk
c
,
где c – некоторая постоянная, связанная с обусловленностью матрицы Гессе.
*)()(
xx
kk
,
где
*
x
- искомое решение.
Сходимость метода Ньютона во многом зависит от выбора начального
приближения
)0(
x
. Метод сходится всякий раз, когда выбор
)0(
x
осуществляется в
соответствии с условием /1/
c1
)0(
.

Страницы