Метод Пауэлла относится к прямым методам (методам нулевого порядка). Этим методом наиболее эффективно осуществляется минимизация функций, близких к квадратичным. На каждой итерации алгоритма поиск осуществляется вдоль системы сопряженных направлений.
Два направления поиска называются сопряженными, если , ,
, ,
где - положительно определенная квадратная матрица.
Обоснование применения сопряженных направлений в алгоритмах оптимизации. В методе Пауэлла - матрица вторых частных производных. Идеи метода Пауэлла относятся к квадратичной функции .
Основная идея заключается в том, что если на каждом этапе поиска определяется минимум квадратичной функции вдоль каждого из - сопряженных направлений и если затем в каждом из направлений делается шаг до минимальной точки, то полное перемещение от начала до шага с номером сопряжено ко всем поднаправлениям поиска.
Идея использования сопряженных направлений лежит в основе ряда алгоритмов.
Пусть - квадратичная функция и процесс минимизации начинается в точке с начальным направлением . Для удобства возьмем этот вектор единичным, т.е. . Тогда вектор и длина шага определяется из условия минимальности функции в данном направлении т.е.
.
Для квадратичной функции
, (1)
и, таким образом, оптимальное значение на первом шаге определяется в соответствии с соотношением
, (2)
где .
Из точки процесс минимизации должен осуществляться в другом сопряженном направлении и при этом
.
Отметим, что квадратичная функция может быть представлена в виде
,
где положительно определенная матрица .
В общем случае система линейно независимых направлений поиска называется сопряженной по отношению к некоторой положительно определенной матрице , если
, .
Так как сопряженные направления линейно независимы, то любой вектор в пространстве можно выразить через следующим образом:
где . (3)
Известная формула, примем ее на веру.
Для некоторой матрицы всегда существует, по крайней мере, одна система из взаимно сопряженных направлений, так как сами собственные векторы матрицы представляют собой такую систему.
Отметим, что для квадратичной функции справедливо следующее соотношение, которое потребуется в дальнейшем:
. (4)
Чтобы убедиться в его справедливости, рассмотрим матрицу . Умножение ее справа на дает
,
если положить .
Вообще говоря, справедливо общее правило, заключающееся в том, что если используются сопряженные направления для поиска минимума квадратичной функции , то эта функция может быть минимизирована за шагов по одному в каждом из сопряженных направлений. Более того, порядок использования сопряженных направлений несущественен.