3.4 Метод сопряженных направлений (метод Пауэлла)

В методе сопряженных направлений (методе Пауэлла [Powell M.J.D.]) ис­пользуется факт, что минимум квадратичной функции может быть найден не бо­лее чем за шагов при условии, что поиск ведется вдоль сопряженных относи­тельно матрицы Гессе направлений. Так как достаточно большой класс целевых функций может быть представлен в окрестности точки минимума своей квадра­тичной аппроксимацией, описанная идея применяется и для неквадратичных функций. Задается начальная точка и направления , совпадающие с координатными. Находится минимум при последовательном движении по направлениям с помощью одного из методов одномерной минимизации. При этом полученная ранее точка минимума берется в качестве исходной для поиска по следующему направлению, а направление использу­ется как при первом , так и последнем поиске. Находится новое на­правление поиска, сопряженное с . Оно проходит через точки, полученные при первом и последнем поиске. Заменяется на , на и т.д. Направление заменяется сопряженным направлением, после чего повторяется поиск по направлениям, уже не содержащим старого направления . Для квадратичных функций последовательность одномерных поисков приводит к точке минимума (если все операции выполнены точно). Построение сопряженного направления для квадратичной функции при изображено на рисунке 3.8. Оно проходит через точки 1 и 3.

Рисунок 3.8

Алгоритм:

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

Положим .

Шаг 2. Найти , где шаг находится в результате поиска минимума

функции по одним из методов одномерной минимизации.

Шаг 3. Проверить условия:

1. Если , то положить и перейти к шагу 2;

2. Если , проверить успешность поиска по последним направлениям. Если , то поиск завершить: , иначе положить и перейти к шагу 2;

3. Если , проверить успешность поиска по первым направлениям. Если , то поиск завершить: , иначе перейти к шагу 4 для построения сопряженного направления.

Шаг 4. Положить и проверить условие окончания:

1. если , то поиск завершить: ;

2. иначе положить (новое направление); (исключается старое направление). Если при этом , то новая система направлений линейно независима. В этом случае положить: , , , и перейти к шагу 2.

Если при этом , то новая система направлений линейно зависима. Тогда следует продолжать поиск в старых направлениях. Для этого положить: , , , и перейти к шагу 2.

Пример: Методом сопряженных направлений найти локальный минимум функции

Решение:

1. Зададим начальную точку , ,

2⁰. Получаем . Найдем минимум функции по . Применим метод квадратичной интерполяции, т.к. минимизируемая функция квадратичная. Получим .

3⁰. Имеем i = 0 < n – 1 = 1, поэтому i = i + 1 = 1 и переходим к шагу 2.

2¹. Получаем . Найдем минимум функции по . Применим метод квадратичной интерполяции, т.к. минимизируемая функция квадратичная. Получим .

3¹. Имеем , поэтому i = i + 1 = 2 и переходим к шагу 2.

2². Получаем . Найдем минимум функции . Получим .

3². Имеем . Переходим к шагу 4.

4⁰. Находим Т.к. положим . Т.к. , то новая система линейно независима. Положим

и перейдем к шагу 2.

2³. Получаем . Найдем минимум функции по . Получим .

3³. Имеем i = 0 < n – 1 = 1, поэтому i = i + 1 = 1 и переходим к шагу 2.

2⁴. Получаем . Найдем минимум функции по . Получим .

3⁴. Имеем , поэтому i = i + 1 = 2 и переходим к шагу 2.

2⁵. Получаем . Найдем минимум функции . Получим .

3². T.к. , то процесс поиска минимума завершается: .