Міністерство науки, вищої школи і технічної політики Російської Федерації.
Новосибірський Державний
Технічний Університет.
Реферат з дослідження операцій на тему
«Метод Девідона - Флетчера - Пауелла».
Варіант № 2.
Факультет: АВТ.
Кафедра: АСУ.
Група: АС-513.
Студент: Бойко Константин Анатольевич.
Викладач: Ренін Сергій Васильович.
Дата: 19 жовтня 1997 року.
Новосибірськ
Введення.
Спочатку метод був запропонований Девідоном (Davidon [1959]), а потімрозвинений Флетчером і Пауеллом (Fletcher, Powell [1963]). Метод Девідона -
Флетчера - Пауелла називають також і методом змінної метрики. Він потрапляєв загальний клас квазіньютоновскіх процедур, в яких напрямки пошукузадаються у вигляді-Djf (y). Напрямок градієнта є, такимчином, відхиленим в результаті множення на-Dj, де Dj - позитивновизначена симетрична матриця порядку n (n, апроксимуютьсязворотну матрицю Гессе. На наступному кроці матриця Dj 1 представляється увигляді суми Dj і двох симетричних матриць рангу один кожна. У зв'язку зцим схема іноді називається схемою корекції рангу два.
Алгоритм Девідона - Флетчера - Пауелла.
Розглянемо алгоритм Девідона - Флетчера - Пауелла мінімізаціїдиференційованої функції декількох змінних. Зокрема, якщо функціяквадратична, то, як буде показано пізніше, метод виробляєпоєднані напрямки і зупиняється після виконання однієї ітерації,тобто після пошуку уздовж кожного з сполучених напрямків.
Початковий етап.
Нехай (0 - константа для зупинки. Вибрати точку х1 і початковусиметричну позитивно певну матрицю D1. Покласти y1 = x1, k =j = 1 і перейти до основного етапу.
Основний етап.
Крок 1. Якщо ((f (yj) ((((, то зупинитися, інакшепокласти dj = - Djf (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 наступним чином:
, (1) де pj = (jdj, (2) qj = f (yj 1) - f (yj).
(3)
Замінити j на j + 1 і перейти до кроку 1.
Приклад.
Розглянемо наступне завдання:
мінімізувати (x1 - 2) 4 + (x1 - 2x2) 2.
Результати обчислень методом Девідона - Флетчера - Пауелла наведенів таблиці 1.
Таблиця 1. Результати обчислень за методом Девідона - Флетчера - Пауелла.
| k | xk | j | yj | f (| ((f | D | dj | (j | yj 1 |
| | F (xk) | | f (yj) | yj) | (yj) ((| | | | |
| 1 | (0.00, | 1 | (0.00, | (-44.00 | 50.12 | | (44.00, | 0.06 | (2.70, |
| | 3.00) | | 3.00) |, | | | -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 | | (-0.89, | 0.11 | (2.45, |
| | 1.22) | | 1.22) | -0.44) | | | 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 | | (-0.18, | 0.10 | (2.25, |
| | 1.11) | | 1.11) | -0.20) | | | 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 | | (-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 визначається у вигляді
-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, 1.058) T на четвертій ітерації, так як норма ((f (y2) ((= 0.006досить мала. Траєкторія руху, отримана методом, показана намалюнку 1.
Малюнок 1. Метод Девідона - Флетчера - Пауелла.
Лемма 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
=-Djf (yj), а (j є оптимальним рішенням задачі мінімізації f (yj
+ (Dj) при ((0. Нехай, крім того, для
j = 1, ..., n - 1 матриця Dj 1 визначається за формулами (1) - (3). Якщо < br>f (yj) (0 для
j = 1, ..., n, то матриці D1, ..., Dn симетричні і позитивнопевні, так що d1, ..., dn - напрямки узвозу.
Доказ.
Проведемо доказ по індукції. При j = 1 матриця D1симетрична і позитивно визначена за умовою лем. Крім того,
f (y1) Td1 =-f (y1) TD1f (y1) (0, тому що D1 позитивновизначена. Тоді по теоремі 1 вектор d1 визначає напрямок спуску.
Припустимо, що затвердження лем справедливо для деякого j (n - 1, іпокажемо, що воно справедливе для j +1. Нехай x - ненульовий вектор з En,тоді з (1) маємо
(4)
Так як Dj - симетрична позитивно визначена матриця, тоіснує позитивно певна матриця Dj1/2, така, що Dj =
Dj1/2Dj1/2. Хай
a = Dj1/2x і b = Dj1/2qj. Тоді xTDjx = aTa, qjTDjqj = bTb і xTDjqj = aTb.
Підставляючи ці вирази в (4), отримуємо:
(5)
За нерівності Шварца маємо (aTa) (bTb) ((aTb) 2. Таким чином, щобдовести, що xTDj 1 x (0, достатньо показати, що pjTqj (0 і bTb (0.
З (2) і (3) випливає, що
pjTqj = (jdjT [f (yj 1) - f (yj )].
(6)
За предположеніюf (yj) (0, і Dj позитивно визначена, так що
f (yj) TDjf (yj) (0. Крім того, dj - напрямок спуску, і,отже, (j (0. Тоді з (6) випливає, що pjTqj (0. Крім того, qj
(0, і, отже, bTb = qjTDjqj (0.
Покажемо тепер, що xTDj 1 x (0. Припустимо, що xTDj 1 x = 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 1 x> 0, тобтоматриця Dj +1 позитивно визначена.
Оскільки f (yj +1) (0 і Dj +1 позитивно визначена, маємо
f (yj 1) Tdj +1 =-f (yj +1) T Dj 1 f (yj +1) <0. Звідси по теоремі
1 випливає, що dj 1 - напрямок спуску.
Лема доведена.
Квадратичної випадок.
Надалі нам знадобитися:
Теорема 2. Нехай f (x) = cTx + (xTHx, де Н - симетрична матриця порядку nx n. Розглянемо Н - зв'язані вектори d1, ..., dn і довільну точку x1. Нехай (k для k = 1, ..., n - оптимальне рішення задачі мінімізації
f (xk + (dk) при ((Е1 і xk +1 = xk + (dk. Тоді для 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. Нехай Н - симетрична позитивно визначена матриця порядку nx n. Розглянемо задачу мінімізації f (x) = cTx + (xTHx за умови x (En. Припустимо, що завдання вирішено методом Девідона -
Флетчера - Пауелла при початковій точці y1 і початкової позитивно певної матриці D1. Зокрема, нехай (j, j = 1, ..., n, - оптимальне рішення задачі мінімізації f (yj + (dj) при ((0 і yj 1 = yj + (jdj, де dj =-Djf (yj), а Dj визначається за формулами (1) -
(3). Якщо 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 1 Hpk, або, що еквівалентно, Dj 1 Hdk = dk для 1 (k (j, pk =
(kdk.
Проведемо доказ по індукції. Для j = 1 твердження 1 і 2очевидні. Щоб довести твердження 3, відмітимо перш за все, що длябудь-якого k справедливі рівності
Hpk = H ((kdk) = 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 1 Hdi, i (j. Таким чином, для i (j маємо
0 = diTf (yj +1) = diTHDj 1 f (yj +1) =-diTHdj 1.
Зважаючи на припущення індукції це рівність показує, що2 твердження також справедливе для j 1.
Тепер покажемо, що затвердження 3 справедливо для j 1.
Вважаючи k (j +1, маємо
. (8)
Враховуючи (7) і вважаючи k = j + 1 в (8), отримаємо, що Dj 2 Hpj +1 =pj 1. Тепер хай k (j. Тому що твердження 2 справедливо для j + 1, то pj 1 THpk = (k (j +1 dj 1 THdk = 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.
Гіммельблау Д. «Прикладне нелінійне програмування». М., 1975.
