Файл: Васильев Ф.П. Лекции по методам решения экстремальных задач.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.04.2024
Просмотров: 252
Скачиваний: 1
S 5] |
Метод проекции |
опорных функций |
|
95 |
||
3. Пусть |
точки |
щ(1 = 0, |
1, . . . , гп) |
таковы, |
что |
векторы |
щ— u0(i = 1, . 2, . . . , m) |
линейно |
независимы. |
Образуем множество |
|||
|
m |
|
|
|
m |
|
S = |
ЩЩ ПРИ всевозможных |
щ > 0 , |
^ щ = |
l j, |
||
|
i= 0 |
|
|
|
i=0 |
|
называемое выпуклой оболочкой множества точек «о,. . . , ит, или симплексом, натянутым на эти точки. Доказать, что 5 — выпук лое множество, и точка u0^ S является внутренней точкой 5 в пространстве Ет тогда и только тогда, если
|
т |
|
т |
ы0 |
— V aiUi при |
> |
0, V ос; = 1. |
|
£=0 |
. |
i= 0 |
Доказать, что если |
точки и0, . . . , |
ит принадлежат некоторому вы |
|
пуклому множеству U, то симплекс 5с=Д. |
4. Точка uq является внутренней точкой выпуклого множества
Uc^Em тогда и только тогда, если равенство |
(I, и— ы0) = 0 при всех |
u ^ U может выполняться только при /=0, |
т. е. выпуклое множе |
ство с внутренними точками не может лежать ни в одной гипер плоскости в Ет. Доказать.
|
У к а з а н и е. |
Доказать |
существование точек |
ии . . . , |
um^ U , |
||||||||||
Для которых |
векторы и\— и0, . . . , |
ит— и0 линейно |
независимы, и |
||||||||||||
воспользоваться упражнением 3. |
|
|
|
|
|
|
|
||||||||
|
5. |
Выпуклое множество |
UczEm не имеет внутренних точек тог |
||||||||||||
да |
и |
только |
тогда, |
если |
существует |
вектор /=Ф0 |
такой, что |
||||||||
(/, |
и— «0) = 0 |
при всех ие(/, |
т. е. множество U лежит в некоторой |
||||||||||||
гиперплоскости (точку и0 можем |
считать принадлежащей |
U). |
|||||||||||||
U, |
6. Пусть /(и) — выпуклая функция на выпуклом множестве |
||||||||||||||
пусть (i+ e/ eU |
при всех |
е, 0 ^ е < Е 0. Доказать, |
что J (и) имеет |
||||||||||||
производную по направлению 1\ |
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
d J |
(и) __ |
|
J |
{u + |
&l) — J |
(и) |
|
|
|
|
|
|
|
|
|
dl |
e-H-0 |
|
8 |
|
|
|
|
|
||
где |
|/|= 1. |
Доказать |
[199], |
что |
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
d J (и) |
|
sup |
( с , |
I ) , |
|
|
|
|
|
|
|
|
|
|
|
dl |
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
с £М( и) |
|
|
|
|
|
|
||
где М (и )— множество всех опорных к |
J |
(и) |
векторов в точке и. |
||||||||||||
|
7. |
Найти все опорные векторы для функций: a) J (и) — \и— 1 1+ |
|||||||||||||
+ |и+1|, |
и ^ Е г\ б) |
/ (и1, и2) = |
|и1— ы2|;— |и1 + |
иа|; |
в) |
J{u) = |
|||||||||
— шах {и2; и - f |
2}, |
и £ Е г. |
|
|
|
|
J(u }i ui) = |
|
|и1 -f- иЧ I. |
||||||
|
8. |
Найти |
все |
опорные |
векторы для |
sup |
96 |
М И Н И М И З А Ц И Я Ф У Н К Ц И И М Н О ГИ Х ПЕРЕМ ЕННЫ Х |
|
[Гл. 2 |
|
9. |
Описать метод проекции опорных функций для. задачи |
|||
нимизации функции |
|
|
|
|
J |
(а1, и2) = шах 112 -i- иЧ + u21 при 0 < |
u‘ < 1 (i = |
|
1, 2). |
|
K|«l |
|
|
|
10. |
Как нужно доопределить функцию |
J (и) = |
1 |
в точке |
|
||||
|
|
1 + |
е х>и |
и = 0, чтобы она стала полунепрерывной снизу?
11. Пусть J |
(и) определена, конечна и полунепрерывна |
снизу |
||
в каждой |
точке |
замкнутого ограниченного |
множества U a E m. |
|
Доказать, |
что тогда /(гг) ограничена снизу на |
U и достигает |
на U |
своей точной нижней грани.
§ 6. МЕТОД УСЛОВНОГО ГРАДИЕНТА
Рассмотрим один метод, пригодный для минимизации функ ции на ограниченном множестве. А именно пусть U — ограничен ное выпуклое замкнутое множество в 'Ет, и пусть задана функция /(гг) е С (U ) . В качестве начального приближения возьмем неко торую точку Если известно /г-е приближение ггп, то прира щение функции /(гг) в точке ип представимо в виде
J (гг) — / (гг„) = (/' (гг„), гг — и„) + о ( |гг —
Возьмем |
главную |
линейную |
часть этого приращения /„ (гг) = |
|
s= (/ '(гг„), |
и — гг„) |
и определим |
вспомогательное приближение |
ип из |
условия |
|
|
|
|
|
/„(гг„) = тт / „(гг) |
= ппп(/'(гг„), гг — гг„). |
(1) |
|
|
|
(ISC/ |
u £ U |
|
Так как множество U замкнуто и ограничено, а линейная функ
ция /„(гг) непрерывна, то такая точка гг„е1/ существует. Сразу же заметим, что
|
min /„ (гг) — /„ (гг„) |
/„ (гг„) |
0. |
|
|
|||
|
|
и |
|
|
|
|
|
|
Если |
окажется, |
что |
/п(ггп) = 0 , |
то |
с |
учетом |
(1) |
имеем |
(/'(ггп), |
гг— ггп) ^ 0 |
при всех гге£/. Согласно |
теореме 1.3 это озна |
|||||
чает, что ип удовлетворяет необходимому |
условию |
минимума. |
||||||
В этом |
случае итерации |
прекращаются, |
и |
для выяснения |
того, |
|||
будет ли ип точкой минимума /(гг) на U, |
нужно дополнительно |
|||||||
исследовать поведение функции в окрестности этой точки. В |
част |
ности, если /(гг) выпукла на U и /„(гг„)=0, то ип в самом деле будет точкой минимума. В дальнейшем будем предполагать, что
§ 6} Метод условного градиента 97
J n (un) < 0. Тогда заведомо ипф и п, и в качестве следующего приб лижения ип + 1 принимаем
«л+1 = и „ + а„(ы „ — |
и„), |
0 < . а „ < 1. |
(2) |
|
В силу выпуклости |
множества U |
точка |
un+i<=‘U. |
В зависимости |
от способов выбора |
величины а п в |
(2) можно получить различные |
варианты описанного'метода, именуемого в литературе методом условного градиента [35, 82, 97, 155, 229] и др. Рассмотрим неко торые из них.
1. Пусть а„ в (2) выбирается газ условия [97, 229]
gn К ) =m in gn(a), gn(а) = J (ип + а (йп— «„)). |
(3) |
0<а<1 |
|
Для определения ап могут быть использованы методы гл. 1. При
таком |
выборе |
а п |
последовательность |
{/ («„)} |
не возрастает, |
так |
|||||
как |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
J (««) = |
ёп (0) > |
gn К ) |
= J (u„+i). |
|
|
|||
Т е о р е м а |
1. |
Пусть |
U — |
замкнутое выпуклое ограниченное |
|||||||
множество из Ет, |
пусть / (ы )е С ‘ (Д) |
и градиент /'(и) |
удовлетво |
||||||||
ряет |
условию |
Липшица: |
\J'(u)— /'(и) |.5g;L|a— v\ |
при |
всех |
||||||
и, к е !/ , |
L — const>0. Пусть |
«о — произвольная начальнаяточка |
|||||||||
из U и |
последовательность |
{«„} определена |
согласно |
условиям |
(1)— (3). Тогда
|
|
h (йя) = |
(J' (и„), ип— «„)-> 0 |
(п |
оо). |
_ |
|
||
|
Если, кроме того, |
J (и) выпукла на |
U, |
то последовательность |
|||||
К } |
является |
минимизирующей |
и любая |
ее предельная |
точка |
||||
будет точкой |
минимума J (и) на |
£/, причем |
в |
случае |
единственно |
||||
сти точки минимума к ней сходится вся |
последовательность |
{ип}. |
|||||||
Справедлива оценка |
|
|
|
|
|
|
|
||
|
0 < a n = J(u n) ~ J ( u t) < ^ ~ , |
n = l , 2 , . . . , |
|
(4) |
|||||
|
|
|
|
п |
|
|
|
|
|
где и* — точка минимума J (и) на U, а С — постоянная, незави |
|||||||||
симая от п, С > 0. |
|
|
|
|
|
|
|
||
|
Если, кроме того, |
У (ы) сильно выпукла на U, то |
|
|
|||||
|
|
К - « Т < — , « = 1 , 2 , |
|
|
|
|
|||
|
|
|
ш |
|
|
|
|
|
|
где |
х = const> 0 из (1.11). |
|
|
|
|
|
|
||
|
Д о к а з а т е л ь с т в о . Обозначим D = |
sup |и— v |— диаметр мно- |
|||||||
|
|
|
|
и.ибС/ |
|
|
|
4 Ф. П. Васильев
98 |
|
М И Н И М И З А Ц И И Ф У Н К Ц И И МНОГИ Х |
ПЕРЕМЕННЫХ |
|
[ Г л . 2 |
||||||||
жества U. По условию множество U ограничено, поэтому |
оо. |
||||||||||||
Так как J |
(un+i) = gn (ап) < g n (a) = - J (u„ + |
а («„ — и,,)) при |
всех а , |
||||||||||
0 < а < 1 , |
|
то, пользуясь неравенством (1*18)- |
при v = un, |
и = и п + |
|||||||||
■+ а («л — ип), |
получим |
|
|
|
|
|
|
|
|
|
|||
J («я) — J |
(«*+0 > |
|
— “ (/' («„), иа — «„) — у |
L |ип— и„ |2 > |
|||||||||
|
>я|Л>(«„) I---| - L D 2, 0 < а < 1 , |
п = |
0, 1, ... |
(5) |
|||||||||
Отсюда |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
О < |/„(й„) I < |
42- LD2 + |
|
а |
|
|
|
||||
при всех |
а, 0 < а ^ 1 |
и д = 0 , |
1,.... |
Так как /(«,,) не возрастает и |
|||||||||
/(гг„) $ s / * > — оо, то |
|
{/(ип)} |
|
сходится и /(гг„)— /(un+i)-^0 при |
|||||||||
«•-*-оо. Поэтому, переходя в предыдущем |
неравенстве |
к |
пределу |
||||||||||
при л-»-оо, |
будем иметь |
|
|
|
|
|
|
|
|
||||
|
|
|
О < П т |J n(й„) |< |
П т |/„ (йя) |< |
-5- LD2 |
|
|
||||||
|
|
|
П-»оо |
|
|
|
|
|
|
2 |
|
|
|
при всех а , |
0 < а < 1 . |
Отсюда |
при |
ос->~-|-0 |
получим, |
что предел |
|||||||
Нш J n (и„) |
существует и равен |
нулю. |
|
|
|
|
|
|
|||||
П-+оа |
|
|
|
|
|
|
|
|
|
|
|
|
|
Пусть теперь /(и) |
выпукла на U и и* |
— точка минимума J (и) |
|||||||||||
на U. Тогда с помощью неравенства |
(1.9) |
и условия (1) |
получаем |
||||||||||
|
|
О < ап = |
J |
(и„) — J |
(и) < |
(/' (и„), и„ — гг*) = |
|
|
|||||
|
|
|
= — У„(гг*)< — 7„(гг„), /г = |
0, |
1, . . . |
|
(6) |
Это неравенство может служить хорошей апостериорной оценкой
при практическом использовании метода |
(1)— (3). |
|||
Так как |
/ п (ип)-^-0 |
при п-*-оо, то |
из |
(6) имеем J (ип)—*- |
/ (гг*)= / *, |
т. е. {ип} |
— минимизирующая |
последовательность. |
Из непрерывности /(гг) следует, что любая предельная точка по следовательности {гг„} является точкой минимума /(гг) на U. В случае единственности точки минимума гг* вся последователь
ность {ггп}->-гг*. |
_ |
|
|
|
|
|
Докажем оценку (4). Так как /„(ггя)->-0 |
при_/г-»-оо, то |
най |
||||
дется |
число гг0 > 1 ,. такое, что величина а |
— * |
^ |
■ будет |
удов |
|
летворять неравенству 0 < а < Н |
при всех |
/ г> п 0. |
Тогда максималь |
|||
ное |
значение функции а \J п (ип) ) ------у - |
LD- |
переменной а |
при |
§ Я |
Метод условного градибнта |
99 |
— оо < а < оо, которое достигается при а — а., будет совпадать с максимальным значением этой функции на отрезке 0 < а < 1 при всех п > п 0. Поэтому, полагая в оценке (5) а = а , получим
|
О-п |
&п+\ — J |
fan) |
|
J |
{Цп+\) |
|
|J п fan) Р> П > П 0. |
|
|
Отсюда и из |
неравенств (6) |
следует |
|
|
|
|||||
|
|
|
|
a n — |
fl/H-i > |
|
п > п о • |
(7) |
||
Так как а п> |
0 (если а„ = |
0, |
|
то ил — точка минимума), то с помощью |
||||||
леммы 1.2 из |
(7) |
имеем ап< |
|
2LD2 |
1) |
при всех п^>п0. Для |
по- |
|||
|
--------(п0 + |
|||||||||
|
|
|
|
|
|
|
ft |
принять С = шах {2LD2; а0} х |
||
лучения |
оценки |
(4) |
теперь остается |
|||||||
х (по + |
!)• |
|
|
|
2G |
|
|
|
|
|
Оценка I ип— |
|
|
|
п = 1 , 2 , . . . |
для сильно выпуклых |
|||||
|
-----, |
юг
функций является следствием неравенства (1.15) и оценки (4). А
2.Рассмотрим еще один вариант метода условного градиен
когда а,г в (2) выбирается из условия [82]
J |
(«„) — J (ы„ + «„ (ия — «„)) > |
еа„ | (ая) |, 0 < а„ < 1, |
(8) |
где е — |
параметр алгоритма, 0 < & |
< 1 . Ниже будет показано, |
что |
при некоторых ограничениях на функцию такой выбор а„ возмо
жен. |
На практике сначала берут ап = 1 |
и проверяют условие |
(8). |
||||
Если |
оно |
выполнено, |
то оставляют |
ап= 1 . |
Если |
же |
(8) |
при ап= 1 |
не выполнено, |
то производят |
дробление а„ до |
тех |
пор, |
пока не выполнится (8), стараясь при этом остановиться на зна
чении а п, по возможности близком к единице. |
|
|||||
Т е о р е м а |
2. Пусть U — замкнутое ограниченное |
выпуклое |
||||
множество в |
Em> |
J (и) <=С‘ {U) |
и |
[/'(и)— /'(к) |
v\, |
|
и, |
L = const>0. |
Тогда можно построить последовательность |
||||
{««}> |
удовлетворяющую условиям |
(1), |
(2), (8), для которой |
Jn (йя) = (J' (иа), йп — ип) ^ 0 (л-»-оо).
Если, кроме того, /(и) выпукла на U, то последовательность {«„} является минимизирующей и любая ее предельная точка будет точкой минимума /(и) на U, причем в случае единственности точ ки минумума к ней сходится вся последовательность {«„}. Спра ведлива оценка
0 < а п = /(ия) - / * « - 5 - ( л = 1 , 2 , . . . ) , |
(9) |
4: