Градиентные методы поиска минимума.

Метод наискорейшего спуска. Данный метод дает возможность на каждом шаге поиска минимума двигаться вдоль «наилучшего» направления. Известно, что направление градиента является направлением наискорейшего возрастания функции. Следовательно, противоположное направление является направлением наискорейшего убывания функции. Это свойство может быть обосновано следующим образом. Предположим, что осуществляется перемещение из точки в следующую точку , где – некоторое направление, а – шаг некоторой длины. Следовательно, перемещение производится из точки в точку , где

а – косинусы направления такие, что

Изменение значений функции определяется соотношениями

(5)

с точностью до первого порядка , причем частные производные вычисляются в точке .

Выражение (5) запишем в виде

, (6)

где ,

Как видим, формула (6) определяет направление наибольшего возрастания функции . Поэтому направлением наискорейшего спуска является направление .

Если мы находимся на текущем шаге в точке , то следующей точкой, аппроксимирующей минимум , будет точка , которая оценивается по формуле

(7)

или, в скалярной форме

В формуле (7) – значение шага, определяющего скорость движения по направлению к минимуму. Оптимальное значение шага можно найти, минимизировав функцию

Причем оптимальное значение можно найти, используя любой метод минимизации функции одного переменного.

Оканчивать вычислительный процесс можно, сравнивая по норме в каком либо пространстве две соседние точки итерационного процесса (7), т.е.

или определяя норму градиента

Эти формулы можно переписать в виде

где , –заданные положительные значения точности вычислений. Недостаток метода – низкая скорость сходимости, прежде всего в малой окрестности точки минимума.

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

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

(8)

Это свойство можно использовать для поиска минимума.

Метод поиска минимума на основе квадратичной аппроксимации. Квадратичная функция

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

откуда .

Согласно (6.9), функция аппроксимируется квадратичной функцией .

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

откуда

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

, (9)

или, с регулируемой скоростью движения к минимуму

. (10)

Здесь – длина шага, определяемая при минимизации функции

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

Давидон, Флетчер и Пауэлл предложили метод, который позволяет избежать вычисления обратной матрицы Гессе. В основе лежат формулы (9), (10).

Метод Давидона – Флетчера – Пауэлла.Суть метода Давидона – Флетчера – Пауэлла (ДФП) состоит в том, что направление поиска на -м шаге задается не вектором-направлением , а направлением , где – симметричная матрица, которая обновляется на каждом шаге и в пределе становится равной обратному гессиану. То есть реализуется следующий алгоритм

. (11)

Рассмотрим алгоритм метода ДФП.

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

1. На шаге имеется точка и положительно определенная симметрическая матрица .

2. В качестве направления поиска выбираем направление .

3. Находим значение (см. формулу (10), минимизирующее функцию , используя методы минимизации функции одной переменной.

4. Находим приращение (приближение) к точке экстремума

5. Определяем следующую аппроксимацию точки экстремума, то есть реализуем итерационный процесс

6. Вычисляем и . Проверяем выпонение условия или . Замечание: в полагаемой точке экстремума .

7. Полагаем

. (12)

8. Вычисляем матрицу для следующей итерации

, (13)

где

, (14)

. (15)

9. Вновь выполняем итерационный процесс, вернувшись на шаг 2.

Ранее отмечалось, что в процессе итераций на определенном шаге матрица станет близкой или равной обратному гессиану, то есть . Если это произойдет за шагов, то поиск минимума функции также будет завершен за шагов. Для доказательства этого факта достаточно показать, что , , …, – линейно независимые векторы матрицы с собственными значениями, равными единице, то есть

. (16)

Заметим, что из выражения (12) следует

Из соотношений (13) – (15) с учетом того, что и можно сократить, следует

Из последнего соотношения и следует (16).

Таким образом, векторы , , …, являются линейно независимыми. Они являются собственными векторами матрицы с собственными значениями, равными единице. Таким образом,

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

На рис. 9. приведена укрупненная структурная схема алгоритма метода ДФП.

Рис. 9. Укрупненная структурная схема алгоритма минимизации функции n переменных методом ДФП

Отметим, что очень близким по концепции является метод Флетчера – Ривса. В основе лежит итерационная процедура, определенная формулой (9).

123

Не нашли, что искали? Воспользуйтесь поиском по сайту: