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

§ 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. ±