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


               Министерство науки, высшей школы и технической
                       политики Российской Федерации.

                        Новосибирский Государственный
                          Технический Университет.
                                    [pic]
                  Реферат по исследованию операций на тему
                   «Метод Дэвидона - Флетчера - Пауэлла».

                                 Вариант №2.

Факультет: АВТ.
Кафедра: АСУ.
Группа: АС-513.
Студент: Бойко Константин Анатольевич.
Преподаватель: Ренин Сергей Васильевич.
Дата: 19 октября 1997 года.

                                 Новосибирск
                                  Введение.

      Первоначально метод был предложен Дэвидоном (Davidon [1959] ), а затем
развит Флетчером и Пауэллом (Fletcher, Powell [1963]  ).  Метод  Дэвидона  -
Флетчера - Пауэлла называют также и методом переменной метрики. Он  попадает
в общий класс  квазиньютоновских  процедур,  в  которых  направления  поиска
задаются  в  виде  -Dj[pic]f(y).  Направление  градиента   является,   таким
образом, отклоненным в результате умножения на  -Dj , где Dj -  положительно
определенная  симметрическая  матрица  порядка  n  (   n,   аппроксимирующая
обратную матрицу Гессе. На следующем  шаге  матрица  Dj+1  представляется  в
виде суммы Dj и двух симметрических матриц ранга  один  каждая.  В  связи  с
этим схема иногда называется схемой коррекции ранга два.

                   Алгоритм Дэвидона - Флетчера - Пауэлла.

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

      Начальный этап.

      Пусть [pic](0 - константа для остановки. Выбрать точку х1 и  начальную
симметрическую положительно определенную матрицу D1. Положить y1 = x1,  k  =
j = 1 и перейти к основному этапу.

      Основной этап.

      Шаг 1. Если (([pic]f(yj) ((( (, то остановиться;  в  противном  случае
положить dj = - Dj[pic]f(yj) и  взять  в  качестве  (j  оптимальное  решение
задачи минимизации f(yj + (dj) при ( ( 0. Положить yj+1 = yj + (jdj. Если  j
( n, то перейти к шагу 2. Если j  =  n,  то  положить  y1  =  xk+1  =  yn+1,
заменить k на k+1, положить j=1 и повторить шаг 1.

      Шаг 2. Построить Dj+1 следующим образом :
                 [pic],                       (1)
      где
                 pj = (jdj,                                   (2)
                      qj      =       [pic]f(yj+1)       -       [pic]f(yj).
(3)

Заменить j на j + 1 и перейти к шагу 1.



Пример.

      Рассмотрим следующую задачу :

      минимизировать   (x1 - 2)4 + (x1 - 2x2)2.

      Результаты вычислений методом Дэвидона - Флетчера - Пауэлла  приведены
в таблице 1.

Таблица 1. Результаты вычислений по методу Дэвидона - Флетчера - Пауэлла.

|k|xk     |j|yj     |[pic]f(|(([pic]f|D     |dj      |(j  |yj+1      |
| |f(xk)  | |f(yj)  |yj)    |(yj) (( |      |        |    |          |
|1|(0.00, |1|(0.00, |(-44.00|50.12   |[pic] |(44.00, |0.06|(2.70,    |
| |3.00)  | |3.00)  |,      |        |[pic] |-24.00) |2   |1.51)     |
| |(52.00)| |(52.00)|24.00) |        |      |        |    |          |
| |       | |       |       |1.47    |      |        |    |          |
| |       |2|       |       |        |      |(-0.67, |0.22|(2.55,    |
| |       | |(2.70, |(0.73, |        |      |-1.31)  |    |1.22)     |
| |       | |1.51)  |1.28)  |        |      |        |    |          |
| |       | |(0.34) |       |        |      |        |    |          |
|2|(2.55, |1|(2.55, |(0.89, |0.99    |[pic] |(-0.89, |0.11|(2.45,    |
| |1.22)  | |1.22)  |-0.44) |        |[pic] |0.44)   |    |1.27)     |
| |(0.1036| |(0.1036|       |        |      |        |    |          |
| |)      | |)      |       |0.40    |      |        |    |          |
| |       |2|       |(0.18, |        |      |(-0.28, |0.64|(2.27,    |
| |       | |(2.45, |0.36)  |        |      |-0.25)  |    |1.11)     |
| |       | |1.27)  |       |        |      |        |    |          |
| |       | |(0.0490|       |        |      |        |    |          |
| |       | |)      |       |        |      |        |    |          |
|3|(2.27, |1|(2.27, |(0.18, |0.27    |[pic] |(-0.18, |0.10|(2.25,    |
| |1.11)  | |1.11)  |-0.20) |        |[pic] |0.20)   |    |1.13)     |
| |(0.008)| |(0.008)|       |        |      |        |    |          |
| |       | |       |       |0.06    |      |        |    |          |
| |       |2|       |(0.04, |        |      |(-0.05, |2.64|(2.12,    |
| |       | |(2.25, |0.04)  |        |      |-0.03)  |    |1.05)     |
| |       | |1.13)  |       |        |      |        |    |          |
| |       | |(0.004)|       |        |      |        |    |          |
|4|(2.12, |1|(2.12, |(0.05, |0.09    |[pic] |(-0.05, |0.10|(2.115,   |
| |1.05)  | |1.05)  |-0.08) |        |      |0.08)   |    |1.058)    |
| |(0.0005| |(0.0005|       |        |      |        |    |          |
| |)      | |)      |       |0.006   |      |        |    |          |
| |       |2|       |(0.004,|        |      |        |    |          |
| |       | |(2.115,|0.004) |        |      |        |    |          |
| |       | |1.058) |       |        |      |        |    |          |
| |       | |(0.0002|       |        |      |        |    |          |
| |       | |)      |       |        |      |        |    |          |


      На каждой итерации вектор dj для j = 1, 2 определяется в виде

–Dj[pic]f(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, 1.058)T на четвертой итерации, так как норма ((f(y2) ((=  0.006
достаточно  мала.  Траектория  движения,  полученная  методом,  показана  на
рисунке 1.



Рисунок 1. Метод Дэвидона - Флетчера - Пауэлла.
[pic]
      Лемма 1 показывает, что каждая матрица Dj положительно определена и dj
является направлением спуска.
      Для доказательства леммы нам понадобится :
      Теорема 1. Пусть S - непустое множество в Еn, точка x ( cl S.  Конусом
      возможных направлений в точке x называется множество D = {d : d ( 0, x
      + (d ( S при всех ( ( (0, () для некоторого ( > 0}.
      Определение. Пусть x и y - векторы из Еn и (xTy( - абсолютное значение
      скалярного произведения xTy. Тогда выполняется следующее  неравенство,
      называемое неравенством Шварца : (xTy( ( ((x(( ((y((.

      Лемма 1.

      Пусть  y1  (  Еn,  а  D1   –   начальная   положительно   определенная
симметрическая матрица. Для j = 1, ..., n положим yj+1 = yj + (jdj,  где  dj
= –Dj[pic]f(yj), а (j является оптимальным решением задачи минимизации  f(yj
+ (dj) при ( ( 0. Пусть, кроме того, для

j = 1, ..., n – 1 матрица Dj+1 определяется по  формулам  (1)  -  (3).  Если
[pic]f(yj) ( 0 для

j = 1, ...,  n,  то  матрицы  D1,  ...,  Dn  симметрические  и  положительно
определенные, так что d1, ..., dn – направления спуска.
      Доказательство.
        Проведем  доказательство  по  индукции.  При  j  =  1   матрица   D1
симметрическая и положительно определенная по условию леммы. Кроме того,

[pic]f(y1)Td1 =  –[pic]f(y1)TD1[pic]f(y1)  (  0,  так  как  D1  положительно
определена. Тогда по теореме 1  вектор  d1  определяет  направление  спуска.
Предположим, что утверждение леммы справедливо для некоторого j ( n –  1,  и
покажем, что оно справедливо для j+1. Пусть x  –  ненулевой  вектор  из  En,
тогда из (1) имеем
                 [pic]                                   (4)

      Так как Dj –  симметрическая  положительно  определенная  матрица,  то
существует  положительно  определенная  матрица  Dj1/2,  такая,  что  Dj   =
Dj1/2Dj1/2. Пусть

a = Dj1/2x и b = Dj1/2qj. Тогда xTDjx = aTa, qjTDjqj = bTb и xTDjqj  =  aTb.
Подставляя эти выражения в (4), получаем :
           [pic]                        (5)

      По неравенству Шварца имеем (aTa)(bTb) ( (aTb)2. Таким образом,  чтобы
доказать, что xTDj+1x ( 0, достаточно показать, что pjTqj  ( 0 и  bTb  (  0.
Из (2) и (3) следует, что

           pjTqj      =       (jdjT[[pic]f(yj+1)       –       [pic]f(yj)].
                 (6)

      По предположению[pic]f(yj) ( 0, и Dj положительно определена, так что

[pic]f(yj)TDj[pic]f(yj) (  0.  Кроме  того,  dj  –  направление  спуска,  и,
следовательно, (j  ( 0. Тогда из (6) следует, что pjTqj ( 0. Кроме того,  qj
 ( 0, и , следовательно, bTb= qjTDjqj  ( 0.
      Покажем теперь, что xTDj+1x ( 0. Предположим, что  xTDj+1x  =  0.  Это
возможно только в том случае, если (aTa)(bTb) = (aTb)2 и pjTx  =  0.  Прежде
всего заметим, что

(aTa)(bTb) = (aTb)2 только при  a  =  (b,  т.е.  Dj1/2x  =  (Dj1/2qj.  Таким
образом, x =  (qj. Так как x ( 0, то ( ( 0.  Далее,  0  =  pjTx  =  (  pjTqj
противоречит тому, что pjTqj ( 0 и ( ( 0. Следовательно, xTDj+1x >  0,  т.е.
матрица Dj+1 положительно определена.
      Поскольку [pic]f(yj+1) ( 0 и Dj+1 положительно определена, имеем

[pic]f(yj+1)Tdj+1 = –[pic]f(yj+1)T Dj+1[pic]f(yj+1) < 0. Отсюда  по  теореме
1 следует, что dj+1 – направление спуска.
                                                             Лемма доказана.
Квадратичный случай.

      В дальнейшем нам понадобиться :

      Теорема 2. Пусть f(x) = cTx + ( xTHx, где Н -  симметрическая  матрица
      порядка n x n.  Рассмотрим  Н  -  сопряженные  векторы  d1,  …,  dn  и
      произвольную точку x1. Пусть (k для k = 1, …, n - оптимальное  решение
      задачи минимизации

      f(xk + (dk) при ( ( Е1 и xk+1 = xk +  (dk. Тогда  для  k  =  1,  …,  n
      справедливы следующие утверждения :
        1. [pic]f(xk+1)Tdj = 0, j = 1, …, k;
        2. [pic]f(x1)Tdk = [pic]f(xk)Tdk;
        3. xk+1 является оптимальным решением задачи минимизации  f(x)  при
           условии

           x  -  x1  (  L(d1,  …,  dk),  где  L(d1,  …,  dk)   –   линейное
           подпространство, натянутое на векторы d1, …, dk, то есть [pic] В
           частности, xn+1 – точка минимума функции f на Еn.

       Если  целевая  функция  f  квадратичная,   то   в   соответствии   со
сформулированной  ниже  теоремой  3  направления  d1,  …,  dn,  генерируемые
методом   Дэвидона   -   Флетчера   -   Пауэлла,   являются    сопряженными.
Следовательно,   в   соответствии   с   утверждением   3   теоремы 2   метод
останавливается после завершения одной итерации в оптимальной  точке.  Кроме
того, матрица Dn+1, полученная в конце  итерации,  совпадает  с  обратной  к
матрице Гессе Н.
      Теорема 3. Пусть Н – симметричная  положительно  определенная  матрица
      порядка n x n. Рассмотрим задачу минимизации f(x) = cTx + (  xTHx  при
      условии x ( En. Предположим, что  задача  решена  методом  Дэвидона  -
      Флетчера - Пауэлла при начальной точке  y1  и  начальной  положительно
      определенной матрице D1. В частности,  пусть  (j,  j  =  1,  …,  n,  –
      оптимальное решение задачи минимизации f(yj + (dj) при ( ( 0 и yj+1  =
      yj + (jdj, где dj = -Dj[pic]f(yj), а Dj определяется по формулам (1) –
      (3). Если [pic]f(yj) ( 0 для всех j, то направления

      d1, …, dn являются Н - сопряженными и Dn+1 =  H-1.  Кроме  того,  yn+1
      является оптимальным решением задачи.
      Доказательство.
      Прежде всего покажем, что для j, такого, что 1 ( j  (  n,  справедливы
следующие утверждения :
     1. d1, …, dj линейно независимы.
     2. djTHdk = 0 для i ( k; i, k ( j.
     3. Dj+1Hpk, или, что эквивалентно, Dj+1Hdk = dk для 1 ( k  (  j,  pk  =
        (kdk.
      Проведем доказательство по индукции. Для j  =  1  утверждения  1  и  2
очевидны. Чтобы доказать  утверждение  3,  заметим  прежде  всего,  что  для
любого k справедливы равенства
           Hpk = H((kdk) = H(yk+1 - yk) = [pic]f(yk+1)  –[pic]f(yk)  =  qk.
      (7)
      В частности, Hp1 = q1. Таким образом, полагая j = 1 в (1), получаем
           [pic],
      т.е. утверждение 3 справедливо при j = 1.
      Теперь предположим, что утверждения 1, 2 и 3 справедливы для j (  n  –
1. Покажем, что они также  справедливы  и  для  j  +  1.  Напомним,  что  по
утверждению 1 теоремы 2 diT[pic]f(yj+1) = 0  для  i  (  j.  По  индуктивному
предположению di = Dj+1Hdi, i ( j. Таким образом, для i ( j имеем
                 0 = diT[pic]f(yj+1) = diTHDj+1[pic]f(yj+1) = –diTHdj+1.
       Ввиду  предположения   индукции   это   равенство   показывает,   что
утверждение 2 также справедливо для j+1.
      Теперь покажем, что утверждение 3 справедливо для j+1.
      Полагая k  (  j+1, имеем
           [pic].                 (8)
      Учитывая (7) и полагая k = j + 1  в  (8),  получим,  что  Dj+2Hpj+1  =
pj+1. Теперь пусть k ( j. Так как утверждение 2 справедливо для j + 1, то
           pj+1THpk = (k(j+1dj+1THdk = 0.                           (9)
      По предположению индукции из (7) и вследствие того, что утверждение  2
справедливо для j + 1, получаем
           [pic] .          (10)
      Подставляя (9)  и  (10)  в  (8)  и  учитывая  предположение  индукции,
получаем
            [pic].
Таким образом, утверждение 3 справедливо для j+1.
       Осталось  показать,  что   утверждение   1   справедливо   для   j+1.
Предположим, что [pic].  Умножая  это  равенство  на  [pic]и  учитывая,  что
утверждение 2 справедливо для j+1, получаем, что [pic]. По  условию  теоремы
[pic], а по лемме 1 матрица [pic] положительно определена,  так  что  [pic].
Так как H положительно определена, то [pic] и, следовательно, [pic].  Отсюда
следует, что [pic], и так как d1, …, dj линейно независимы по  предположению
индукции, то [pic] для i = 1, …, j.  Таким  образом,  d1,  …,  dj+1  линейно
независимы и утверждение 1 справедливо для j+1.  Следовательно,  утверждения
1, 2 и 3 выполняются.  В  частности  сопряжённость  d1,  …,  dn  следует  из
утверждений 1 и 2, если положить j = n.
      Пусть теперь j = n в утверждении 3. Тогда [pic] для k = 1, …, n.  Если
в качестве D взять матрицу, столбцами которой являются векторы  d1,  …,  dn,
то [pic]. Так как D имеет обратную, то [pic],  что  возможно  только  в  том
случае, если [pic]. Наконец, [pic] является оптимальным решением по  теореме
2.
                                                           Теорема доказана.

                             Список литературы.

1. Базара М., Шетти К. «Нелинейное программирование.  Теория  и  алгоритмы».
  М., 1982.
Химмельблау Д. «Прикладное нелинейное программирование». М., 1975.