Файл: Васильев Ф.П. Лекции по методам решения экстремальных задач.pdf

§ Щ

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

Таккера

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 Ф. П.

Васильев

см. в работах

[25— 27, 73,

79, 89,

109, 111, 114, 116, 119,

133, 134,

149, 170, 191, 196, 199, 235, 239, 256, 260, 269] и др.

Не вдаваясь в подробности, укажем на следующий итерацион­

ный процесс:

^гг-Н == P (/i (Цп

ц1~>и {Pni

^л))>

] — P a i (рп Ф* CCrJ-'X

(Pti> Pn))>

n = 0,

1, . . . ,

чениям g(u)<C 0 ,

g ( u ) = 0 , руководствуясь удобством вычисления

проекции P Ut («).

Заметим, что проектирование на At осуществ­

ляется совсем просто:

Л 1

если

р* > О

РаЛ Ъ =

где Х= (р,,ц), ц '=

р‘ < 0 .

Л 5

0, если

Р (рп-pi» ^п)

minL (и, Ал),

Рл, (^л j ®пРх (Рп* ^я))»

1

п = 0,

1, . . .

Упражнение 1. Пусть множество

U = {u -.u ^ U i, g(n)<C 0}, где

U1 — выпукло,

g i ( u ) , t= l, 2 , . . . ,

s —

гладкие выпуклые функции