4.7. Методи штрафних функцій

Так як задача визначення мінімуму функції без обмежень є більш легкою, ніж задача визначення мінімума функції з обмеженнями, то природними є спроби зведення задач з обмеженнями до задач без обмежень.

Методи штрафних функцій дозволяють звести задачу нелійного програмування

/(и) -» тіп, неї/,

(4.63)

І/= |м є £„:&(«)<(),  / = 1,т|, (4.64)

де функції 3{и), gl{u),...,gm{u) визначені на Е/ та приймають

скінчені значення, до однієї або послідовності задач безумовної оптимізації деяких допоміжних штрафних функцій. При цьому допоміжна функція підбирається таким чином, що:

1. на більшій частині допустимої множини V задачі (4.63)-(4.64) ця штрафна функція є близькою до нуля;

2. кожна з них достатньо швидко зростає або при наближенні з середини множини и (внутрішні або бар'єрні функції), або при виході за його межі (зовнішня штрафна функція);

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

В комбінованих методах, які необхідно застосовувати при обмеженнях-рівностях, в процесі мінімізації одні з обмежень задовольняються, а інші ні. Але коли досягається розв'язок всі умови з заданою точністю задовольняються.

Метод зовнішньої точки

Основна ідея методу зовнішньої точки полягає в такому перетворені функції ./(«), при якому значення перетвореної цільової функції в допустимій області V точно або наближено дорівнюють значенням функції У(и), в той час як    значення поза межами

множини І/ дуже великі в порівнянні зі значеннями функції ./(«). В цьому випадку мінімум функції У(и) не буде суттєво відрізнятися від мінімуму перетвореної функції.

Визначення 1. Послідовність функцій {Р(и,гк)}, к = 1,2,...,

визначених на множині V, називають штрафною функцією множини І/ (зовнішньою штрафною функцією), якщо

(О,   якщо    «є її, ітР(«,гі)= (4.65) со,   якщо и<£и.

Метод штрафних функцій розв'язання задачі (4.63)-(4.64) полягає в заміні цієї задачі послідовністю задача безумовної оптимізації функцій

Зк(и) = 3(и) + Р(и,гк). (4.66)

При побудові допоміжної функції треба намагатися забезпечити необхідну  гладкість,  випуклість,  зручність  обчислення значень

функції та її градієнта. Якщо функції %і (и),   / = 1, т, не випуклі, то

штрафна функція не біде випуклою на множині І/. Тому вона може мати локальні мінімуми, в той час як вважається, що знаходимо глобальний мінімум задачі (4.63)-(4.64). Це порушує сходимість і є суттєвим недоліком методу штрафних функцій в застосуванні до невипуклих задач. В випадку, коли задача (4.63)-(4.64) є задачею випуклого програмування, то штрафна функція теж буде випуклою. Але виникає інша трудність. Для одержання якісного наближення слід гк вибирати достатньо великим. При цьому градієнт функції Р(и, гк )

по и також буде великим, бо він пропорційний гк. Але показано, що

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

Задача (4.66) розв'язується одним із методів безумовної оптимізації.

Теорема 1 (про сходимість). Нехай «/(и) еС'((7) задачі (4.63)-(4.64),а штрафна функція Р(и, гк ) має наступні властивості:

a) Р(и,гк) неперервна по обом змінним и, гк\ Р(и,гк) = 0, якщо и^І/;

b) Р(и,гк) монотонно зростає з ростом гк.

Нехай, крім того, для деякої сталої М множина им(к) = {иєЕп: Зк(и) <М} обмежена. Тоді:

а)функція Зк (и) досягає на Ея свого мінімума Зк, в деякій точці

(/,,, при цьому Зк, <, 3,, де 3, = тіп3(и) і Зк. —> 3.;

Ь) будь-яка гранична точка и. послідовності {и^*}^ —при к-їсо є точкою мінімума задачі (4.63)-(4.64), тобто вся послідовність ~*    "Р11   £ ~^ 00 •

(без доведення).

Штрафну   функцію    Р(и, гк)    можна   будувати різними способами. Наведемо кілька з них:

їй Я

Р(и, гк) = г£ [тах{£,(М),0}],  д > 0.

і=і

При ої=2 маємо квадратичну функцію.

1      (   т ' Р(и,п) =—ехр г1£[тах{й(«),0}] ,

г*        ^    і=і /

Р(и,гк) = гк тм[тах{&(и),0}].

і=1,т

Якщо  задача  (4.63)-(4.64)  містить  обмеження-рівності, то штрафну функцію можна вибрати в вигляді:

т «

д«.'і)='*і;ьі(«)). «ьі.

і=1

Алгоритм методу штрафних функцій.

Нехай функції У(н)єС'(£/) gi(u)єCї(U),  і = їт. Покладемо А=1, виберемо є>0, початкову точку ик<^Еп, штрафний параметр гк > 0 і число /? > 1.

Крокі. При заданій початковій точці розв'яжемо наступну задача безумовної оптимізації функції

Зк{и) = У(и) + Р(и, гк) -» тіп.

