Основы теории оптимизации (стр. 74 )

      (18)

где α>1. Если же новое значение F оказывается большим за предыдущее, то сдвиг считается неудачным и следующий шаг определяется по формуле

      (19)

где β<1 .

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

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

6.9. Методы второго порядка

Ньютоновские методы. Эта группа методов основана на более точной аппроксимации целевой функции в окрестности точки

f( + )=+o(|| ||2).

Минимизируемая функция Ψ( ). Соответствующее направление и шаг берут из условия минимума Ψ ( ):

(1)

• Для квадратичной целевой функции Ψ ( ) метод (1) решает задачу миними­зации за одну (!) итерацию.

• В окрестности невырожденного экстремума имеет квадратичную сходимость (гессиан Gk > 0 и симметричен).

• Ньютоновское направление - это направление наискорейшего спуска в G-энертетической метрике

• Существенным является то, что на каждом шаге необходимо решать систему линейных уравнений (1) для определения нътоновского направления очеред­ной итерации.

• При модификации метода Ньютона, когда гессиан фиксируется на определенное число итераций - в методе Ньютона-Рафсона — существенен алгоритми­ческий выигрыш, но при этом обеспечена лишь линейная сходимостъ метода.

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

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

Такими методами, не требующими решения СЛАУ (1) на каждом итерационном шаге для определения направления спуска, являются методы сопряженных направлений. Для квадратичной функции Ψ( ):

они позволяют не более чем за п шагов спуска получить её минимум. Напомним:

Симметричная положительноопределенная матрица А>0, АТ=А

позволяет ввести "А-энергетическую" норму вектора

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

Определение. Векторы, ортогональные в А-энергетическом смысле, называются сопряженнымы относительно матрицы А.

Сопряженные векторы обладают рядом "хороших" свойств:

1) Если {xi}k — система сопряженных векторов и k ≤ п, то эта сисстема векторов — линейно независима.

Действительно, пусть

- ненулевая комбинация остальных векторов. Тогда

но А > 0 и следовательно нулевой вектор, что невозможно.

2) Если число векторов в рассматриваемой системе k=п, то {xi}k —сопряженный базис. Можно считать его сопряженным ОНБ. т. е. (xi, xj)А = δij. Разложим направление по ОНБ {xi}k и рассмотрим квадратичную функцию на этом направлении

(2)

Движение по каждому из сопряженных направлений xi изменяет

только одно слагаемое в сумме (2) и, тем самым, за не более, чем п

шагов приводит к минимуму функции Ψ.

Существуют различные способы построения сопряженных относительно А направлений, в частности - метод сопряженных градиентов (метод Флетчера-Рнвса)- приводит к одной из наиболее эффективных процедур многомерной численной минимизации.

Рассмотрим снова квадратичную аппроксимацию Ψ(х) целевой фрикции f(х) в окрестности точки :

На каждом цикле итерационных шагов для построения сопряженного базиса будем использовать одну и ту же матрицу Gk ≡ hess f(xk). При этом мы будем считать, что находимся в достаточно малой окрестности точки минимума x*, где G (xk) > 0.

В методе сопряженных градиентов совокупность сопряженных относительно G ≡ G (xk) направлений строится следующим образом. Опишем процедуру постро­ения одного цикла минимизации, содержащего п шагов и точно минимизирующего Ψk ( ).

(3)

Пусть , … , Gk - сопряженная система векторов

Покажем, что (3) определяет систему сопряженных относительно Gk векторов движения { }n.

а) Проверить самостоятельно 2 й шаг;

б) 1: opтoгонально всем предыдущим при j ≤ s, ибо спускаясь на предыдущем, S-ом шаге, мы пришли в точку

вдоль направления .

Но эта точка — — точка "минимума", т. е.

Если проследить "вглубь" траектории, то

Тогда

Добавим слева и справа по ≡ (Mk), и учтем, что Gk ≡G; Gх + b ≡ (х). Таким образом

Тогда

2: Покажем, что вектор ортогонален всем градиентам ,. Имеем

т. о.

3: Рассмотрим очередное направление:

и покажем, что сопряжено всем ,. Оно сопряжено, по крайней мере, со всеми до предыдущего, т. е.

Действительно, поскольку j ≤ S, то

Предыдущее направление:

Метод Флетчера Ривса обладает квадратичной сходимостью, в достаточно малой окрестности точки . Рестарт в точке Мk

осуществляется по антиградиенту ().

Это один из наиболее эффективных методов численной минимизации функций многих пепременных.

7. Методы анализа многомерной безусловной оптимизации

7.1. Анализ методов прямого поиска

Методы разделяются на методы прямого поиска и градиентные. Методы прямого поиска используют только значение функции, разделяются на эвристические и теоретические. Теоретические методы инвариантны.

Среди эвристических методов: поиск по симплексу и его модификация – метод Нелдера-Мида, а также метод Хука-Дживса.

Среди теоретических: метод сопряжённых направлений Пауэлла (основан на фундаментальном свойстве параллельного подпространства).

Градиентные методы:

·  с использованием первой и второй производной;

·  сопряжённых градиентов;

·  квазиньютоновские методы.