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

Міністерство науки, вищій школі та програмах технічної політики Російської Федерации.

Новосибірський Государственный.

Технічний Университет.

[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 — 2×2)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. Нехай P. S — непорожнє безліч в Еn, точка x (cl P. S. Конусом можливих напрямів у точці x називається безліч D = {d: d (0, x.

+ (d (P.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 — симметрическая позитивно певна матриця, то існує позитивно певна матриця Dj½, така, що Dj = Dj½Dj½. Пусть.

a = Dj½x і b = Dj½qj. Тоді 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, тобто. Dj½x = (Dj½qj. Таким чином, 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 для і (k; і, 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 і трьох справедливі для j (n — 1. Покажемо, що вони також справедливі й у j + 1. Нагадаємо, що у утвердженню 1 теореми 2 diT[pic]f (yj+1) = 0 для і (j. По індуктивному припущенню di = Dj+1Hdi, і (j. Отже, для і (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] для і = 1, …, j. Отже, d1, …, dj+1 лінійно незалежні і запровадження 1 справедливо для j+1. Отже, затвердження 1, 2 і трьох виконуються. Зокрема сопряжённость 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.