книги из ГПНТБ / Васильев Ф.П. Лекции по методам решения экстремальных задач

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 задается

несколькими

ограничениями типа

смотрения

достаточно провести на множестве U\\ в

частности,

здесь нет

необходимости задавать функции /(и), g i(« ),

Ph{u) на

всем пространстве Е т.

достаточно

быстро

возрастающую последовательность k — k n

(например,

fe„=10n,

п = 1, 2, . . . ) и использовать метод штрафных

лись, например, в работах [27, 35, 75, 109, 155, 170, 171,

192, 229,

235, 260]. Подробное изложение различных вариантов

метода

Будем рассматривать задачу

минимизации /(и)

переменных

ы = (и\

и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, . . , п), то будем писать х > у . Тогда сформулирован­

124

МИНИМИЗАЦИЯ

ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ

[ Г л . 2

где

Au =

i a =

(So, £):£>£■(“). So > J (“)}.

u t U i,

5 = {6 = (g0, g ) : g < 0 ,

Множества

Л и Б

не имеют общих внутренних точек.

В

самом деле,

если 6 =

(So, S) € -80,

то

g < 0 ,

g0 <•/(«*). В

то время

как для

точек

а =

(!„,

Е) € Л

имеем

g„ > /

(и) >

/(«’), в случае «6£/,

а

если же

и £ Ult

но

u<£U, то найдется

такой

номер

i, l < t < s ,

что

g£ >

> § г(и )> 0 .'.

Таким образом,

Л°

f] £ ° =

0 -

Далее,

Л и Б — выпук­

лые

множества в Es+ ь

В

самом деле, если

