Переход из точки  в точку  на -м шаге алгоритма Пауэлла осуществляется в соответствии с формулой: .

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

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

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

Доказательство. Используя ранее полученные результаты (10), можно записать, что в первом случае ,

аналогично, во втором случае можно записать

.

Вычитая из первого выражения второе получим, что

.

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

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

Следующий рисунок служит иллюстрацией теоремы.

 

Пусть в начальный момент для двумерной задачи поиск осуществляется из точки  вдоль направлений, параллельных осям координат:  и . Последовательно были найдены точки  (см. рис. 6).

 

Рис. 6.

Таким образом, определили 2 сопряженных направления, в которых следует вести поиск:  и . В системе исходных направлений  должно быть заменено на , представляющее собой полное перемещение из первого минимума. Направления поиска на следующем этапе: , .

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

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

1. Начиная с точки , решается последовательность задач минимизации функции , , в направлениях . При этом находятся точки , которые минимизируют исходную функцию в заданных направлениях, причем ,   ,  …,  .

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

На примере квадратичной функции Пауэллом было показано, что при нормировании направлений поиска в соответствии с соотношением:

, ,

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

Для такой проверки из точки  делается дополнительный шаг в направлении , соответствующий полному перемещению на -м этапе и получают точку . Для проверки того, что определитель матрицы направлений поиска увеличивается при включении нового направления, делается шаг 3.

3. Обозначим наибольшее уменьшение  на -м шаге

,

соответствующее направление поиска обозначим через .

Обозначим: , , ,

Где , .

Тогда, если  и (или) , то следует использовать на -м этапе те же направления , что и на -м этапе, то есть , , и начать поиск из точки  или из точки , в зависимости от того, в какой точке функция принимает минимальное значение.

4. Если тест на шаге 3 не прошел, то ищется минимум  в направлении вектора , проведенного из  в : . Точка этого минимума берется в качестве начальной точки на -м этапе. А в системе сопряженных направлений сохраняются все, кроме направления , которое заменяется на новое направление , но новое направление помещается в последний столбец матрицы направлений. На -м этапе будут использоваться направления .

5. Критерий останова. Алгоритм прерывается, если изменение по каждой переменной оказывается меньше заданной точности по соответствующей переменной или .