Метод Дэвидона-Флетчера-Пауэлла

Министерствонауки, высшей школы и техническойполитикиРоссийской Федерации. НовосибирскийГосударственныйТехническийУ ниверситет.Рефератпо исследованию операций на тему Метод Дэвидона - Флетчера- Пауэлла . Вариант 2. Группа АС-513.Студент Бойко Константин Анатольевич.

Преподаватель Ренин Сергей Васильевич.Дата 19 октября 1997 года. НовосибирскВведение.Первоначально метод был предложен Дэвидоном Davidon 1959 , а затем развит Флетчером и Пауэллом Fletcher, Powell 1963 . Метод Дэвидона - Флетчера -Пауэлла называют также и методом переменной метрики.

Он попадает в общийкласс квазиньютоновских процедур, в которых направления поиска задаются в виде-Djf y . Направление градиентаявляется, таким образом, отклоненным в результате умножения на -Dj , где Dj - положительно определенная симметрическая матрицапорядка n ? n, аппроксимирующая обратную матрицу Гессе. Наследующем шаге матрица Dj 1 представляется в видесуммы Dj и двух симметрических матриц ранга один каждая.

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

направлений. Начальный этап. Пусть gt 0- константа для остановки. Выбрать точку х1 и начальнуюсимметрическую положительно определенную матрицу D1. Положить y1 x1, k j 1 иперейти к основному этапу. Основной этап.Шаг 1.Если f yj lt e, то остановиться в противномслучае положить dj - Djf yj и взять вкачестве ljоптимальное решение задачи минимизации f yj ldj при l sup3 0.

Положить yj 1 yj ljdj. Если j lt n, то перейти к шагу 2. Если j n, то положить y1 xk 1 yn 1,заменить k на k 1, положить j 1 и повторить шаг 1. Шаг 2. Построить Dj 1следующим образом , 1 где pj ljdj, 2 qj f yj 1 - f yj . 3 Заменитьj на j 1 и перейтик шагу 1. Пример. Рассмотрим следующую задачу минимизировать x1 -

2 4 x1- 2x2.Результаты вычислений методом Дэвидона - Флетчера -Пауэлла приведены в таблице 1. Таблица 1. Результаты вычислений по методу Дэвидона - Флетчера -Пауэлла. k xk f xk j yj f yj f yj f yj D dj lj yj 1 1 0.00, 3.00 52.00 1 2 0.00, 3.00 52.00 2.70, 1.51 0.34 -44.00, 24.00 0.73, 1.28 50.12 1.47 44.00, -24.00 -0.67, -1.31 0.062 0.22 2.70, 1.51 2.55, 1.22 2 2.55, 1.22 0.1036 1 2 2.55, 1.22 0.1036 2.45, 1.27 0.0490 0.89,

-0.44 0.18, 0.36 0.99 0.40 -0.89, 0.44 -0.28, -0.25 0.11 0.64 2.45, 1.27 2.27, 1.11 3 2.27, 1.11 0.008 1 2 2.27, 1.11 0.008 2.25, 1.13 0.004 0.18, -0.20 0.04, 0.04 0.27 0.06 -0.18, 0.20 -0.05, -0.03 0.10 2.64 2.25, 1.13 2.12, 1.05 4 2.12, 1.05 0.0005 1 2 2.12, 1.05 0.0005 2.115, 1.058 0.0002 0.05, -0.08 0.004, 0.004 0.09 0.006 -0.05, 0.08 0.10 2.115, 1.058 На каждой итерации вектор dj для j 1, 2определяется в виде Djf yj , где D1 единичная матрица, а D2 вычисляется по формулам 1 -

3 . Приk 1 имеем p1 2.7, -1.49 T, q1 44.73, -22,72 T. На второйитерацииp1 -0.1, 0.05 T, q1 -0.7, 0.8 T и, наконец, на третьей итерацииp1 -0.02, 0.02 T, q1 -0.14, 0.24 T. Точка yj 1 вычисляется оптимизацией вдоль направления dj при начальной точке yj для j 1, 2.Процедура остановлена в точкеy2 2.115, 8 T начетвертой итерации, так как норма f y2 0.006 достаточно мала.

