3. Метод сопряженных направлений Пауэлла

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

Определение. Пусть - симметрическая матрица порядка. Векторыназываются- сопряженными, если они линейно независимы и выполняется условиепри.

Пример. Рассмотрим функцию

.

В качестве матрицы можно взять матрицу Гессе

.

В качестве одного из направлений выберем . Тогда направлениедолжно удовлетворять равенству

.

Следует заметить, что сопряженные направления выбираются неоднозначно. Однако если добавить условие нормировки, то их можно определить однозначно:

.

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

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

Утверждение. Пусть задана квадратичная функция , две произвольные точкии направлениеS..Если точка является точкой минимума функциивдоль направленияS из точки , а- точкой минимума функции вдоль направленияS из точки , то направлениесопряжено с направлениемS.

Алгоритм.

Шаг 1. Задать начальную точку и систему линейно независимых направлений (они первоначально могут совпадать с направлениями координатных осей). Минимизировать функцию при последовательном движении по направлениям; используя какой-либо одномерный поиск; и полученную ранее точку минимума взять в качестве исходной.

Шаг 2. Выполнить дополнительный шаг , соответствующий полному перемещению на шаге 1. Вычислить точку(рис 12). Проверить критерий (*) включения нового направления в систему сопряженных направлений.

Шаг 3. Пусть – наибольшее уменьшение целевой функции в одном из направлений:

и является направлением, соответствующим.

Если выполняются условия

(*)

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

Рис. 12

Шаг 4. Если условия не выполняются, то минимизировать функциювдоль направления. Точку этого минимума взять в качестве начальной на следующем этапе. На этом этапе использовать систему направлений

: ,

т.е. направление заменить на, которое поместить в последний столбец матрицы направлений.

Шаг 5. Если , то минимум найден. В противном случае выполнить шаг 1.

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

Минимизация функции

методом сопряженных направлений

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

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

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