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

Основные формулы, составляющие алгоритм МСГ при минимизации квадратичной формы -переменных имеет вид:

 

; (1)

, (2)

. (3)

Коэффициент определяется из условия сопряженности: (4)

(5)

, . (6)

Для нахождения необходимо решить известную одномерную задачу минимизации:

. (7)

Представленные формулы (1), (2), (3), (6), (7) составляют алгоритм МСГ Ф-Р, позволяющий не более, чем за шагов минимизировать квадратичную форму -переменных. Как видно, это конечный алгоритм, однако, при его реализации необходимо использовать известное неравенство:

, . (8)

Если минимизируемая функция является квадратичной функцией, то МСГ Ф-Р будет не конечным, а итеративным. Здесь применение известного неравенства совершенно необходимо, причем -номер итерации, состоящей из не более, чем шагов. Причем, для выражения , будут несколько иными:

, . (9)

Все остальные формулы МСГ совпадают с формулами этого метода при минимизации квадратичной формы.

Существенно отметить еще раз, что МСГ будучи методом многомерной безусловной оптимизации 1-го порядка для функций трижды дифференцированных и сильно выпуклых об-

 

ЛК №3

17.09.2003

 

см. [3] стр. 63

 

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

 

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

Итерационная формула методов имеет вид:

, (1)

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

Таким образом, Квазиньютоновские методы становятся методами многомерной безусловной оптимизации 1-го порядка.

Существует рекуррентная формула, позволяющая по исходным данным определить матрицу , найти матрицу

Параметр находится как правило, способом, аналогичным способом, применяемому во 2-м обобщенном МН.

,

Данный метод является методом 1-го порядка, а скорость сходимости сверхлинейная.

 

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

Как известно, эти методы (методы 1-го порядка) при минимизации функции, используют информацию только о значениях самой функции (рассматривается как производная нулевого порядка).

К числу методов нулевого порядка относятся:

1) метод сканирования;

2) метод покоординатного спуска;

3) метод деформируемого многогранника.

 

Метод сканирования.

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

 

См. [3] стр. 64

 

 

[3] – ознакомиться с методом самостоятельно. Стр. 64

 

.

Методы 0-го порядка, в т.ч. метод сканирования, позволяют численно решать экстремальные задачи для функций , которые являются непрерывными и дифференцируемыми, а также позволяют находить все множество точек минимума и максимума , т.е. находить не только локальные, но и глобальные экстремумы (методы 1-го и 2-го порядка применимы для минимизации только непрерывной дифференцируемой функции и позволяют находить только локальные экстремумы).

Основной недостаток метода сканирования (и других методов 0-го порядка): малая сходимость, и как следствие, значительные временные затраты.

Как правило, множество точек в методе сканирования задается в некотором гиперпараллелепипеде: с использованием " сеточного" разбиения".

 

Метод покоординатного спуска.

Этот метод сходит с ранее изученным методом градиентного покоординатного спуска, однако при нахождении шага минимизации вдоль каждого " направления" решается одномерная оптимизационная задача с использованием известных методов: МД, МЗС или МФ. Последнее использует также информацию только о значениях самой функции.

Естественно, что итерационный процесс следует приводить к условию:

,

 

⇐ Предыдущая45678910111213Следующая ⇒

Поделиться: