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

(с, р < £ ,

{gi (uk), р ) < |

при is/ *,

|pl'| s ^ l(i= l,...,

т )}.

Так

как

Ak — замкнутое ограниченное множество, a v (a )= |

непрерывна на

Ак, то существует такая

точка

—

p*k)£Ah

что

m inv(a) =

*

*

a=Q<=Ah,

Ак

Если

~ v ( a k) =

^t. При этом

поэтому Efc<v(0) = 0.

на и найдено (Нь р\) =

ак.

3. Далее вычисляем новое значение параметра б:

„

(

б/г, если & < — бА,

Щ-Н =

{

0,5бА, если — бй< ^ < 0 .

[

Al =

{а = (|, р ): (с, р) <

g,

(gi (ик), р ) < Ъ

при i 6

/ь |р‘ |< 1 (i

= 1..........

т)},

где

I'k = { iA < i< s ,g i( u k)= 0}.

Пусть min v (а)

достигается на а

— (£*,

р*к).

Если окажется, что

цесс

на этом заканчивается.

Если же £&<(),

то

полагаем 6fe+i= 0,5S fe

и переходим к п.

4.

4. Наконец, полагаем ик+] =

ик - f a крк, где рк = pi

при ^ < 0 ,

а

если

^ =

0

и ! ь < 0 , то рк =

pi,

а число а к — min a ki,

где

a ki

есть

наименьший

положительный

корень

l<£<s

0 (i =

уравнения

g ( (uk -f а рк) =

= 1,

. . . , s) (если

при некоторых i

окажется,

что g t (uk -f apA) <

0

при

всех

a > 0 ,

то условно

принимаем

a ki = -)- оэ).

Очевидно,

J (щ+1) =

J

(ик) +

a k (с, pk) <

J (ик)

и % + iel/ .

§ 4}

Метод

возможных направлений

81

нейной)

gi(u) s£T0(t= 1 ,

s ) . Оказывается, для

определения и0

мизации функции v ( a )= |

на множестве Л/= { а = (| ,

и) '.gi{u)^.%r

i= 1, 2,_..., s}. Так как

по условию U содержит внутреннюю точку

ио,- то а0— (|о, и0) , где

f 0

= max g t (w0) < 0, будет

принадлежать

А', и, следовательно,

i<;<s

m inv(w )<0. Поэтому для того, чтобы полу-

решать эту вспомогательную задачу. Здесь

достаточно,

начиная

с произвольной точки u0t.E m, проделать

некоторое

конечное

Т е о р

е м а 2. Пусть U = { u : g i ( u ) ^ . О ( t = 1,..., s ) } , где g i ( u ) —

выпуклые

функции из С1(Ет), пусть U ограничено и имеет внут­

ным выше методом возможных направлений,

такова,

что:

1)

J (ик) =

(с,

ик) -+•J* = inf J

(и);

и

2)

любая ее

предельная точка и* будет точкой

минимума J (и)

на U, а в случае единственности точки минимума вся последова­

тельность {Wfe}->W*.

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

Так

как

{J{uk)}

монотонно

убывает

и

J (ик) >

J" > —оо. то существует lim J

(ик) и J

