Навигация по сайту

Популярные статьи

Методи умовної оптимізації. Будівельна галузь

Головна Методи умовної оптимізації

[ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ] [ 12 ] [ 13 ] [ 14 ] [ 15 ] [ 16 ] [ 17 ] [ 18 ] [ 19 ] [ 20 ] [ 21 ] [ 22 ] [ 23 ] [ 24 ] [ 25 ] [ 26 ] [ 27 ] [ 28 ] [ 29 ] [ 30 ] [ 31 ] [ 32 ] [ 33 ] [ 34 ] [ 35 ] [ 36 ] [ 37 ] [ 38 ] [ 39 ] [ 40 ] [ 41 ] [ 42 ] [ 43 ] [ 44 ] [ 45 ] [ 46 ] [ 47 ] [ 48 ] [ 49 ] [50] [ 51 ] [ 52 ] [ 53 ] [ 54 ] [ 55 ] [ 56 ] [ 57 ] [ 58 ] [ 59 ] [ 60 ] [ 61 ] [ 62 ] [ 63 ] [ 64 ] [ 65 ] [ 66 ] [ 67 ] [ 68 ] [ 69 ] [ 70 ] [ 71 ] [ 72 ] [ 73 ] [ 74 ] [ 75 ] [ 76 ] [ 77 ] [ 78 ] [ 79 ] [ 80 ] [ 81 ] [ 82 ] [ 83 ]

завжди будуть в робочому списку; активність вихідних нерівностей в даному випадку залежить від того, чи звертаються в нуль відповідні допоміжні змінні.

Зауваження та вибрану бібліографію до розділу 6.3

Ідея «приведення» або «проектування» градієнтів спочатку висловлювалася щодо завдань з лінійними обмеженнями. Посилання на відповідні роботи дані в зауваженнях до розд. 5.1 і 5.2. Для задач з нелінійними обмеженнями перший метод «проекцій градієнтів» був запропонований Розеном (1961), який узагальнив сконструйований ним же аналогічний метод мінімізації при лінійних обмеженнях (Розен, 1960). Для визначення в алгоритмі Розена неявно використовується ортогональна матриця Zj.

Авторами схеми узагальнених наведених градієнтів є Абаді і Карпентье (1965, 1969). В її першій реалізації матриця (6.18) будувалася в явному вигляді. Програма, розроблена Абаді і його колегами по Electricite de France, широко застосовувалася для вирішення практичних завдань (див., Наприклад, Абаді і Гігу (1970)). Експериментальне зіставлення різних методів, проведене Колвілл (1968), показало, що методи узагальнених наведених градієнтів були одними з найбільш надійних і ефективних. До теперішнього моменту їх сімейство поповнилося великою кількістю нових алгоритмів: як уже було зазначено в розд. 6.3.1, для конкретизації кожного пункту схеми типу наведених градієнтів є Нама можливостей.

В останні роки иад методами типу наведених градієнтів в числі інших працювали Сарджент і Муртаф (1973), Абаді (1978), Лесдон і Уорен (1978),

Відомо, що при істотно нелінійних обмеженнях методи типу наведених градієнтів працюють погано, оскільки сильно іскрівлеітшге кордону допустгшого безлічі відстежувати важко (див. Розд. 6.3.2). У зв'язку з цим висувалися різні пропозиції, і зокрема пропонувалося занижувати необхідну точність дотримання обмежень. Правда, останнє означає пересмсгтр принципових позицій і перехід в клас методів спроектованого лагранжиана (див. Розд. 6.5). Загальний огляд методів типу наведених градієнтів з деякими міркуваннями щодо їх зв'язків з методами спроектованого лагранжиана читач знайде в статті Сарджент (1974),

6.4. МЕТОДИ МОДИФІКОВАНИХ функції Лагранжа

До класу методів модифікованих функцій Лагранжа можцо йти різними шляхами. Однак кінцеву мету завжди формулюють однаково: звести пошук вирішення завдань NEP або NIP до міні-

