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

• Решение онлайн
• Видеоинструкция
• Оформление Word

Метод Пауэлла относится к прямым методам (методам нулевого порядка). Этим методом наиболее эффективно осуществляется минимизация функций, близких к квадратичным. На каждой итерации алгоритма поиск осуществляется вдоль системы сопряженных направлений.
Два направления поиска S_i, S_j называются сопряженными, если S_j^T·H·S_j=0, i≠j, S_i^T·H·S_i=0, i=j.
где H - положительно определенная квадратная матрица.
Обоснование применения сопряженных направлений в алгоритмах оптимизации. В методе Пауэлла H=▽²f(x^k) - матрица вторых частных производных. Идеи метода Пауэлла относятся к квадратичной функции f(x).
Основная идея заключается в том, что если на каждом этапе поиска определяется минимум квадратичной функции f(x) вдоль каждого из p (p < n) - сопряженных направлений и если затем в каждом из направлений делается шаг до минимальной точки, то полное перемещение от начала до шага с номером p сопряжено ко всем поднаправлениям поиска.
Идея использования сопряженных направлений лежит в основе ряда алгоритмов.
Пусть f(x) - квадратичная функция и процесс минимизации начинается в точке x⁰ с начальным направлением S¹. Для удобства возьмем этот вектор единичным, т.е. (S¹)^T·S¹=1. Тогда вектор x¹=x⁰+λ¹·S¹ и длина шага λ¹ определяется из условия минимальности функции в данном направлении т.е.
.
Для квадратичной функции
, (1)
и, таким образом, оптимальное значение λ на первом шаге определяется в соответствии с соотношением
, (2)
где H=▽²f(x^k).
Из точки x¹ процесс минимизации должен осуществляться в другом сопряженном направлении S² и при этом
(S²)^T·H·S¹=0.
Квадратичная функция может быть представлена в виде
,
где положительно определенная матрица H=▽²f(x).
В общем случае система n линейно независимых направлений поиска S¹, S²,..., Sⁿ называется сопряженной по отношению к некоторой положительно определенной матрице H, если (Sⁱ)^T·H·S^j=0, 0 ≤ i ≠ j ≤ n.
Так как сопряженные направления линейно независимы, то любой вектор в пространстве Eⁿ можно выразить через S¹, S²,..., Sⁿ следующим образом:
где . (3)
Для некоторой матрицы H всегда существует, по крайней мере, одна система из n взаимно сопряженных направлений, так как сами собственные векторы матрицы H представляют собой такую систему.
Отметим, что для квадратичной функции справедливо следующее соотношение, которое потребуется в дальнейшем:
. (4)
Чтобы убедиться в его справедливости, рассмотрим матрицу . Умножение ее справа на H·S^k дает
,
если положить .
Вообще говоря, справедливо общее правило, заключающееся в том, что если используются сопряженные направления для поиска минимума квадратичной функции f(x), то эта функция может быть минимизирована за n шагов по одному в каждом из сопряженных направлений. Более того, порядок использования сопряженных направлений несущественен.
Покажем, что это действительно так. Пусть f(x) - квадратичная функция и , при этом ▽f(x)=b+H·x.
В точке минимума ▽f(x*), и эта точка x*=-H^T·b.
Заметим, что ▽^Tf(x^k)·S^k=(S^k)^T·▽f(x^k).
Так как x¹=x⁰+λ¹·S¹, (5)
где λ¹ определяется в соответствии с соотношением (2):
,
затем минимум находится в следующем сопряженном направлении по аналогичным формулам x²=x¹+λ²·S² и т.д., то на n-м шаге имеем
. (6)
На каждом шаге минимизируем функцию f(x^i-1+λⁱ·Sⁱ) в направлении Sⁱ, чтобы получить λⁱ, что приводит к следующему выражению (на основании (2))
. (7)
Кроме того,
и (Sⁱ)^T·▽f(x^i-1)=(Sⁱ)^T·[H·x⁰+b],
так как все (Sⁱ)^T·H·S^k=0, ∀i≠k, Sⁱ и S^k – сопряжены.
Таким образом,
. (8)
Выразим векторы x⁰ и H^-1·b через систему сопряженных векторов Sⁱ следующим образом (по аналогии с (3)):
,
.
Подставив эти выражения в (7), получим
xⁿ=x⁰-x⁰+H^-1·b=H^-1·b. (9)
Таким образом, точка xⁿ, полученная в результате минимизации квад­ратичной функции на n-м шаге, совпадает с точкой минимума квадратичной функции f(x).
Покажем, что для сопряженных направлений, если f(x) каждый раз минимизируется в сопряженном направлении S^j в соответствии с формулой (2), то при этом выполняется следующее равенство:
(x^j)^T·▽f(x^l), 1 ≤ j ≤ l-1,
при использовании не более чем n направлений, то есть ▽f(x^l) ортогонален использованным сопряженным направлениям.
Для квадратичной функции ▽f(x^l)=b+H·x^l. Следовательно,
,
где x^k - произвольная точка, из которой начинается поиск по сопряженным направлениям. Поскольку ▽f(x^k)=b+H·x^k,
то .
Умножение этого уравнения слева на (S^k-1)^T дает
.
Первый член в правой части (S^k-1)^T·▽f(x^k)=0, так как градиент в точке x^k ортогонален направлению предыдущего спуска, если точка получена в результате минимизации функции в этом направлении. Кроме того, все остальные слагаемые под знаком суммы исчезают вследствие сопряженности направлений S^k-1 и S^j, и таким образом
(S^j)^T·▽f(x^l)=0, 1≤j≤l-1. (10)

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