Покладемо ик+1 рівним оптимальному значенню цієї задачі. Крок2. Якщо Р(икіІ,гк) < є, то зупинитися, інакше гк=рУк,

к=к+ї та перейти до кроку 1. Алгоритм описано.

Метод внутрішньої точки (метод бар'єрів)

Головним  недоліком  попереднього  методу  є те,  що и,

апроксимується зовні, тобто різноманітні наближення щ,,..., ик,,

одержані при коефіцієнтах г1,,...ігк,і не належать множині V. Саме це

привело до того, що були запропоновані інші методи штрафу, в яких мінімум апроксимується в межах області V.

Визначення 1. Послідовність функцій {В(и,гк)},к = \,2,.„, визначених і невід'ємних в усіх внутрішніх точках множині V, називають бар'єрною функцією множини [/, якщо Р(и,гк) —> оо , коли и наближуються до межі множини І/.

Прикладами бар'єрної функції множини І/ можуть бути:

 

На відміну від методу штрафних функцій, в якості початкового наближення вибирається и0 е II. Мінімум для методу внутрішньої точки досягається в межах множини II, але не належить її межі для жодного гк > 0. Суттєво для цього методу, щоб \тАи Ф&.

Алгоритм методу визначення початкового наближення для методу внутрішніх штрафних функцій.

Нехай функції Ди)єС\и) gi{u)^Cl(U),  і = \~іп.

Покладемо к= 1, виберемо є > 0, початкову точку икєІІ, штрафний параметр гк > 0 і число (3 > 1.

Крокі. Покладемо 1 = {і,2,...,т}. Якщо 1 = {і: gi(ыt)<0}, то зупиняємось, при цьому ик задовольняє умові Я((и4)<0 для всіх

і = 1, т .

Крок2. Використаємо метод бар'єрів для розв'язання наступної задачі при початковій точці ик:

*'<И)^тІП' (4.66) &(«)<0,  і є Л

Покладемо иі+1 рівним оптимальному значенню задачі (4.66). Якщо £/(и*+і) — 0» 10 зупиняємося, так як множина {мєД,:   gJ.(u)<0,   / = 1,т| є пустою. В протилежному випадку

покладемо к=к+1 і перейдемо до кроку 1. Алгоритм описаний.

Алгоритм припинить свою роботу не більше ніж через т ітерацій або  повернувшись до точки  щ є II, яка задовольняє

нерівностям gj(и) < 0, / = 1,т , або впевнившись, що таких точок не існує.

Метод Фіакко та Мак-Корміка

Розглянемо задачу

Ли) —> тіп,  и є и, (6)и=

и є Д, :#,(«) <0,  і = 1,5

&(и) = 0,  / = 5 + 1,т

(7)

де gi ((/),   і = * +1, т у - лінійні функції.

В якості штрафних функцій в комбінованих методах можуть виступати, наприклад, наступні функції:

і   5      і т

Фк («)=т+-х ——+&    («),

і   т т

Фк{и)=т—2,п(-яди))+л/ї 2>?(и).

Процедура мінімізації функції Фк (и) починається з внутрішньої точки и0, в якій всі обмеження в вигляді нерівностей задоволені.

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

початкового вибору г0:

а) г0=1,

Ь) г0 = , де Д(и0) = £­1

ЛН)Г[Л'(Ц,)ҐЛН)

Щодо вибору подальших значень параметра г, то як показує практика, алгоритм пошуку мінімуму задачі (6)-(7) методом штрафних

функцій  буде  достатньо  ефективним,  якщо  послідовність {гк}визначається простим співвідношенням гк+1 = р\к, де /? > 1 є сталою (на практиці часто покладають /? = 4 ).

Умови сходимості методу Фіакко та Мак-Корміка.

Нехай    функції    Ди) є С2 (І/), & ((/) є С2 ((7),   і = ї^п, і виконані наступні умови: &УШІ/ #0;

b) Для будь-якого скінченого М і будь-якого гк > 0 множина точок

им (к) = \и^Еп:  Д («) < 0, і = й, Ди) + & X й2 («) < М|

обмежена;

c) функції %і («), і = 1,т, випуклі;

(і) функція /(и) випукла і сума ^Я,2(«) також є випуклою;

е)Гессіан розширеної функції Фк(и) не дорівнює нулю ні в одній із точок множини иі = ^і єЕя:   gj(u)<0,i = \,т\.

Теорема.     Якщо    задача    нелінійного програмування задовольняє умовам 1)-5), то

a) кожна розширена функція Фк (н) має мінімум в деякій точці

b) якщо {?(.}- строго монотонно зростаюча послідовність, то

Ііт Фк(Чк*) ~ птіп Ди) - «/(«* ) = 3»,

Тобто послідовність безумовних мінімумів функцій Ф/і(и) сходиться до умовного мінімуму функції У(н) .

Критерієм закінчення ітераційного процесу може виступати наступна умова:

Iі 1

—V-^£,де є > 0 - задана стала величина.

1м«,(")