4.4 Метод штрафных функций

Помимо метода возможных направлений существуют иные ме­тоды поиска условного экстремума. Одним из них является метод штрафных функций. Основная идея метода заключается в сведе­нии исходной задачи

/(ж) —т- П1ІП С; = {ж Є іГ І (рі(х) < О, г = 1,то}

(4.26)

(4.27)

к последовательности задач минимизации

Рк{х) —т- тіп ,   к = 1, 2,...

(4.28)

где -Рй(ж) — некоторая вспомогательная функция, которая под­бирается так, чтобы с ростом номера к она мало отличалась от исходной функции /(ж) на множестве С; и быстро возрастала на множестве В,п\С;. Быстрый рост функции ^(ж) вне С; приводит к тому, что при больших к нижняя грань этой функции на Кп будет достигаться в точках, близких к множеству С;, и решение задачи (4.28) будет приближаться при определенных условиях к решению исходной задачи (4.26)-(4.27). При этом имеется доста­точно большой произвол в выборе функций ^(ж). Это позволяет подобрать наиболее удобный вид минимизируемой функции ^(ж) и применить более простые методы безусловной оптимизации.

Определение 4.2 Функция Рк{х) называется штрафной фун­кцией множества С;, если Рк{х) > 0 для любых к = 1,2,...,

Из этого определения видно, что при больших номерах к за нарушение условия х £ С; приходится платить большой штраф, в то время как при х £ С; этот штраф стремится к нулю с ростом к (рис. 10).

ж Є К и

 

если х Є С; если х ^ С;.

А рм

Для любого множества С; можно указать сколь угодно много штраф­ных функций. Пусть [а]+ = тах(0, а) и

т

9(х) = £[^'(ж)] + .

i=l

Теперь множество допустимых решений представимо в виде

<2 = {х е Яп | д{х) < 0}, и штрафными функциями являются, например, следующие:

кд{х),   кд{х)2,   ек^/к,   (1 + д(х))к-1. Пусть штрафная функция Рк(х) уже выбрана. Положим

Рк(х) = /(х)+Рк(х), к =1,2,... и будем считать, что

т! Рк(х) > —со,   для всех к = 1,2,... (4.29)

Тогда для каждого к можно постараться найти решение зада­чи (4.28) и получить последовательность оптимальных решений.

К сожалению, нижняя грань в (4.29) может достигаться не при всех к. Поэтому зададимся последовательностью в (к) такой, что в (к) > 0, к = 1,2,... и в (к) —т- 0 при к —> оо и с помощью какого-либо метода безусловной оптимизации найдем точки хк, к = 1, 2,.. , удовлетворяющие условию

П = 1п|„ ВД < ^(я*) < Я+ €(*). (4.30)

Другими словами, вместо точного решения ж* будем искать при­ближенное решение хк с погрешностью, не превосходящей е(к). Отметим, что, вообще говоря, ж^ может и не принадлежать <5. Дальнейшее изложение уже не зависит от того, каким именно ме­тодом будет найдена точка хк. Поэтому мы ограничимся предпо­ложением о существовании такого метода и перейдем к исследо­ванию сходимости метода штрафных функций.

Пусть штрафные функции Рк(х) задаются с помощью вспомо­гательных функций Фк(д) равенствами Рк(х) = Фк(д(х)) и функ­ции Фк(д) таковы, что

a) Фк(д) определены и непрерывны для всех к = 1, 2,... ;

b) Фк(д) положительны, монотонно возрастают по д и Нт Фк{д) = +оо для д > 0;

к—>оо

c) Фк(д) сходятся к 0 равномерно при к —> оо в области д < 0. Тогда следующая теорема дает достаточные условия сходимости метода штрафных функций.

Теорема 4.6 Пусть функции /,д определены и непрерывны на Кп, т!хе[>п /(ж) > —со, штрафные функции удовлетворяют условиям а) Ь) с) и последовательность {хк} определяется со­отношениями (4.30). Тогда