Теорема: Если при начальной точке x⁰ поиска в направлении вектора S минимум функции f(x) находится к точке x^a, а при начальной точке x¹≠x⁰ поиск минимума функции f(x) в том же направлении S приводит к точке x^b, то при f(x^b)<f(x^a) направление x^b-x^a сопряжено с направлением поиска S.

Доказательство. Используя ранее полученные результаты (10), можно записать, что в первом случае
S^T·▽f(x^a)=S^T·(H·x^a+b)=0,
аналогично, во втором случае можно записать
S^T·▽f(x^b)=S^T·(H·x^b+b)=0,
Вычитая из первого выражения второе получим, что
S^T·H·(x^b-x^a)=0,
Следовательно, векторы S и (x^b-x^a) являются сопряженными.
Эта теорема непосредственно может быть распространена на случай нескольких сопряженных направлений следующим образом. Если, начиная из точки x⁰, точка x^a определяется после использования при минимизации нескольких сопряженных направлений p (p<n). И, аналогично, если из точки x¹≠x⁰ точка x^b определяется после использования тех же направлений и функция f(x) минимизируется на каждом шаге, то вектор (x^b-x^a) сопряжен ко всем p направлениям.
Следующий рисунок служит иллюстрацией теоремы.


Рисунок.
Пусть в начальный момент для двумерной задачи поиск осуществляется из точки x⁰ вдоль направлений, параллельных осям координат: S⁰₁ и S⁰₂. Последовательно были найдены точки x⁰₁, x⁰₂, x⁰₃ (см. рис.).
Таким образом, определили 2 сопряженных направления, в которых следует вести поиск: S⁰₂ и (x⁰₃-x⁰₁). В системе исходных направлений S⁰₁ должно быть заменено на (x⁰₃-x⁰₁), представляющее собой полное перемещение из первого минимума. Направления поиска на следующем этапе:
S¹₁=S⁰₂,
S¹₂=x⁰₃-x⁰₁.