Траектория движения,полученная методом, показана на рисунке 1.Рисунок 1. Лемма 1 показывает, что каждая матрица Dj положительно определена и dj является направлением спуска.Для доказательства леммы нам понадобится Теорема 1. Пусть S - непустое множество в Еn, точка x cl S. Конусом возможных направлений в точке x называется

множество D d d sup1 0, x ld S при всех l 0, d для некоторого d gt 0 .Определение. Пусть x и y - векторы изЕn и xTy - абсолютное значение скалярного произведения xTy. Тогда выполняется следующее неравенство, называемоенеравенством Шварца xTy x y . Лемма 1. Пусть y1 Еn, а D1 начальная положительно определенная симметрическаяматрица. Для j 1, n положим yj 1 yj ljdj, где dj Djf yj , а lj является оптимальным решением задачи минимизации

f yj ldj при l sup0. Пусть, кроме того, дляj 1, n 1 матрица Dj 1 определяется по формулам 1 - 3 . Если f yj sup1 0 дляj 1, n, то матрицы D1, Dn симметрические и положительно определенные, так что d1 dn направления спуска. Доказательство. Проведемдоказательство по индукции. При j 1 матрицаD1 симметрическая и положительно определенная поусловию леммы.

Кроме того, f y1 Td1 f y1 TD1f y1 lt 0, так как D1 положительно определена. Тогда по теореме 1 вектор d1 определяет направление спуска. Предположим, чтоутверждение леммы справедливо для некоторого j n 1, ипокажем, что оно справедливо для j 1.Пусть x ненулевой вектор из En, тогда из 1 имеем 4 Так как Dj симметрическая положительно определенная матрица, то существуетположительно определенная

матрица Dj1 2, такая, что Dj Dj1 2Dj2. Пустьa Dj1 2x и b Dj1 2qj. Тогда xTDjx aTa, qjTDjqj bTb и xTDjqj aTb.Подставляя эти выражения в 4 , получаем 5 По неравенству Шварца имеем aTa bTb sup3 aTb 2. Такимобразом, чтобы доказать, что xTDj 1x sup3 0, достаточнопоказать, что pjTqj gt 0 и bTb gt 0. Из 2 и 3 следует, чтоpjTqj ljdjT f yj 1 f yj .

6 По предположениюf yj sup1 0, и Dj положительно определена, так чтоf yj TDjf yj gt 0. Кроме того, dj направление спуска, и, следовательно, lj gt 0. Тогда из 6 следует, что pjTqj gt 0. Кроме того, qj sup1 0, и , следовательно, bTb qjTDjqj gt 0. Покажем теперь,что xTDj 1x gt 0. Предположим, что xTDj 1x 0. Это возможно только в том случае,если aTa bTb aTb 2и pjTx 0.

Прежде всего заметим, что aTa bTb aTb 2только при a lb, т.е. Dj1 2x lDj1 2qj. Таким образом, x lqj. Так как x sup1 0, то l sup1 0. Далее, 0 pjTx l pjTqj противоречит тому, что pjTqj gt 0 иl sup1 0. Следовательно, xTDj 1x gt 0, т.е. матрица Dj 1 положительно определена. Поскольку f yj 1 sup1 0 и Dj 1положительно определена, имеемf yj 1

Tdj 1 f yj 1 T Dj 1f yj 1 lt 0. Отсюда по теореме 1 следует, что dj 1 направление спуска.Лемма доказана. Квадратичный случай. В дальнейшем нам понадобиться Теорема 2. Пусть f x cTx 1 xTHx, где Н - симметрическая матрица порядка n x n. Рассмотрим Н - сопряженные векторы d1, ,dn и произвольную точку x1. Пусть lk для k 1, , n - оптимальное решение задачи минимизацииf xk ldk при l

Е1 и xk 1 xk ldk. Тогда для k 1, , n справедливы следующие утверждения 1. f xk 1 Tdj 0, j 1, , k 2. f x1 Tdk f xk Tdk 3. xk 1 является оптимальным решением задачи минимизации f x при условииx - x1 L d1, , dk ,где L d1, , dk линейное подпространство, натянутое на векторы d1, ,dk, то есть В частности, xn 1 точка минимума функции f на Еn. Если целевая функция f квадратичная, то в соответствии со сформулированнойниже теоремой 3 направления

