Материал: Бородакий Нелинейное программирование в современных задачах оптимизации 2011

Векторы yi вычисляются по рекуррентным формулам:

y1 = q1 ,

…

Блок-схема алгоритма может быть представлена в виде, изображенном на рис. 1.17. На рисунке использованы следующие обозначения:

k – номер цикла;

= – номер итерации при движениях по ˆi ; i 1, n S

j – счетчик неудачных шагов; x0 – это x в начале цикла;

x– текущий аргумент.

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

(метод Пауэлла)

Два вектора x и y называются Q-сопряженными (или

взаимно ортогональными, если x т y = 0 , таким образом, понятие сопряженности является обобщением понятия ортогональности).

47

Направления S1 , S2 , …, Sn являются сопряженными относительно матрицы Q, если

SiтQS j = 0 при i ≠ j , i, j =1, n .

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

Это самая общая идея метода. Существуют несколько способов построения системы сопряженных направлений и, соответственно, несколько различных вариантов метода сопряженных направлений. Метод Пауэлла – один из таких вариантов, относящийся к методам нулевого порядка, т.е. методам, не требующим вычисления производных.

На чем основана идея сопряженных направлений и в чем преимущество поиска вдоль таких направлений? Дело в том, что если имеем квадратичную целевую функцию

f (x) = a + x тb + 12 x тQx ,

где x – n-мерный вектор, Q – матрица Гессе (Q – положительно определенная матрица), то минимум такой функции может быть найден ровно за n шагов от любой начальной точки, если поиск вести вдоль системы из n Q-сопряженных направлений.

На рис. 1.18 приведен пример формирования Q-сопряженных направлений для случая квадратичной целевой функции f (x) .

Может возникнуть вопрос: зачем понадобилось тратить усилия на минимизацию квадратичной функции, если она минимизируется

аналитически и дает результат x* = −Q−1b ?

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

испытывают на квадратичной функции.

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

48

f (x) = b +Qx .

Поскольку xi – это точки минимума на направлении S, градиент функции в этих точках ортогонален к S, т.е.

S т f (x1 ) = 0 = S т (b + Qx1 ), S т f (x 2 ) = 0 = S т (b + Qx 2 ).

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

0 = S тQ(x1 − x 2 ) ,

т.е. S и (x1 − x 2 ) – Q-сопряженные направления.

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

1. Выбрать в качестве начальных направлений S10 , S20 ,…, Sn0 , совпадающие с координатными осями (k = 0). Выбрать начальную точку поиска x0k .

2. Определить с помощью одномерного поиска

вдоль нового полученного направления) и взять в качестве начальной точки для следующей итерации

x0k +1 = xnk + λ* S k ,

положив k = k +1 , и перейти к п. 2.

Блок-схема алгоритма метода Пауэлла приведена на рис. 1.20.

50