24. Метод Пауэлла

Один из первых методов сопряжённых направлений представлен английским математиком М. Д. Д. Пауэллом в 1964 году для минимизации функции нескольких переменных , . Этот метод является развитием метода циклического покоординатного спуска, в котором последовательный одномерный поиск производится в направлениях ортов координатных осей , , …, . В отличие от метода покоординатного спуска в методе Пауэлла строится система сопряженных направлений.

Каждая итерация метода Пауэлла начинается с определения линейно независимых направлений , , …, . Первоначально эти направления совпадают с ортами координатных осей: , .

Из начальной точки производится вспомогательный одномерный поиск в последнем направлении :

, . (3.16)

Затем из точки выполняется итерация метода покоординатного поиска в виде проведения последовательных одномерных поисков в направлениях ортов координатных осей:

, , . (3.17)

Последняя точка получена при минимизации функции из точки в направлении . Таким образом, точки и найдены путем минимизации функции в одном и том же направлении . В случае квадратичной целевой функции по свойству параллельного подпространства направление сопряжено к направлению . Из системы направлений , , …, исключается первое направление и добавляется новое направление . При этом полагают для и . Для квадратичной функции после окончания первой итерации два последние направления поиска и сопряжены.

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

Таким образом, для квадратичной функции после итераций метода Пауэлла последние направления поиска , …, , выбранных для -й итерации, будут взаимно сопряженными. После итераций все направления будут взаимно сопряженными, поэтому метод Пауэлла обеспечивает минимизацию квадратичной функции не более чем за итераций. Так, для минимизации квадратичной функции с двумя переменными и достаточно выполнения двух итераций. При этом точка минимума будет найдена после выполнения четырех одномерных поисков.

Алгоритм метода Пауэлла.

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

Выходной параметр – конечная точка поиска.

1. Положить , .

2. Вычислить .

3. Положить , , .

4. Вычислить .

5. Положить .

6. Если , то положить и перейти к шагу 4.

7. Положить .

8. Положить .

9. Если , то положить и перейти к шагу 8.

10. Вычислить .

11. Если , то перейти к шагу 2.

12. Остановиться.

В этом алгоритме на шаге 1 формируется матрица направлений поиска как единичная матрица размера . Шаги 2–11 составляют итерацию метода Пауэлла. На шаге 2 выполняется одномерный поиск из точки в направлении последнего столбца матрицы . На шагах 4–6 производится последовательный одномерный поиск в направлениях всех столбцов матрицы . На шагах 7–10 формируется новая матрица направлений исключением первого ее столбца и добавлением последнего столбца. На шаге 11 проверяется критерий окончания вычислений.

Пример 3.1. На рис. 3.3 представлена траектория поиска минимума квадратичной функции (1.3) методом Пауэлла, включающая все точки поиска. Лучшие точки итераций соединены жирной линией. Для вычисления точки минимума с допустимой погрешностью 10–3 метод затратил 3 итерации, причем значение функции 9,2∙10–33 было найдено за две итерации при погрешности вычисления точки минимума 1,2∙10–16, а последняя итерация использована для проверки критерия окончания вычислений. Значения целевой функции были вычислены 35 раз. Сравнивая эти результаты с результатами примера 1.5 для минимизации той же функции методом циклического покоординатного спуска, можно убедиться в преимуществе метода Пауэлла.

Пример 3.2. На рис. 3.4 представлена траектория минимизации функции Розенброка методом Пауэлла, включающая лучшие точки итераций. Для нахождения точки минимума с допустимой погрешностью 10–3 метод затратил 12 итераций и 529 вычислений функции.

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

Рис. 3.3. Минимизация квадратичной функции методом Пауэлла

< Предыдущая		Следующая >