Второй этап начинается с минимизации вдоль направления S¹₂, затем, если необходимо, перемещение в направлении S¹₁. Но в случае квадратичной функции двух переменных после минимизации по двум сопряженным направлениям будет достигнута точка минимума.
В общем случае, на k-м шаге алгоритма Пауэлла используется n линейно независимых направлений поиска. Поиск начинается с точки x^k₀ и осуществляется по следующему алгоритму:
1. Начиная с точки x^k₀, решается последовательность задач минимизации функции , j=1,n, в направлениях S^k₁, ... , S^k_n. При этом находятся точки x^k₁, ... , x^k_n, которые минимизируют исходную функцию в заданных направлениях, причем x^k₁=x^k₀+λ₁·S^k₁ = x^k₁+λ₂·S^k₂, ..., x^k_n=x^k_n-1+λ_n·S^k_n.
2. Поиск, осуществляемый на первом этапе, может привести к линейно зависимым направлениям, если, например, в одном из направлений Sⁱ не удается найти меньшего значения функции. Поэтому 2 направления могут стать коллинеарными. Поэтому в системе сопряженных направлений не следует заменять старое направление на новое, если после такой замены направления нового набора становятся линейно зависимыми.
На примере квадратичной функции Пауэллом было показано, что при нормировании направлений поиска в соответствии с соотношением:
(S^k_i)·H·S^k_i=1, i=1,n,
определитель матрицы, столбцы которой представляют собой направления поиска, принимает максимальное значение тогда и только тогда, когда S^k_i взаимно сопряжены относительно матрицы H. Он пришел к выводу, что направление полного перемещения на k-м шаге должно заменять предыдущее направление только в том случае, когда заменяющий вектор увеличивает определитель матрицы направлений поиска. Так как только тогда новый набор направлений будет более эффективным.
Для такой проверки из точки x^k_n делается дополнительный шаг в направлении (x^k_n-x^k₀), соответствующий полному перемещению на k-м этапе и получают точку (2x^k_n-x^k₀). Для проверки того, что определитель матрицы направлений поиска увеличивается при включении нового направления, делается шаг 3.
3. Обозначим наибольшее уменьшение f(x) на k-м шаге
,
соответствующее направление поиска обозначим через S^k_m.
Обозначим:
f₁=f(x^k₀), f₂=f(x^k_n), f₃=f(2x^k_n-f₁=f(x^k₀),
где x^k₀=x^k-1_n, .
Тогда, если f₃≥f₁ и (или) (f₁-2f₂+f₃)(f₁-f₂-Δ^k)²≥0.5*Δ^k(f₁-f₃)², то следует использовать на (k+1)-м этапе те же направления S^k₁, ... , S^k_n, что и на k-м этапе, то есть S^k+1_i=S^k_i, i=1,n, и начать поиск из точки x^k+1₀=x^k_n или из точки x^k+1₀=2x^k_n-x^k₀=x^k_n+1, в зависимости от того, в какой точке функция принимает минимальное значение.
4. Если тест на шаге 3 не прошел, то ищется минимум f(x) в направлении вектора S^k_n+1, проведенного из x^k₀ в x^k_n: S^k_n+1=(x^k_n-x^k₀). Точка этого минимума берется в качестве начальной точки на (k+1)-м этапе. А в системе сопряженных направлений сохраняются все, кроме направления S^k_m, которое заменяется на новое направление S^k_n+1, но новое направление помещается в последний столбец матрицы направлений. На (k+1)-м этапе будут использоваться направления
[S^k+1₁, S^k+1₂, ..., S^k+1_n] = [S^k₁, S^k₂, ..., S^k_{m-1, S^km+1}, ... , S^k_n, S^k_n+1].
5. Критерий останова. Алгоритм прерывается, если изменение по каждой переменной оказывается меньше заданной точности по соответствующей переменной или ||x^k_n-x^k₀||≤ε.

Пример №1. Методом Пауэлла найти точку минимума функции 4(x₁-5)²+(x₂-6)², если задана начальная точка х⁽⁰⁾ = (8, 9)^Т.
Решение:
Градиент функции:

Итерация №0.

Проверим критерий остановки: |▽f(X₀)| < ε

Вычислим значение функции в начальной точке f(X₀) = 45.
Направление поиска:
p¹ = [1;0]^T
p² = [0;1]^T

Шаг №1. Сделаем шаг вдоль направления поиска p² = [0;1]^T

f(X₁) = 4(8-5)²+((h+9)-6)² → min
f(X₁) = h²+6h+45 → min
Найдем такой шаг h, чтобы целевая функция достигала минимума вдоль этого направления. Из необходимого условия существования экстремума функции (f'(x₁)=0):
2h+6 = 0. Получим шаг: h = -3
Выполнение этого шага приведет в точку:

Шаг №2. Сделаем шаг вдоль другого направления поиска p¹ = [1;0]^T

f(X₂) = 4((h+8)-5)²+((6)-6)² → min
f(X₂) = 4h²+24h+36 → min
Найдем такой шаг h, чтобы целевая функция достигала минимума вдоль этого направления. Из необходимого условия существования экстремума функции (f'(x₂)=0):
8h+24 = 0. Получим шаг: h = -3
Выполнение этого шага приведет в точку:

Шаг №3. Повторно сделаем шаг вдоль направления поиска p² = [0;1]^T

f(X₃) = 4(5-5)²+((h+6)-6)² → min
f(X₃) = h² → min
Найдем такой шаг h, чтобы целевая функция достигала минимума вдоль этого направления. Из необходимого условия существования экстремума функции (f'(x₃)=0):
2h = 0. Получим шаг: h = 0
Выполнение этого шага приведет в точку:

Шаг №4. Выбираем сопряженное направление: p² = x³ - x¹
p² = [5;6]^T - [8;6]^T = [-3;0]^T

Итерация №1.

Проверим критерий остановки:
|▽f(X₃)| < ε

Вычислим значение функции в начальной точке f(X₃) = 0.
Ответ: X = [5;6]^T

Пример №2. Минимизировать функцию f(x) методом сопряженных направлений, заканчивая вычисления при |d(x)/dx| < 10^-3, i=1,2,..,n.
x₁⁴+2*x₂⁴+x₁²*x₂²+2*x₁+x₂
Градиент функции

Итерация №1.

Итерация №2.