(ик)—J (ик+{) -»-0(&-нэо).

Покажем, что

k~>oo

(k-^oo). Последовательность {бА} положительна

и

монотонно

убывает, следовательно, существует

lim SA=

6 >

0.

Предположим,

что б > 0 .

Пусть

kn— номер

итерации,

когда

проис­

ходит дробление параметра б/;,

т.

е. — 6^ <

^

< 0

и бдп+1 =

0,58^

Если

lim 6,г =

б > -0,

то процесс

деления пополам

заведомо

конечен

и, более того,

найдется такой номер N0, что

8k =

8 и Ек <

— б при

всех

k > jV0.

Пусть

и* — предельная

точка

{ик}. Ясно, что u*£U .

Выбирая при необходимости

подпоследовательности,

можем

считать,

что

ик

и* (k -у оо).

Пусть

Г

=

{ i : K i < S

, - S <

g

;

(«’) <

0}.

В

силу

непрерывности g l (и) имеем — б <

(ик) < 0 при всех k ^ N x >//0

и г 6 /*.

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

а

1к при всех k ^ Nx. Тогда

(с - Р*) = (с,

Р к ) < & < — б,

(gi(uk), ,рк) < & <

— 8

82

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

[Гл. 2

бирая подпоследовательность, можем считать,

что pft->p*. Тогда при

k->-oo из

предыдущих

неравенств

имеем

(с,

р*) ф — 8 < 0 ,

(& («’),

Р *)< — б < °

при всех

Кроме

того,

£ £(« *)< — 6

при

i 0 I*

по определению /*.

Таким

образом,

р* Ф 0

и

направление

р*

является

подходящим

для

точки и*. Пусть

а* — min а*, где

a j — наименьший

положитель-

l< i< s

ный корень уравнения g ( (и* +

ар*) = 0

(t = 1 ,

. . .

,

s)

(если

при

не­

которых i

окажется,

что

(и‘ + ар‘ ) <

0

при всех а > - 0 , то условно

полагаем а* =

+ о о ). Тогда g t (и* -г ар*) <

0

при всех

а,

0 <

a < а \

и i = l , . . ,

,

s. В силу непрерывности

g c (и)

имеем gt (и'

арк) фО

при всех

к >

АР, >

0 < ^ а < ^ а ’ и t = 1 , . . .

, s.

Это

означает,

что

а к >

a* >

0 при всех к >

АР,. Тогда 0< а *8 < — ak (с, pk)= J(uk) — J{u-k+1)

при

всех

k >

iV2, что

противоречит соотношению

J(uk) — У (ик+\)

->■ 0 (k

оо).

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

8к->• 0 (/г

оо)

и

последовательность

{£,,},

когда

8 Ал+1 = 0,5 б&я и — Ькп <

< 0,

не

обрывается

ни

при

шагов — в этом

случае

теорема

очевидна).

Отсюда

вытекает,

что

Zkn-^0

при я -ь о о .

Теперь покажем, что У(ы*)->У\ Пусть

и* — предельная

точка

{ukJ .

Можем

считать,

что

икп~-^и*.

Обозначим /* =

( i : 1

<

i

< s ,

gi [и") = 0},

так

что

gi (и*) •<0

при

i 0 Г .

Покажем,

что

4

при всех л > АР,. Для

этого

обозначим

maxg( (и*) =

— 8*<^0. Тогда

ге/*

£ i(« * )< — s* при всех i 0

/*. Так как 8fe->0 и

(«fc/,)-vgi(u*)(t= 1, . . . ,s),

то найдется такой номер АР,, что

при всех п >

АР, будет g c (ик ) < —

— 0 .5 6 *< — 8 fen

для

i 0

Г

и

— 0.58*

< g f (uft/j) < 0 = g f («*)

для j £/*.

Это

и

означает,

что

/*:=э/*

при

всех л>А Р,. Пусть я*

не является точкой минимума У (и) на б/. В

силу

теоремы

1

тогда

существует

число

| < Д ,

и

вектор

рф О ,

такие,

что, (с,

р )< £ ,

(gi (и")> Р) < 1

(i 6

/*),

1рг'| < 1

(i = 1, . . .

,

/тг). Из непрерывности

gi (и) следует, что

(g't (ukJ ,

р) <

f при всех я >

М, и i £ h n ф }\.

По определению

^

тогда

имеем

при я > М 4, что проти­

воречит соотношению

-*-0(я-> - оо).

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

я* — точка ми­

нимума J (и) на U

и У {икп)

У (и*) = У\

Поскольку

У (я&) монотон­

но убывает,

то

и вся

последовательность

J (u k) - + J \

Тогда

любая

предельная

точка последовательности {ик}

является точкой минимума

У (и) на У, а в случае единственности

точки

минимума вся

последо­

вательность {ик}~^и".

А.

S 4}

Метод возможных направлений

83

О > gt (и) > g{ (ик) +

(g\ {ик),

и — ик)

при всех и 6 U и i — 1, . . .

, s. Это

означает,

что

U ст Uk = { и : (gi (ик),

и — и*) + & (“а) <

О

{ i = l , . . .

,

s)}.

Тогда mi n / (и) < m in/(«) = /* и приходим к

следующей

оценке по-

ик

и

грешности:

О <

/ {ик) — /* < /

{ик) — mi n/ (и) (k =

0, 1, 2 , . . . ) .

(1)=

uk

Эта оценка достаточно удобна на

практике,

поскольку

задача

минимизации J (и) на Uk является

стандартной задачей линейного-

задача минимизации J (и) на Uk

может быть решена достаточно

просто.

,

Всюду выше от подходящего

направления pk (k = 0, 1,...) мы

тов

метода

возможных направлений

подробнее

см.

в работах'

[79,

109, .114,

116,

135,

149,

177,

193,

196,

239,

260].

Упражнения.

1. Доказать эквивалентность двух задач миними­

зации .функций: /(«)

на множестве

U— {и : g i ( u )

s£:0(t=

1,..., s)} и.

/i(|,

и ) = £

на

множестве £Л = {(|,

и ) :/ ( а ) ^ | , gy(u) sg;0(i=

= l,...,s ) } .

м

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

\Гл. 2

ной

точкой] множества

U = {и : gi(u) ^ 0 ( i = 1 ,

s)}, £*(«)<=

е С(Ет ),

необходимо

и достаточно,

чтобы

(г^о) < 0

при всех

i —1

, s

[ g ' i ( w o ) = 0 ,

хотя

бы при

одном

значении

£,

Доказать.

переменных мы предполагали

существование градиента функций

в каждой точке множества U.

В этом параграфе рассмотрим один

Пусть задана функция J (и)

на некотором множестве U.

т

О п р е д е л е н и е

1. Линейная функция

(I, и) =

пе-

ременной u^U , определяемая

вектором

1= (к,

£=1

назы­

к , —, 1т),

вается опорной к функции J (и)

в точке u^U ,

если

J (и) > / (ц) +

(/,

и — v)

при всех и в U.

(1)

Вектор I назовем опорным

вектором

для

функции J (и)

в

точке

а е У .

Неравенство (1) геометрически означает,

что

гиперповерх­

ность, определяемая функцией £ = / (ц ),

лежит не

ниже

гиперпо­

верхности, определяемой линейной

функцией

£=(/,

и— у) + / ( у),

причем

при

и = и эти две

гипер­

поверхности

имеют общую точку

(рис. 11). Если J (и) — выпукла

и

е С ‘ (Д),

где

U — выпуклое

множество,

то

согласно

теоре­

ме 1.2 J (и)—J (и) ^

и— и)

при

всех

wet/,

т. е.

функция

£ = (/ '(ц ),

и),

является опорной к

J (и)

в

точке

v,

а

градиент

Л (у) — опорный вектор в этой

точке. Однако функция может

иметь

опорный

вектор

и в тех

случаях, когда Л (а) не сущест­

вует. Например /(u) =

|w|

в точке

и = 0

не имеет

производных,

§ 5]

Метод проекции опорных

функций

85

ми и функциями,

которые

в каждой

точке

обладают

опорной

функцией.

Понятие опорного

вектора обобщает понятие градиента

и

играет большую

роль

при

исследовании

экстремальных

задач

в

общей постановке

[73], [97], [99], [199], [269]. Различные свойст­

ва опорных векторов,

техника их вычисления в

конечномерных

и

Пусть функции

Ji(u)

в

точке

и

имеют

опорные

векторы

l i ( i — 1, 2, . . .

,

р).

Тогда:

1) функция

р

.

Ч-

J

a cJ c (и),

а£ =

(и) —

const >

О

i=i

р

в

этой

точке

имеет опорный

вектор

/ = ^

а £/£;

2)

функция

J

(и) =

max Ji (и)

i=i

в точке и имеет опорный вектор

Ш <р

i =

£

vA.

где у£ — произвольные числа,

такие,

что у£> 0 ,

£

у£ =

1,

а мно-

жество

индексов

I

(о) = {£:

1 <

i •< р,

J

(и) =

/£ (о)},

в

частности,

можно взять / =

/£,

i € I (v).

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

Необходимость. Если и* — точка миниму­

ма, то J (и) > J (и*) -)- (0,

и — и*) = J (и*) при всех

и 6 U,

т. е.

нуле­

вой вектор является опорным в точке и*.

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

Если

нулевой вектор

оказался опорньщ

к J (и)

в точке и*, то I(и)

(и*) + (0, и— u * ) = J( u * )

при

всех

« е У .

Следовательно, и* — точка минимума J (и)

на U. ±

§ 5]

Метод проекции

опорных функций

87

и итерации прекращаются).

Пусть

вопреки

утверждению

теоремы

lim J (ип) =

J*

2е, е /> 0. Рассмотрим множество

«“>00

Ме = { и : и 6 U, J (и) < J* + е}.

Покажем, что это множество имеет

внутреннюю точку.

Пусть и0—

внутренняя

точка U, существование

которой

вытекает

из

условия

теоремы. По определению J*

существует

такая

точка

v 6 U,

что

J (v) <

J" +

е/2. Так как точки и = v + а (и0— v)

при

всех а,

О <

<а<С1> являются внутренними для

множества U (см.

ниже упраж­

нение

1) и функция J (и) непрерывна, то можно указать

точку ие —

= v

а (е) (и0— v), которая

вместе

с

шаром

и& =

{и:\и — ие |< 6}

принадлежит U i i / ( w ) < J * - f e

при

всех

u £Us.

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

ие — внутренняя

точка МЁ и Ue czM s. Так

как

J (ип) > J* + е при

всех

0,

то J {u n) > J * +

е > / (и),

при всех

u^U&,

или 0 >

> / (и) — J

(ип) > (I (ип), и — ип)

при всех

и 6 U& и п > Nx.

В

част­

ности,

поэтому

и = ие +

б I (и„) 11(ип) I” 1е U6,

0 > ( / (ип),

иг — ип + б / («„) 11(«„) |- •) = (/ (и„), и8— «„) + 8 1/ К ) |,

или (/(«„),

ие — ип) </ — б I / (И„) | при всех п >

Л^.

Тогда,

учитывая

|ие — ип+1 12 = (Р у (ые) — Ру (ы„ — а„/ (ип) (I (ип) h 1) (2 <

< (ив— ип-f а„/ (м„) 11 {ип) |~! |2 = (иЁ-~ ип|2 +

+

+

2ап {I (ия) . «s ~'«я) 11 К ) |“ ■1< |«Е —

|3 + а* — 2а„б =

= I«е — «я I2 — &*я + а п (а„ — 6).

Так как

а „ -> 0, то а„ — б < 0 при всех п >

Nn, и, следовательно,

§ 5]

Метод

проекции опорных

функций

89

Если либо inf

(с, х)^>а,

либо sup (с, у) <

а,

то

говорят

о

строгом

х&Х

у £ У ■

inf

(с, х) = а,

то

гипер-

разделении этих множеств. Если при этом

х £ Х

плоскость (с,х) = а называют опорной к множеству-Л".

. Геометрический

смысл

разделяющей

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

(с, х) — а состоит в том,

что множество X находится в одном полу­

пространстве,

определяемом

этой

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

множество

У — в другом

(рис. 12,

13).

Если

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

{с, х ) = а

разде­

Рис .

13

ляет множества X и У, то, очевидно, гиперплоскость

(рс, л :)= р а

при любом

р > 0

также разделяет эти множества.

Поэтому

при

необходимости можно считать, что |с| =

1.

Т е о р е м а

4. Если X — выпуклое

множество

из Еп, то для

любой точку У0.Х0 существует

гиперплоскость_ (с,

х ) = а ,

с ф О,

разделяющая множество X и точку у. Если У0.Х, то

разделение

будет строгим. Если у — граничная точка X, то а = (с,

у).

Д о к а з а т е л ь с т в о . _Пусть сначала У0.Х (рис. 14). Проек­

цию точки у на множество X обозначим через у*. Так как у$ЁХ,

то вектор

с = у * —уфО. В силу_неравенства (3.1)

(с, х— г/*) =

= (у*— у, х— у*) > 0 при всех л е ! А тогда

(с, х — у) =

(«/*— у, х — у) =

\у*— у\2 + (у*— У, х — у*) >

> U / * - y l 2 = |c|2> o .