d1, , dn, генерируемые методом Дэвидона - Флетчера - Пауэлла,являются сопряженными. Следовательно, в соответствии с утверждением 3теоремы 2 метод останавливается после завершения одной итерации воптимальной точке. Кроме того, матрица Dn 1, полученная в конце итерации, совпадает с обратной кматрице Гессе Н.Теорема 3. Пусть Н симметричная положительно определенная матрица порядка n x n.

Рассмотрим задачу минимизации f x cTx 1 xTHxпри условии x En. Предположим, что задача решена методом Дэвидона -Флетчера - Пауэлла при начальной точке y1 и начальной положительно определенной матрице D1. В частности, пусть lj, j 1, , n, оптимальное решение задачи минимизации f yj ldj при l sup3 0 и yj 1 yj ljdj, где dj -Djf yj , а Dj определяется по формулам 1 3 .

Если f yj sup1 0 для всех j, тонаправленияd1 dn являются Н -сопряженными и Dn 1 H-1. Крометого, yn 1является оптимальным решением задачи.Доказательство.Прежде всего покажем, что для j, такого, что 1 j n, справедливыследующие утверждения 1. d1, ,dj линейно независимы.2. djTHdk 0 для i sup1 k i, k j.3. Dj 1Hpk,или, что эквивалентно, Dj 1Hdk dk для 1 k j, pk lkdk.

Проведем доказательство по индукции. Для j 1 утверждения 1 и 2 очевидны. Чтобы доказатьутверждение 3, заметим прежде всего, что для любого k справедливы равенстваHpk H lkdk H yk 1 -yk f yk 1 f yk qk. 7 В частности, Hp1 q1.Таким образом, полагая j 1 в 1 , получаем, т.е. утверждение 3 справедливо при j 1. Теперь предположим, что утверждения1, 2 и 3 справедливы для j n 1. Покажем, что они также справедливы и для j 1.

Напомним, что по утверждению 1 теоремы 2 diTf yj 1 0 дляi j. Поиндуктивному предположению di Dj 1Hdi, i j. Такимобразом, для i j имеем0 diTf yj 1 diTHDj 1f yj 1 diTHdj 1. Ввиду предположения индукции это равенствопоказывает, что утверждение 2 также справедливо для j 1. Теперь покажем, что утверждение 3справедливо для j 1. Полагая k j 1, имеем. 8 Учитывая 7 и полагая k j 1 в 8 , получим, что

Dj 2Hpj 1 pj 1. Теперь пусть k j. Так как утверждение2 справедливо для j 1, тоpj 1THpk lklj 1dj 1THdk 0. 9 По предположениюиндукции из 7 и вследствие того, что утверждение 2 справедливо для j 1, получаем . 10 Подставляя 9 и 10 в 8 иучитывая предположение индукции, получаем .Такимобразом, утверждение 3 справедливо для j 1. Осталось показать, что утверждение 1справедливо для j 1. Предположим, что . Умножая это равенство на и учитывая, что утверждение 2 справедливо для j 1,

получаем, что . По условию теоремы , а по лемме 1 матрица положительно определена,так что . Так как H положительноопределена, то и, следовательно Отсюда следует, что , и так как d1, , dj линейно независимы по предположению индукции, то для i 1, , j. Таким образом, d1, , dj 1линейно независимы и утверждение 1 справедливо для j 1. Следовательно, утверждения 1, 2 и 3 выполняются. Вчастности сопряж нность d1, , dn следует из утверждений 1

и 2, если положить j n. Пусть теперь j n в утверждении 3. Тогда для k 1, , n. Если в качестве D взять матрицу, столбцами которой являются векторы d1, ,dn, то . Так как D имеетобратную, то , что возможно только в том случае, если . Наконец, является оптимальнымрешением по теореме 2.Теорема доказана. Списоклитературы.1. Базара М Шетти К. Нелинейное программирование.

Теорияи алгоритмы . М 1982.2. Химмельблау Д. Прикладное нелинейноепрограммирование . М 1975.