ції без обмежень, причому допоміжну функцію підібрати так, щоб (i) не було неминучою поганої обумовленості (як в методах гладких штрафних і бар'єрних функцій з розд. 6.2,1) і (ii) Ф мала безперервні перші похідні (на відміну від негладких штрафних функцій нз розд. 6.2.2).

6.4.1. ВИЗНАЧЕННЯ МОДИФІКОВАНОЇ функції Лагранжа

Методи, які ми будемо розглядати тут і в розд. 6.5, будуть отримані з розглянутих раніше умов оптимальності (див. Розд. 3.4) і істотно використовують множники Лагранжа, а точніше нх оцінки. Спочатку викладемо основні ідеї, не зупиняючись на деталях реалізації. Детальний опис способів оцінювання множників в задачах з нелінійними обмеженнями буде дано в розд. 6.6.

Методи модифікованих функцій Лагранжа можна використовувати і для задач з рівностями, і для задач з нерівностями. Принцип обліку рівності завжди один і той же, а для нерівностей можливі варіанти. Зазвичай використовується якась стратегія прогнозування активного набору, і тоді на початку кожного циклу безумовної мінімізації по нікому правилом визначається, які обмеження увійдуть в с "(див. Розд. 6.5.5). Інші схеми обліку нерівностей в методах модифікованих функцій Лагранжа обговорюються в зауваженнях. Поки ж заради простоти викладу припустимо, що заздалегідь відомо правильний список активних в х * обмежень, і через с {х) будемо позначати вектор, складений з їх функцій.

Надалі вважається, що в шуканої точці х * виконані достатні умови оптимальності нз розд. 3.4, зокрема

g {x) = A {xfX.

(6.22)

Тут А-матриця, чиї t рядків є градієнти активних в X * обмежень. Якщо Л (х *) має повний ранг, вектор X "визначається рівністю (6.22) однозначно. Введемо функцію Лагранжа

L {x, Ц = Р {х) - 1с {х).

(6.23)

(Зауважте, що визначення (6.23) залежить від того, як формується вектор с.) Співвідношення (6.22) означає, що при К = к * х * буде її стаціонарної (по х) точкою. Якби ця стационарность означала екстремальність, функцію Лагранжа можна було б використовувати в якості Ф. Проте в загальному випадку х * не доставляє мінімуму L {x, X *) (див. Другий фрагмент рис. 6Ь). Значить, навіть маючи X *, розраховувати на те, що X * вдасться знайти безумовної мінімізацією функції Лагранжа, не можна.


гл. 6. Завдання з нелінійними обмеженнями

Позначимо через Wix.k) матрицю других похідних по х від L {x, X), т. Е.

W (x, X) cw-XM, w. i = i

у tt (x *, X *) можуть бути і негативні, і нульові власні значення, але спроектовану матрицю Гессе (х ") W (х", X *) Z (х) в силу сказаного раніше ми вважаємо позитивно оп-редетеннок ( через Z (х) прийнято позначати матрицю, стовпці якої формують базис простору векторів, ортогональних рядках А (х)). Отже, х * буде точкою мінімуму L (х, X) по X на різноманітті, орпюгональном градиентам активних в х * обмежень.

Зазначене властивість оптимальності х * означає, що відповідну функцію Фу можна отримати, додавши до лагранжіаном доданок, яке, не порушивши стаціонарності х *, змінить властивості матриці Гессе щодо векторів з підпростору, натягнутого на стовпці А (x »). Найчастіше в якості такої поправки використовують квадратичний штраф, отримуючи тим самим модифіковану функцію Лагранжа виду

L (x. I, p) F (x) - kc (x) -i {xfc {x). (6.24)

Тут р-позитивний параметр штрафу.

У точці X * і сам квадратичний штраф, і його градієнт звертаються в нуль (оскільки з складається з функцій активних в X обмежень). Таким чином, прв Х = К * точка х * є стаціонарною (по х) для (6.24). Матриця Гессе штрафного терма дорівнює Ci (x) G, {x) -iA {xy А {х). При х = х * ненульовим в цьому

вираженні буде тільки другий доданок А {Хуа (х). Це-позитивно полуопределенная матриця, причому всі її власні значення, що відповідають власним векторам нз ранг-простору A (xY, більше нуля. Значить, поправка до функції Лагранжа в (6.24) приводить до збільшення (можливо, негативних) власних значень матриці W для векторів з ранг-простору А (xV, в той час як властивості матриці Гессе щодо векторів, ортогональних А {xY, зберігаються. Неважко довести існування кінцевого значення р, такого, що для будь-якого р> р матриця Гессе V}., i (х *, Х- *, р) буде позитивно визначена та спо тветственно в л * реалізується сильний локальний мінімум Lix, X *, р). При цьому незалежно від р для будь-якої матриці Z (х *), ортогональної рядках Л (х *), справедливо рівність

Z (x) VLL>, p) Z (x) = Z (x «) W {х; i.) Z {x).

6.4. Методи зміну функцій Лагранжа

т. е. на спроектовану матрицю Гессе штрафна добавка не впливає.

Проілюструємо ефект описаної модифікації функції Лагранжа иа простому прикладі.

Приклад 6.4. Розглянемо одновимірну задачу

знайти minx

при обмеженні х -) - 1 = 0.

Її єдиною допустимою і, отже, оптимальною точкою є х * = - 1, причому>. * = 3. Таким чином,

L (x,?. *) = X »-3 (х - 1).

Ця функція в х має локальний максимум. У той же час при будь-якому р> р (р = 6) модифікована функція Лагранжа

La (X, Х>, р) = х-3 (х + 1) (х-1 1) "

в X * досягає локального мінімуму. Графіки для х і L (x,?. *) Зображені на рис. 6h суцільний і нунктірнон лініями. Модіфі-


Модіфі-

Мал. eh. Суцільна лінія - графік цільової функції ІЕ прикладу 6.4, f (х) -х; пунктирна - графік функції Лагранжа; штрихова - графік моліфіціро-ванною функції Лагранжа Lix, л, 9).

царювати функція Лагранжа з р = 9 показана штриховою лінією. Відзначимо, що оіа не обмежена знизу при будь-якому значенні параметра штрафу р.


6.4.2. СХЕМ.А алгоритмів з модифікованою функції Лагранжа

Зі сказаного в розд. 6.4.1 випливає, що в ідеальному випадку X * можна знайти одноразової безумовної мінімізацією гладкої функції (6,24). Однак цей випадок практичного інтересу не представляє, оскільки передбачає знання вектора X *, а, не маючи рішення х *, його обчислити не можна. В реальній ситуації замість справжніх множників Лагранжа використовуються їх оцінки. Центральна роль, яку вони грають в методах модифікованих функцій Лагранжа, пояснює, чому ці методи часто називають також MetnoikiMU множників.

Відомо кілька способів застосування функцій типу (6.24) для пошуку умовного мінімуму. Єдині вони в тому, що завжди виникає п-мірна подзадача безумовної мінімізації диференціюється, що має в якості параметрів оцінки множників Лагранжа і включає штраф, призначення якого перетворити х * з безумовно стаціонарної точки в безумовно опт1шальную.

6.4.2.1. Модельна схема. В даному розділі схематично описаний один із способів пошуку мінімуму при ограніченіяч-неравен ствах з використанням модифікованої функції Лагранжа. Він передбачає завдання початкового списку включаються в с обмежень, початкової оцінки вектора множників Лагранжа Л », початкового наближення Хо, початкового значення параметра штрафу і позитивного цілого числа К, яке послужить верхньою межею кількості ітерацій. Визначивши все це і зробивши привласнення А - * - 0, треба виконати наступні дії.

Алгоритм AL (Модель методу модифікованої функції Лагранжа)

ALI. [Перевірка дотримання правил зупинки.] Якщо х задовольняє умовам оптимальності або А> / С, обчислення припинити. У першому випадку Xj береться в якості іско. мого рішення; у другому видається ознака невдачі.

AL2. [Мінімізація модифікованої функції Лагранжа.] Використавши Xj в якості початкової точки, застосувати процедуру вирішення підзадачі

(6.25)

що передбачає можливість необмеженість Lj знизу. Найкраще нз знайдених нею наближень взяти в якості Xfi + i.

AL3. [Перерахунок оцінок множників Лагранжа.] Якщо це доречно, змінити склад с. Обчислити новий вектор оцінок множників Лагранжа X + j.

знайти minL (x, Xj, р).

AL4. [Збільшення, якщо це необхідно, параметра штрафу.] Якщо в точці х +, невнзкі обмежень: ідачп істотно менше, ніж в х ,, перейти до наступного кроку, а інакше збільшити р.

AL5. [Переклад лічильника ітерацій.] Зробити привласнення ft. і повернутися до кроку AL1.

6.4.2.2. Властивості модифікованої функції Лагранжа. Припускаючи іспапьзовать який-небудь метод з модифікованою функцією Лагранжа 1л, треба мати на увазі наступні обставини.

- * - 1-1

Локальність мінімуму. Як і для штрафних функцій, описаних-іих в розд, 6.2 (за відсутності у вихідній задачі спеціальних властивостей), в точці х * в кращому випадку реалізується лише локальний мінімум La- При цьому La може бути не обмеженої знизу для будь-якого значення параметра штрафу р . Отже, застосовуючи до подзадаче (6.25) стандартний алгоритм безумовної мінімізації, потрібно передбачити в ньому відповідні запобіжні заходи (на що і зазначено в п. AL2 модельної схеми). Зазвичай збільшенням р врешті-решт вдається отримати настільки широку область тяжіння л: *, що необмеженість 1. стає безпечною. Однак повних гарантій збіжності до х * в загальному випадку дати не можна.

Труднощі вибору параметра штрафу. Підібрати відповідний параметр р іноді буває непросто навіть в таких ситуаціях, коли проблема необмеженості знизу модифікованої функції Лагранжа не виникає. Справа в тому, що серед значень р. забез-чивающих існування в х * локального безумовного мінімуму La, поряд зі «занадто великими» зазвичай є і «занадто малі». , І ті й інші дають погано обумовлені La. При завищених р функція La стає погано обумовленою з тих же причин, що і гладкі штрафні функції. Причиною поганої обус.1; оБлеіно-сти La при занижених р є виродження її матриці Гессе (еслн матриця Гессе звичайної функції Лагранжа знаконеопределеіа) при мінімальному допустимому р.

На рис. 61 зображені лінії рівня La (х, р) при трьох значеннях параметра р для завдання з прикладу 6.2, обмеження якої трактується як рівність. Друга функція (рО.2) обуслсшлена добре. Перша (р = 0.075) і третя (р = 100) ілюструють наслідки вибору занадто малих і дуже великих р.

Критична роль оцінок множників Лагранжа. Оскільки xf буде точкою мінімуму модифікованої функції Лагранжа лише якщо для збіжності використовує її л1етода при огра-

ніченний р необхідно забезпечити збіжність генеруються оцінок множників до X *.


[ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ] [ 12 ] [ 13 ] [ 14 ] [ 15 ] [ 16 ] [ 17 ] [ 18 ] [ 19 ] [ 20 ] [ 21 ] [ 22 ] [ 23 ] [ 24 ] [ 25 ] [ 26 ] [ 27 ] [ 28 ] [ 29 ] [ 30 ] [ 31 ] [ 32 ] [ 33 ] [ 34 ] [ 35 ] [ 36 ] [ 37 ] [ 38 ] [ 39 ] [ 40 ] [ 41 ] [ 42 ] [ 43 ] [ 44 ] [ 45 ] [ 46 ] [ 47 ] [ 48 ] [ 49 ] [50] [ 51 ] [ 52 ] [ 53 ] [ 54 ] [ 55 ] [ 56 ] [ 57 ] [ 58 ] [ 59 ] [ 60 ] [ 61 ] [ 62 ] [ 63 ] [ 64 ] [ 65 ] [ 66 ] [ 67 ] [ 68 ] [ 69 ] [ 70 ] [ 71 ] [ 72 ] [ 73 ] [ 74 ] [ 75 ] [ 76 ] [ 77 ] [ 78 ] [ 79 ] [ 80 ] [ 81 ] [ 82 ] [ 83 ]
0.0014

X,?
X,?