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

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

{ап}

по правилу

[187]

«л-Н = Ри (u„ — ап — /

Y

а„ >

0,

/г =

0, 1,

. . .

(2)

В зависимости от способов выбора а„

в

(2)

можно

получить

различные варианты этого метода. Если 7

(и)

выпукла

и е С ‘ (7)

на выпуклом множестве U, то L(un) = / '(« „ ),

и метод (2) превра­

щается в метод проекции градиента.

Если

U = E m, то P u (u )= u , п

полагать, что

в

(2)

1{ип) =£0(/г = 0 ,■1,

2 ,...),

ибо. при

l(un) = 0 в

^ 1лу теоремы

1 в

точке

ип функция /(и) достигает своего мини­

мума на U. Рассмотрим

один вариант метода

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

функций. Именно в (2)

в качестве щ зафиксируем любую точку

из U, а {а„} выберем

произвольно,

лишь бы

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

условия [187]

оо

а „ > 0 ,

ая->-0 (п -эоо ),

£

а л =

+ о о

(3)

л = 0

^например,

ап = — - j- y

/г =

0, 1, . ..^ .

Т е о р е м а

2.

Пусть U

выпуклое

замкнутое

множество

в Ет,

имеющее хотя бы одну

внутреннюю

точку

(в частности,

возможно

U =

Em). Пусть функция J (и) непрерывна на U,

inf J (и) = J *^>— оо

и во

всех точках v £U

функция J (и)

имеет

опорную

функцию | =

= (/ (о), и). Тогда для последовательности {ц„},

построенной соглас­

но (2 — 3),

при

любом

начальном u0£U справедливо

равенство1

lim J (ип) =

J",

или, иначе

говоря,

существует

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

П - * оо

такая,

что / (u„s) —>J* (s

оо). (В формулировке теоремы

ность {u„J,

требования

на функцию J

(и)

можнб уточнить и ослабить;

см.

ниже

теоремы б, 7, 8.)

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

Прежде всего

заметим,

что

при выполне­

нии условий теоремы

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

{ип} из

(2 — 3)

определя­

ется однозначно (разумеется,

если 1(ип) — 0,

то ип— точка минимума,

1 Напомним,

что

число а =

lim ап — нижний

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

П-эоо

{а п},

если все предельные точки

(ол) не меньше а

и существует

такая подпос­

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

{п„Д , что a„k ~+a (k —>оо).

Верхний

предел

lim а„ ~ Ь

мож-

Я -*о о

88

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

[Гл. 2

Если

проекцию точки на множество U и опорные

функции

1{ип) найти несложно,

то метод

(2— 3)

очень прост. Однако этот

метод, вообще говоря,

немонотонный:

необязательно

J (un+1)^=

^ J ( u n),

поэтому близость J (ип)

к /* трудно проверяема. Различ­

[35, 96, 109, 154,

187— 189,

193, 251—253].

2. Выясним вопрос, какие функции обладают опорными функ­

циями во всех точках выпуклого множества

t/ sE ,n?

Т е о р е м а

3. Для того чтобы функции I(u ),

определенная на

выпуклом множестве U, имела опорную функцию во всех точках

множества U, необходимо,

чтобы J (и) была выпуклой на

U.

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

Возьмем

произвольные

точки и,

v 6(7 и

число а, 0 < а < 1 . По условию J (и)

во

всех

точках

множества U

имеет опорные функции. В

частности,

для точки иа = а и + (1 — а) у

существует вектор 1а , что

J (w) — J («а) >

(la, W— На)

при Всех

W6 U

Примем здесь

последовательно w — и и и. Получим

J {и)

J

(Ца) ^ (/(xi U

Ua) > J

(у) — J

(wа) ^

(/<Xi V — Cla)-

*

Умножим первое из этих неравенств на а,

второе — на

1 — а

и сло­

жим. Будем иметь

а J (и) + (1 — а) J (у) — J (а и + (1 — а) и) > (/а, иа — иа) = 0.

Отсюда и из

произвольности

и, v £ U ,

0 < а < 1

следует

выпук­

лость J(u). ±

пуклая функция

J (и) = — У 1 — ц2

в точках

и = ± 1

не имеет

опорных. Заметим,

что точки н = ± 1

являются граничными для об­

ласти определения

этой функции. Оказывается,

это

неслучайно.

Ниже будет показано, что всякая

выпуклая

на U функция во

внутренних точках

U имеет опорную функцию. Для доказательст­

ве Е п. Замыкание множества X в Е п обозначим через X,

множест­

во всех внутренних точек X — через Х°.

О п р е д е л е н и е 2. Пусть X

и У — два множества

из Ет.

Гиперплоскость (с, * )= a = c o n s t с

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

вектором

с ф 0

называется разделяющей множества X и У, если (с,

х ) ^ а ^

(с, у)

при всех х<=Х и г/еУ, или, иначе говоря,

inf {с, х) > a >

sup (с, у).

х £ Х

у&У