Файл: Васильев Ф.П. Лекции по методам решения экстремальных задач.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.04.2024
Просмотров: 247
Скачиваний: 1
118 |
М И Н И М И З А Ц И Я |
Ф У Н К Ц И И М Н О ГИ Х ПЕРЕМЕННЫ Х |
[T.i. 2 |
|||
задачей |
минимизации |
однопараметрического |
семейства |
функций |
||
Jh (u )= = .J(u )+ P k (u) |
на |
всем пространстве, где Ph(u) — |
функция, |
|||
выражающая собой |
«штраф» за |
нарушение |
ограничений « е У , |
|||
a k — параметр, регулирующий величину «штрафа». |
|
|||||
Для примера возьмем задачу на условный экстремум из клас |
||||||
сического анализа: найти минимум функции |
J (и) на множестве |
|||||
|
U = |
{ u :g i (u) = 0, |
i = 1, 2, . . . |
,s}, |
(1) |
|
где 7(ы), ё\{и) — заданные функции, определенные на всем про
странстве |
Ет. |
Рассмотрим функцию |
J k ( u ) = J (и )+ k g (u ), где |
|
S |
|
|
|
|
g (u )= |
|
k — достаточно большое положительное число. |
||
£=1 |
|
|
служит «штрафом» за нарушение усло |
|
Слагаемое kg (и) = P h(u) |
||||
вия гге/У: |
если |
и<=0, то |
Р Л(и )з=0, а |
если u £ U , то Р%(и)>0 и |
при небольшом нарушении ограничения g .{u )= 0 величину «штра фа» можно сделать как угодно большой за счет выбора больших
k> 0 . |
Далее |
будем |
решать задачу |
минимизации |
Д (« ) |
на Ет, |
используя те |
или |
иные известные методы минимизации. |
Пусть |
|||
Д (« ) |
достигает своего минимума на Ет в точке %. Можно наде |
|||||
яться, |
что с ростом k функция Jk(u) |
будет достигать |
минимума в |
|||
таких точках Uk, которые все точнее и точнее удовлетворяют огра ничению g(u) = 0 , и, кроме того, Л (uk) - * J “= inf J (и).
|
|
|
|
Функцию Ph(«) |
u£U |
|
|
|
|||
О п р е д е л е н и е |
1. |
называют |
штрафной |
||||||||
функцией множества |
U, |
если Рь(и ) ^ |
0 при всех |
и ^ Е т и /г>0, и |
|||||||
|
lim |
Pk (и) = |
0, |
если |
и 6 U, |
|
|
|
|||
|
оо, |
если |
u ^ U . |
|
|
|
|||||
|
|
|
|
|
|
|
|
||||
Приведем примеры штрафных функций для множеств, зада |
|||||||||||
ваемых с помощью одного неравенства |
|
|
|
|
|
|
|||||
|
|
U = { u :u £ E m, g(u) < 0 } , |
|
|
|
(2) |
|||||
где g(u) — известная функция, |
определенная на |
всем |
простран |
||||||||
стве. |
|
|
|
|
|
|
|
|
|
|
|
Заметим, что в таком виде представимы широкие классы |
мно |
||||||||||
жеств. |
Например, |
множества, |
задаваемые |
системой неравенств |
|||||||
g i(u) ^ 0 |
(г= 1, . . . , |
s), нетрудно |
записать |
в |
виде |
(2): |
для |
этого |
|||
в (2) достаточно взять |
|
|
|
|
|
|
|
|
|||
|
|
|
|
* ( “) = £ |
fei (“)]+. |
|
|
|
|
|
|
|
|
|
|
£=1 |
|
|
|
|
|
|
|
где принято обозначение [g(M)]+ = m ax{0; |
g (u )}. Множества |
вида |
|||||||||
|
|
|
|
|
|
|
|
S |
|
|
|
(1) также записываются в виде (2) при g (и) = £ gf (и).
£=1
§ 9] |
Метод штрафных функций |
119 |
|
В качестве штрафной функции множества (2) |
могут служить, |
||
например, следующие функции: |
|
|
|
Рц (и) = |
k [g («)]+, Р„ (и) = |
k ([g (u)]+)2, |
|
Pk («■) = 4 - |
ekg(u\ Pk (и) = (1 + |
[g («)]+)* - |
1 |
k |
|
|
|
и др. В зависимости от метода, применяемого для минимизации функции J ii ( u ) = J (и) +Ри{и) на Ет> при выборе штрафной функ ции надо учитывать ее гладкость, удобство вычисления значений функции и ее производных и т. п.
Важно заметить, что нет необходимости точно решать задачу
минимизации Д (и ) |
на Ет при фиксированном /е>0, |
а нужно лишь |
|||||||||
позаботиться о том, чтобы с ростом k |
эта |
задача |
решалась все |
||||||||
точнее и точнее. |
А |
именно |
обычно |
берут ка_кую-либо функцию |
|||||||
е —е (6 )> 0 при & > 0 , е(£)-И ) при k-+oo |
и с |
помощью того или |
|||||||||
иного метода минимизации определяют точку Uih такую, чтобы |
|||||||||||
Л = |
inf. J k (и) < |
J k (uk) < |
4 |
-г e (k), |
k > |
0. |
(3) |
||||
|
uSEm |
|
|
|
|
|
|
|
|
|
|
Т е о р е м а |
1. Пусть функции /(u), |
g(u) |
определены |
и непре |
|||||||
рывны на Ет, |
i n f / ( w) > — оо, |
пусть |
U = |
{и : g(u) ^ 0 } . |
Пусть |
||||||
|
т |
|
|
|
|
|
|
|
Pk(u) ==Qh(g(u)) |
||
штрафная функция |
множества U |
имеет |
вид |
||||||||
(см. выше примеры), причем: 1) для каждого /г функция Q;t(g)
определена, |
непрерывна |
и |
неотрицательна |
при |
всех |
g; |
||||||||||
2) Q k(g)> 0, |
монотонно |
возрастает |
по |
g и 1 im Qk (g) = |
-j- ос при |
|||||||||||
g > 0 ; 3) |
если g ^ O , то |
Qk(g)-+0 |
(Jk-*-+oo) равномерно |
относи |
||||||||||||
тельно gs^O. Пусть {Uk} |
определены из условий (3) |
при некоторых |
||||||||||||||
е(/г) > 0 , г(/г)-+0 |
при k->-+ оо. |
|
|
|
|
|
|
|
|
|
||||||
|
Тогда: 1) |
Нгп / (uk) < |
J" — inf / (и), l i m g ( « ft) < 0 ; |
2) |
если |
мно- |
||||||||||
|
|
|
£-->оо |
|
|
« £ £ / |
|
£ — >4~°° |
бы одну предельную |
|||||||
жество {иА} при k |
+ оо будет |
иметь |
хотя |
|||||||||||||
точку и*, |
то |
и* — точка |
минимума |
J (и) на U\ 3) если |
множество |
|||||||||||
Ue — {u :g (и) ■< 6} |
ограничено хотя |
бы |
при |
одном |
6 = |
60]> 0 , то |
||||||||||
lim J (uk) — Г , |
р (uk, U) = |
inf \uk — и |->-0 |
(6-»-оо) и любая предель- |
|||||||||||||
£ - * о о |
|
|
|
|
|
и £ ( / |
будет точкой минимума J (и) |
на U, |
а в |
|||||||
ная точка {uk} при /г -> + |
о о |
|||||||||||||||
случае единственности точки минимума \uk — и* |-»- О |
[k |
оо). |
|
|||||||||||||
|
Д о к а з а т е л ь с т в о . |
Пусть |
{&,„} — какая-либо гминимизирующая |
|||||||||||||
последовательность |
J {и) |
на |
U, т. |
е. |
ьт6 U |
и J {vm) ->•Г (т |
оо). |
|||||||||
Возьмем |
произвольное е > 0 . |
Тогда |
найдутся |
такие |
числа |
/«о > 0 , |
||||||||||
k 0> |
0, что J |
( o j |
< |
/* + |
е, е (k) < |
е, |
Pk (om) = Qk (g (vm)) < |
г |
при всех |
|||||||
т > |
т0 и &>&„. |
Следовательно, |
с |
учетом (3) |
получаем |
|
|
|
||||||||
120 |
|
МИНИМИЗАЦИЯ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ |
|
[ Г л . 2 |
||||||||||
|
|
|
J |
(«*) < |
J k (ыА,) < Л -1- e (k) < |
J k («„,) + |
e = |
|
|
|||||
|
|
|
|
= |
J (vm) + |
Pк(Vm) + |
6 •< У* -f Зв. |
|
|
|
||||
Отсюда в |
силу |
произвольности е > 0 |
имеем Пгп J |
(«/г) < У’ . Далее, |
||||||||||
Q* (g (%)) = ^ (“ft) — ^ («*) < |
J* + |
Зе — inf J |
(«) < oo |
при всех |
k > £0. |
|||||||||
|
|
|
|
|
|
___ |
|
^m |
|
|
|
|
|
|
Это возможно£|только при |
lim g («ft) < О,) |
ибо |
в |
противном |
случае |
|||||||||
|
|
|
|
|
к.—too |
|
Ukn, |
|
|
|
|
|
|
|
существовала,(бы. ^последовательность |
для |
которой |
limg' (ы* ) = |
|||||||||||
- |
а > 0 |
и |
|
|
|
|
|
|
|
|
|
|
П - * оо |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
0 < |
|
< |
& я (£(«О ) ^ |
+ |
00 |
(Л-»-0°). |
|
|
||||
Наконец, |
пусть |
ы* — предельная |
точка 'множества |
{«*} |
при |
k —»оо, |
||||||||
т. е. существует |
последовательность |
«*п -» |
«* |
(/г-»-оо) .}• Тогда |
||||||||||
Пш g («й ) = |
g («*) |
0, т. е. «* 6 U■ Следовательно, |
|
|
|
|||||||||
П -Ю О |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
У* < |
У («*) = |
П т У («* ) < |
lim У (Uk) |
< У*, |
|
|
||||
|
|
|
|
|
|
П— >оо |
|
fe— >оо |
|
|
|
|
||
т. |
е. У («*) = |
J" . Последнее утверждение теоремы теперь очевидно.’^ |
||||||||||||
|
Если |
множество |
U задается |
несколькими |
ограничениями типа |
|||||||||
неравенств или равенств, то на практике часто бывает целесооб разно штрафовать не все из этих ограничений, а только некоторые из них. А именно пусть f/ = {u :« et/ | и gi(u).<Z.О, i — 1, 2,..., s}, где
Ux — множество достаточно простого вида и реализация тех или иных методов минимизации функций на множестве не встречает больших затруднений. Тогда на ограничения gi(u) ^ 0 ( г = 1, 2,...,s) можно наложить штраф с помощью какой-либо штрафной функ ции Ph(u) и перейти к задаче минимизации функции J k (« )= / (« ) + Р й(«) на множестве U\. Теорема 1 и ее доказатель ство и в этом случае полностью сохраняют силу, причем все рас
смотрения |
достаточно провести на множестве U\\ в |
частности, |
здесь нет |
необходимости задавать функции /(и), g i(« ), |
Ph{u) на |
всем пространстве Е т. |
|
|
Метод штрафных функций дает простую и универсальную схе му решения задач минимизации на множествах 11ф Ет и часто применяется на практике. Однако, как показывает численный опыт, при больших значениях k нахождение точек «л, удовлетво ряющих условиям (3), с ростом k становится все более трудным. Это связано с тем, что с ростом k методы минимизации, исполь зуемые для определения «л, сходятся все более медленно, и, кро ме того, оперирование с большими числами /г также вносит допол
§ Щ Теорема Куна — Тиккера 121
нительные погрешности в вычисления. Поэтому на практике целе сообразно поступать следующим образом. Сначала нужно задать
достаточно |
быстро |
возрастающую последовательность k — k n |
(например, |
fe„=10n, |
п = 1, 2, . . . ) и использовать метод штрафных |
функций до таких возможно больших п, пока удается получить достаточно быстрое убывание функции /(и) с небольшой затратой машинного времени. При этом для малых п слишком точное ре шение задачи минимизации /*(и) нецелесообразно, и успех в при менении метода штрафных функций часто зависит от согласован ного выбора величин к п и е(/еп) = е „ . Если на этом пути не уда-, лось получить решение с требуемой точностью и процесс движения к минимуму при некоторых п сильно замедлился, то далее прибе гают к услугам других более тонких и, вообще-говоря, более тру доемких методов минимизации, позволяющих получить'решение задачи с требуемой точностью. Решение, полученное с помощью метода штрафных функций на одном этапе, полезно использовать в качестве начального приближения на следующем этапе.
Различные аспекты метода штрафных функций рассматрива
лись, например, в работах [27, 35, 75, 109, 155, 170, 171, |
192, 229, |
235, 260]. Подробное изложение различных вариантов |
метода |
штрафных функций, обсуждение вычислительных аспектов этого метода, большое число примеров можно найти в книге [235]. В работах [55, 229] исследован другой способ учета ограничений типа (2), заключающийся в специальном выборе нелинейного преобразования координат, позволяющем перейти от задачи на условный экстремум к задаче поиска экстремума функции на всем пространстве.
§10. ТЕОРЕМА КУНА — ТАККЕРА
Вэтом параграфе рассмотрим теорему Куна — Танкера, за нимающую важное место в теории выпуклого программирования. Эта теорема представляет собой обобщение классического метода множителей Лагранжа [126] для определения экстремумй при на личии ограничивающих условий на случай, когда последние содер жат не только равенства, но и неравенства.
Будем рассматривать задачу |
минимизации /(и) |
переменных |
|||||||||
ы = (и\ |
и2, . . . , ит) |
на множестве |
|
|
|
|
|
||||
U {и : и е |
и ъ |
g L (и) < |
0 |
(г = |
1 , 2 , . . . |
, s), |
g t (и) = 0 |
(i = |
1, 2, . . . |
, р)}, |
|
где U1 — заданное множество в |
Е т, |
функции /(«), |
g i ( u ) , |
g i ( u ) |
|||||||
определены |
на |
и 1ш |
В |
частности, |
возможно, И\= £ т , |
или |
|||||
U{ = (п : ш ^ 0 (г = Л , 2 , . . . , т ) } . |
|
|
|
|
|
||||||
В дальнейшем для каких-либо двух векторов х = ( х и . . . , хп), |
|||||||||||
|
|
уп) |
будем |
писать х ^ у , |
понимая |
под |
этой записью |
||||
выполнение следующих неравенств: xi'^ yi ( i= 1, |
2, . . , |
/г). Если же |
|||||||||
xi> y i ( t =l , |
2, . . , п), то будем писать х > у . Тогда сформулирован |
||||||||||