1) Нт /(хк) < /* = т( /(ж)  и   Нт д(хк) < 0;

к—>оо к—>оо

2) если ж* принадлежит множеству Ыт{хк} предельных точек последовательности {хк}, то х* £ С; и /(ж*) = /*;

3) если множество С;$0 = {ж 6 Ка \ д(х) < 5о} ограничено для некоторого So > 0 , то lim f(xk) = /* и

k—>оо

p(xk,Q) = inf Цж^ — ж 11 —> О при к —т- со.

Доказательство. 1) По определению /* существует последова­тельность {ут},ут G Q, для которой f(y'm) —т- /* при т —> оо. Тогда для любого е > 0 найдутся номера то, ко такие, что

Дут)<Г + е, е(к)<е

при т > то,к > ко. Учитывая д(у'т) < 0 и условие с), можно считать, что

Рк{ут) = Ыд{ут))<£

при т > то, к > ко. Из этих неравенств и условий теоремы имеем

f(xk)<Fk(xk)<F*k+e(k)<

< Fk{ym) + е = f(ym) + Рк{ут) + € < Г + 36. Следовательно, lim f(xk) < f*.

к—>оо

Заметим, что при к > ко справедливо неравенство Ф*(</(ж*)) = Ffc(Sfc) - /(ж*) < Г + Зе - inf /(ж) < оо.

Покажем, что отсюда следует неравенство Нт д{х ) < 0. Пред-

к—>оо

положим, что верно обратное неравенство. Тогда существует по­следовательность {хкв}, для которой д{хкз) > а > 0 для всех в, больших некоторого во- Из условия Ь) имеем 0 < Фкз (а) < Фк8(д(хкв))     +оо при в —т- оо. Противоречие.

2) Пусть ж* 6 Ыт{хк}. Тогда существует подпоследовательность {хкв} сходящаяся к ж*. Функция д{х) непрерывна и, как доказа­но ранее, Нт д(хк) < 0. Поэтому Нт д{хкз) = д(х*) < 0. Сле-

/г->оо «->оо

довательно, ж* 6 <5- Из условий теоремы имеем /* < /(ж*) =

lim f(x s)1 а из определения верхнего предела следует обратное

s—>оо

неравенство lim f(xks) < lim f(xk) < f*. Поэтому f(x*) = /*.

s-S>oo fc->oo

3) Докажем, что из установленного неравенства lim д(хк) < О

к—>оо

следует p(xk,Q) —у 0 при к —У со. Предположим, что существу­ет г > 0 такое, что для любого s > 0 найдется номер ks > s, для которого p(xks,Q) > F. Рассмотрим подпоследовательность {xks}.

Из условия lim д(хк) < 0 следует, что существует номер No та­к—>оо

кой, что для любого ks > No справедливо g(xks) < So- Так как множество Qs0 компактно, то без ограничения общности мож­но считать, что подпоследовательность {xks} сходится к точке хо & Qs0- Из непрерывности функции д(ж) получим д(хо) < 0 и, следовательно, жо G Q. Учитывая компактность множества Q, с помощью неравенства треугольника легко доказать, что для лю­бых точек ж' и ж" справедливо неравенство

\p(x',Q) - p{x",Q)\ < \\х' - х"\\.

Следовательно, функция p(x,Q) — непрерывна. Тогда

p(xks, Q) —т- р(х0, Q) при s —> со.

Поэтому справедливо неравенство р(хо, Q) > г > 0. В то же время выше было доказано, что жо G Q. Получили противоречие. Мы показали, что из неравенства lim д{хк) < 0 следует p(xk,Q) —у 0

к—>оо

при к —у со. Аналогичным образом можно показать, что из нера­венства lim д(хк) < 0 следует lim f(xk) = /*. Теорема доказана.

к—>оо к—>оо

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