Безусловная минимизация функций численными методами второго порядка.

 

Методы безусловной оптимизации второго порядка используют некоторые частные производные минимизируемой функции clip_image002. Суть этих методов состоит в следующем [3,11]:

Необходимым условием экстремума функции многих переменных в точке clip_image004, является равенство нулю ее градиента в этой точке. Разложение clip_image006 в окрестности точки clip_image008в ряд Тейлора позволяет представить уравнение в таком виде:

clip_image010 (57)

здесь clip_image012 - матрица вторых производных (матрица Гессе) минимизируемой функции. Следовательно, итерационный процесс построения последовательных приближений описывается выражением:

clip_image014, где (58)

clip_image016 - обратная матрица для матрицы Гессе, а clip_image018 - направление спуска.

Полученный метод минимизации называют методом Ньютона. Очевидно, что в данном методе величина шага вдоль направления спуска полагается равной единице. Последовательность точек, получаемая в результате применения формулы (58) при определенных предположениях сходится к некоторой стационарной точке clip_image004[1]функции clip_image002[1]. Если матрица Гессе clip_image020положительно определена, точка clip_image004[2]будет точкой локального минимума функции clip_image002[2]. Последовательность clip_image022 сходится к точке clip_image004[3]только в том случае, когда матрица Гессе целевой функции положительно определена на каждой итерации.

Если функция clip_image002[3] является квадратичной, то независимо от начального приближения и степени овражности, метод ньютона находит ее минимум за один шаг. Это объясняется тем, что направление спуска clip_image024 в любых точках всегда совпадает с направлением в точку минимума clip_image004[4]. Если же функция не квадратичная, но выпуклая, то метод Ньютона гарантирует ее монотонное убывание от итерации к итерации. При минимизации овражных функций скорость сходимости метода Ньютона более высока по сравнению с градиентными методами.

Существенным недостатком метода в данной форме является зависимость сходимости для невыпуклых функций от начального приближения clip_image026. Если clip_image026[1]находится достаточно далеко от точки минимума, то метод может расходиться, т.е. при проведении итераций каждая следующая точка будет еще более отдаленной от точки минимума, чем предыдущая. Сходимость метода независимо от начального приближения обеспечивается выбором не только направления спуска, но и величины шага вдоль этого направления. Соответствующий алгоритм называется методом Ньютона с регулировкой шага или методом ньютона – Рафсона. Итерационный процесс в таком случае определяется выражением:

clip_image028 (59)

величина шага выбирается из условий минимума функции clip_image002[4] по clip_image030в направлении движения:

clip_image032 (60)

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

Алгоритм метода Ньютона – Рафсона состоит в следующем:

1. В точке clip_image026[2]вычисляется clip_image034;

2. На k- том шаге в соответствии с выражениями (59) и (60) определяются шаг clip_image036и точка clip_image038;

3. Вычисляется величина clip_image040;

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

clip_image042 и осуществляется переход к п.2.

Количество вычислений на одной итерации методом Ньютона – Рафсона, как правило, значительно больше, чем в градиентных методах. Это объясняется необходимостью вычисления и обращения матрицы вторых производных целевой функции. Однако число итераций, требуемых для нахождения оптимума, в методе Ньютона – Рафсона значительно меньше по сравнению с градиентными методами.

В ряде случаев целесообразно комбинированное использование градиентных методов и метода Ньютона – Рафсона. В начале процесса минимизации, когда точка clip_image026[3] находится далеко от точки экстремума, можно применять какой-либо вариант градиентных методов. Далее. При уменьшении скорости сходимости градиентного метода можно перейти к методу Ньютона – Рафсона.

Метод сопряженных градиентов Флетчера-Ривса.

Этот метод относится к группе методов сопряженных направлений, при которых шаги итерационной процедуры минимизации целевой функции предпринимаются в сопряженных направлениях. Два n-мерных вектора x и y называют сопряженными по отношению к матрице H (или H-сопряженными), если скалярное произведение (x,Hy)=0. Здесь H – симметричная положительно определенная матрица размером n x n [11].

Методы сопряженных направлений обладают по сравнению с градиентными методами более высокой скоростью сходимости. Минимум положительно определенной квадратичной функции n переменных

clip_image002 (49)

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

Наиболее существенна при методах сопряженных направлений проблема эффективного построения таких направлений. Метод Флетчера - Ривса решает эту проблему путем преобразования на каждом шаге антиградиента - clip_image004 в направлении clip_image006, H – сопряженном с ранее найденными направлениями clip_image008. Рассмотрим сначала этот метод применительно к задаче минимизации квадратичной функции (49).

Направление clip_image006[1] вычисляются по формулам:

clip_image010, clip_image012

clip_image014 (50)

Величины clip_image016 выбираются так, чтобы направления clip_image018 были H-сопряженными: clip_image020 (51)

В результате для квадратичной функции:

clip_image022 (52)

Итерационный процесс минимизации имеет вид

clip_image024 clip_image026 clip_image028, где (53)

clip_image030 - называют величиной шага, а n-мерный вектор clip_image032 - направлением спуска на k-том шаге. Величина шага выбирается из условий минимума функции в направлении движения:

clip_image034 (54)

Для квадратичной функции clip_image036 (55)

Алгоритм сопряженных градиентов состоит в следующем:

1. В точке clip_image038 вычисляется clip_image040;

2. На k-ом шаге по формулам (55) и (53) определяется шаг clip_image030[1]и точка clip_image042;

3. Вычисляются величины clip_image044 и clip_image046;

4. Если clip_image048, то точка clip_image042[1]является минимумом функции. В противном случае из соотношения:

clip_image050 (56)

определяется новое направление clip_image052 и осуществляется переход к следующей итерации. Благодаря этой процедуре минимум квадратичной функции находится не более чем за n шагов. При минимизации не квадратичных функций метод Флетчера -Ривса из конечного становится итеративным. В таком случае после clip_image054 итерации шаги 1 – 4 алгоритма повторяются с заменой clip_image038[1] на clip_image057, а вычисления заканчиваются при clip_image059, где clip_image061 - заданная точность.

Пример 9. Найти минимум функции clip_image063. Начальная точка (9; -7; 11) [2] .

Решение: Итерационный процесс приведен в таблице 4.

Таблица 4.

итерации

x1

x2

x3

F

1

9

-7

11

418

2

-0,481

0,111

7,83

37,14

3

1,206

2,827

4,862

4,965

4

0,999

2

3

4,26E-14

Оптимальное значение найдено на 4 шаге.

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