aL= (go, SO 6 A (i =

1, 2),

то

существует

6 Ux такое, что а, 6

Лы..

Покажем,

что тогда

аа =

аа1 + (1 — а) а2 =

(ag> +

(1 — а) %

ag1 +

(1 — a)vg2) 6 Л„аг,

при

любом а ,

0 < а <

1;

здесь ыа =

аиг +

(1 — а) и2 6

в

силу

вы­

пуклости

U1.

Из

выпуклости J (и), gi(u) имеем

8 («а) <

а § Ю

+

(■1 — а) g («г) <

а !1 -г- ( If— а) g2,

J («а) <

а/ (ых) +

(1 — а )7 (м2) <

ago - f (1 — a) go-'

Следовательно, aa £ Лца cz Л [при

любом

а ,

0 <

а <

1.

Аналогично

доказывается

выпуклость Б.

Согласно

теореме

5.5

тогда

существует

гиперплоскость

(с,

а ) = а =

const

с

направляющим

вектором c = (v 0,

/0) =7^0 ,

кото­

рая разделяет множества Л и Б. Это значит, что

‘

(с, b)

< а

< ( с ,

а), аЕ А, Ь£ В.

(6)

Левое неравенство (6) возможно лишь при сГ^гО, ибо

во

множе­

стве Б

содержатся точки 6 = (g о, S)

со сколь угодно

большими

по

модулю отрицательными координатами.

Покажем,

что v o > 0 .

Если

допустить v o = 0 ,

то

из

c — (vо, 1о)¥=0

следует 1офО. В

силу

регу­

лярности

множества

U тогда

найдется

такая

точка

о е/ 71э

что

(/„,

£ ( н ) ) < 0 .

Положим

в

(6)

а = (/(о),

g {v)±<=AvciA ,

b =

(J(u *),

0 ) е Б . При

v o = 0 получим

неравенство

(/о,

g ( w ) ) ^ 0 ,

противоречащее определению

о.

Следовательно,

v o > 0 ,

/0^ 0 .

ЙГ

Примем теперь в (6)

а = (J

(и), g (и)) 6 Л„ с= A, b — (J («*), 0) £ Б .

Будем

иметь

v0J

(и*) < v oy (и) +

(/0, g(u)),

или

если разделить

на

v0> 0

и принять V =

Vo

то

J

(и") < / ( « )

+

(Я*, g

(и))

при любом и 6 Ux.

(7)

126

МИНИМИЗАЦИЯ

ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ

[ Г л . 2

где р.£ > О,

f = l , 2 , . . .

,п,

а u£, i

=

1, 2,

. . . , р, могут быть

произ­

вольными ([114]., [116],

[134] и др.).

Пусть вектор у пред­

Д о к а з а т е л ь с т в о .

Д о с т а т о ч н о с т ь .

ставим в виде (.9). Тогда

при любом / 6 й

имеем

(У, I) = 2 V/ (с;> 0 + £ ? 6 , 0 = 2 ? / (Ъ, 0 < 0.

i=l

i=l

t=l

т. е. неравенство (8) справедливо

при любом / £ й .

Н е о б х о д и м о с т ь .

Пусть

вектор

у удовлетворяет условию

(8). Покажем, что тогда имеет место представление

(9).

В про­

странстве Ет введем множество

Z = [z = (г1, •••, г"1) : z =

£

№

+ 2

И/ с’> И/ >

°-

1= 1

1=1

t =

1, 2, . . . , /I,

р£, i — 1,

2,

. •. , р — произвольны|.

Нетрудно видеть, что множество Z — выпукло и замкнуто

(дока­

y^ Z . Предположим,

что г/gzZ. Тогда согласно теореме 5.4 сущест­

вует

гиперплоскость

(I, z— у ) = 0

с

направляющим

вектором

1т) Ф 0, строго разделяющая множество Z и точку у, т. е.

(/, z— у) < 0

при всех

z e Z .

Заметим,

что

поскольку

O eZ, то

(/, г/)>0. Покажем, что fe Q .

В самом деле,

(Л 2) = 2

Hi (ci- 0

-f-2 Hi (С/, l) < (/, «/) = const

t= l

i—'l

при всех

(X i^ O

и

произвольных Pi,

что

возможно только при

(с£,

I) = 0 ,

i = l ,

2, . . ,

р,

(Ci, 1)4:0, i =

1, 2, . . ,

п, т. е. /<=й. По усло­

вию

(8) тогда

(у, I) ^ 0 , в то время как по построению

(/,

у) > 0 .

Пришли

к противоречию, которое и доказывает теорему. ±

Рассмотрим следующую задачу: найти

min J

(u),

U =

:ы/> 0 ,

/£/,

Аи.= Ь, Аи <

6

( Ю )

и£Ц

где / — некоторое заданное подмножество индексов / среди

1 < / < т

(в частности, возможно,

/ =

0 , или / = { / : !

< / < //г});

§ Щ

Теорема Куна —

Таккера

127

заданные

матрицы

и векторы. Если

р = 0 или

s = 0, тогда

будем

считать, что в (10)

ограничения Аи = Ь или соответственно

Аи.^.Ь

отсутствуют.

Пусть

_А* , А*

— матрицы, порученные

транспонированием

ответственно

на

вектор-столбец

и = [ и11\;

uT— (ul, . . . t ит) —

\ит)

вектор-строка

(впрочем,

если это

не

может привести к недоразу­

мениям,

знак

Т

в обозначении вектор-строки

будем часто опус-

ТП

кать);

(и, а)

= ^

и1а ‘ —

скалярное

произведение векторов-столб-

i=i

цов и, а ^ Е т\ е5= ( 0 , . . . ,

0, I, 0 , . . . ,

0) — /-тый единичный коор­

динатный вектор;

i-тые столбцы матриц А, А, А*, А’

соответственно.

В этих обозна­

чениях имеем

m

m

m

Au = Yi “'А , Аи = £ и*А;, (Аи)) =

£

a hu’ =

•i=i

i=i

/=1

-

= (А*, и), (Аи)с = (Д*, и), и’ = (е., и),

и задача (10)

может быть записана

в виде (1):

найти min J (и),

иеи

U = {и :и £ Ult

g c (u) = (Ai, и) — bt = 0

(i = 1,

... , р),

gt.(u) =

(А*, и) — bt <

0 (t = 1, . . .

, s)},

где и х — {и : и 6 Ет, и1> 0 , i б I).

А* = ОЛ И*) € Лх = (А =

(р, р ): р б £ s> Ц > 0, ц б Ер},

такой, чтобы

пара

(«*, А*) образовала седловую точку вида- (2)

для функции

L(u,

A,)==/(u) +

(|.i, Аи—Ь) + (р, Аи— Ь) на множе­

стве П1Х Л 1.

128

МИНИМИЗАЦИЯ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ

[Гл. 2

Д о к а з а т е л ь с т в о .

Достаточность доказана в теореме 1.

Докажем

необходимость.

Пусть и* — точка минимума функции

J (и) на U. Покажем, что

функция L(u, X) на множестве 1Л Х Л i

имеет седловую точку (и*,

Л*). Направление

1т)¥= 0 на­

что и= и* + atef/ ,

т.

е.

и£ =

и *

+

ali >

0^ (i 6 /), А (и* + а/) — Ь,~А (и* + аI) <^.Ь

при всех

а,

0 < а <

а о. Введем множества

индексов

/I = "{i : 1 <

i <

s, (Au')i =

&,}, l\ =

{i : i 6 /,

u‘* =

0}.

Нетрудно ^видеть, что направление

I ф 0

будет

возможным

в

точке

и* тогда и только тогда, если A l= 0, (А1); < 0

lt > 0

(t 6 /2),

или

(Л;,/)

= 0

( i =

1, . .. ,р), (Л ;,/)<0

(гб /Г),

( -

e t., /)=-/,<0

(16 /2).

5( H )

Заметим также,

что в

силу выпуклости

множества

U направление /

будет

возможным

тогда и

только

тогда,

когда

существуют

точка

и 61/,

иф иС , и число в > 0 ,

такие, что l =

s(u — и*). Поэтому

в

си­

лу теоремы 1.3 будем иметь

(J ' (и*), и — и*) > 0

при всех и 6 1/

или

(J' (и*), /) > 0

для любого /, удовлетворяющего условиям

(11).

Поло­

жим в теореме 3 у = — J' (и'), с, = Ас, а в качестве

ci возьмем

век­

торы Л( при i 6 /*

и — ег при i 6 /2-

Как вытекает из (II)

и’ неравен­

ства (— Д (ы *),/ )< 0,

все условия теоремы 3 _выполнены,

и,

следо­

вательно,

существуют

числа

р£ > 0

(i 6 /1), р£|> 0

(t 6 /2)

и

Pi (i =

= 1, 2, ■■•,р),

такие

что

— J' (и*) =

РгА +

^ р И Н -

£ ]p i(— £/).

£J2)

i£l\

16/J

Положим П =

(p *7p V

где

р* =

(pi, • ^

, Рр),

^р* = (рь • • •,

Ps),

Рг и

р* взяты из (12),

недостающие числа р£ (i ф /])

положены

равными

нулю.

Тогда (12)

можно переписать в виде

J ’ (ц*) +.Л*р* +

Л*р* =

£

р*е;,:.р*|> 0,

рЦ >0 (г6 /2).

(13)

Покажем,

что

(и*, Я*) — седловая

толка

функции

L {и,

Я),= /(и) +

+ (р,~Ли— 6) +

(р, Ли — 6)

на множестве

х Ax.

В

самомделе,

L (и, Г ) -

L ( и * , Г ) =

J

(и) -

/ (и*) +

(р*, Л (и -

и*)) + (р*,

А (и -

и*))

Для гладкой выпуклой функции всегда J

(и) — J (и*) > ( J '

(и*), и — иГ),

поэтому с учетом (13) для любого u^U 1 получим

L (и, Я*) — L (и*, Г )

>

(J' (и*) + А У + I V

, и — и*) =

= Y,^ (в* « и — “ *) = S й ( « * — « О = j ]

> о.

iG/j

iG /j

t'G/j

Наконец, при всех Я 6 Лх будем

иметь

L (ц*, К ) — Н У , Я) = (р* — р,

Ли* — 6) +

(j?— р, Ли* —Ъ) =

= £

( р ; - р , ) ( Л и * - й ) ^ 2

(— (ч) (Ли* — б); > 0,

г^/*

так как р£> 0 ,

(Ли* — й)£< 0

при

Д

Теоремы 2 и 4 являются частным 'случаем следующей более

общей теоремы, которую также принято называть теоремой

Ку­

на — Таккера.

_

Т е о р е м а

5.

Пусть

U = {u :u ^ U u

g(u) ,^;0Л g(u) = 0 },

где

U\—заданное выпуклое множество из Ет, g(u) — (gi(u),

..., g's(u)),

ё ( и) =

( Ы ы)>

£ ? ( “ )) .

причем функции gi(u ),

i = l ,

2,

...,

s,

и

часть

функций gi(u) при

i = l ,

2,_... ,

r .^ s

являются

линейными,

т. е.

существуют

векторы

а£,

а£_ и

числа

bitJ> it

такие,

что

gi(u) = {au u)—bh

i= K 2 , . . . , р, gi(u) =

(a,-, u)—bt, i =

1,

2 , . . . ,

г,

a остальные

функции gv(il),

i = r + 1, . . . ,

s,

выпуклы

на

и

не

являются линейными (возможно, что s = 0 или г = 0, или r — s,

или

р = 0, т. е. некоторые из ограничений g(u)<C.0

или g (u )= 0 могут

отсутствовать в представлении множества U).

Пусть

существует

точка

a e l/ i,

такая,

что g i(v ) < 0 при i = r + l , . . . , s

(если

r = s ,

то

это условие отсутствует), и пусть J (и) выпуклая функция на U\.

Тогда,

для того чтобы в точке ( ( * e l /1

достигался

минимум функ­

ции J (и) на множестве U, необходимо и_достаточно существова­

ния точки Я *= (р *,

p * ) e A i =

{Я = (р, р)

: p e £ s, р ^ О ,

р е £ р},

та­

кой, чтобы пара

(u*,' Я*) образовала седловую точку вида

(2)

для

функции Лагранжа

L(u,

Я )= / (и ) + (р,

g'(u)) +

(p

g (u ))

на мно­

жестве Ui X A i.

Доказательство этой теоремы см.,

например,

в работе [269],

§ 28.

Теорема

Куна — Таккера имеет многочисленные приложения

ремы

в следующем параграфе будет

доказан

ряд

важнейших

теорем

линейного программирования.

Теорема

Куна

— Таккера

5 Ф. П.

Васильев