Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.10.2024
Просмотров: 144
Скачиваний: 0
1.4. КОНУСЫ, ВЫПУКЛЫЕ МНОЖЕСТВА И ВЫПУКЛЫЕ ФУНКЦИИ 27
|
Рассмотрим произвольные точки х ь . . |
|
хт+1 из X и любую |
|||||
их |
выпуклую линейную комбинацию: |
|
|
|
||||
|
|
х = Лрц -{- Я2Х2 • • • -j- ктхт-|- кт+1хт+\, |
|
|||||
|
|
m-f-1 |
|
|
|
|
|
|
где |
к ^ |
0, 2 j ki = |
l. Р1еобходимо |
показать, что х £ Х . |
|
|||
|
|
г=1 |
|
|
|
|
|
|
|
Если |
оказалось, |
что |
A,m+1= l , |
тогда |
х = |
хт+1. По |
условию |
хт+1£Х, |
следовательно, |
в этом случае и х £ Х . |
Если же А,т+1< 1 , |
|||||
то представим х в виде |
|
|
|
|
|
|||
х = ( л 1+ . . . + и ( ^ : ^ - х1 + . . . |
|
|
|
|||||
“Ь ^m+lxm+l — (^ 1 |
• • • ~Ь к т) Z -j- Я т + 1Хт + 1 — |
(1 |
^m+i) 2 Т |
^ т + 1 х т + 1 - |
||||
Так как X выпукло по первому определению, то по индуктивному предположению z £ X. Заметим, что в силу условия 0 ^ ?Lm+1 < 1 имеем 0 < 1 — k m+i ^ 1. Поэтому из выпуклости X по первому определению и принадлежности точек z и хт+1 множеству X сле дует, что х g X. Индукция завершена и эквивалентность опреде лений доказана.
Пример 9. Гиперплоскость сх = |
z есть выпуклое множество; |
||||||
с — заданный |
вектор, z — скаляр, |
х — любая точка |
гиперпло |
||||
скости. |
|
|
|
|
|
|
|
Д оказательство. |
Пусть х( |
и xs - |
произвольные точки гипер |
||||
плоскости, т. е. cxj = |
2 и сх2 = |
2 . Тогда точка х = ^Xj + |
(1 — к) х 2 |
||||
тоже принадлежит гиперплоскости, поскольку |
|
||||||
СХ = |
С [^Xj + (1 — |
х 2] = |
kz |
+ (1 — к) Z = |
Z. |
||
Пример 10. Полупространство сх ^ |
z (или сх < г) есть выпук |
||||||
лое множество, поскольку из сх4 |
и сх'2 ^ 2 следует, что точка |
||||||
х = к х j + |
(1 — к) х 2 принадлежит полупространству сх ^ г, так |
||||||
как |
|
СХ = A,CXj + |
(1 — к) |
с х 2 ^ 2. |
|
||
|
|
|
|||||
Л емма. |
Пересечение выпуклых множеств выпукло. |
|
|||||
Доказательство очевидно. |
|
|
|
|
|||
Точка х выпуклого множества X называется крайней точкой, |
|||||||
если из условия х = kxt + (1 — Я.) х 2 |
и 0 < А, < 1 следует, что |
||||||
либо х = |
Xj = х2, |
либо х 4 ($ X, х 2 $ Х 1). |
|
||||
х) Обычно используется эквивалентное определение: х — крайняя точка выпуклого множества X, если ее нельзя представить в виде линейной выпук лой комбинации двух точек из X .— Прим, ред.
28 |
ГЛ. 1. ОСН ОВНЫ Е п о н я т и я |
Заметим, что крайняя точка выпуклого множества всегда является граничной точкой множества, но обратное неверно.
Рассмотрим систему уравнений
Ах = b (А есть (т X гс)-матрица),
которую можно записать в виде
Э;Х = bt (i = 1, . . ., т),
где ai есть i-я вектор-строка матрицы А. Множество точек, удов летворяющих г-му уравнению, образует гиперплоскость
а;х = bt.
Если все уравнения независимы, то число п — т называется размерностью выпуклого множества {х | Ах = Ь}.
Пусть дано множество Р, не обязательно выпуклое. Для этого множества можно найти выпуклое множество X , содержащее Р,
т. е. х £ Р =#• х £ X.
Выпуклой оболочкой множества Р называется х) пересечение всех выпуклых множеств X t, содержащих Р.
Выпуклая оболочка конечного числа точек называется выпук лым многогранником, натянутым на эти точки. Очевидно, что выпуклый многогранник натянут на свои крайние точки.
Рассмотрим понятие минимума функции / (х). Часто в литера туре под минимумом функции понимается локальный или отно сительный минимум, поскольку сравниваются значения функции лишь в небольшой окрестности. Определим это понятие более точ но: функция / (х) достигает строгого локального минимума в точ
ке х0, если существует е > |
0, такое, что / (х0) |
(х) |
для |
всех х |
||
из e-окрестности |
точки х 0. |
Функция / (х) |
достигает локального |
|||
минимума в точке |
х0, если существует е > |
О, такое, |
что / |
(х0) ^ |
||
^~/(х), для всех |
х из е-окрестности точки х0. |
|
|
|
||
В математическом программировании нас интересует глобаль |
||||||
ный минимум функции, определенной на множестве X , т. е. мы |
||||||
хотим найти такую точку х0, что / (х0) ^ |
/ (х) |
для |
всех |
х £ X. |
||
Поскольку в общем случае локальный и глобальный минимумы функции не совпадают, возможным путем для нахождения гло бального минимума может оказаться сравнение всех локальных минимумов. Вместе с тем, как будет показано, для определенного класса функций, называемых выпуклыми, глобальный минимум функции совпадает с локальным.
!) |
Л егко видеть, |
что это определение |
эквивалентно следующему: |
выпук |
||
лой оболочкой |
множества Р |
называется |
совокупность всевозможных |
точек |
||
|
N |
|
N |
|
|
|
вида |
^ |
гДе |
> 0, 2 |
^г — 1» x i £ P - — П р и м . р ед . |
|
|
|
г—1 |
|
г=1 |
|
|
|
1.4. КОНУСЫ, ВЫПУКЛЫЕ МНОЖЕСТВА II ВЫПУКЛЫЕ ФУНКЦИИ 29
Функция / (х), определенная на выпуклом множестве X , назы вается выпуклой, если
/ [Ах, + (1 - А) х 2] < А/ (Xl) + (1 - X) f (х2) (0 < Я, < 1)
для любых Х(, х2 f X.
Функция / (х), определенная на выпуклом множестве X,
называется |
строго выпуклой, если |
|
|
|||
/ |
[Ах, + |
(1 - |
X) х2] < Xf (х,) |
+ (1 |
- X) f (х2) |
(0 < А < 1) |
для |
любых двух |
различных хь |
х 2 £ X. |
|
||
Заметим, что выпуклая функция всегда определена на выпук |
||||||
лом |
множестве, |
поскольку в невыпуклом множестве точки |
||||
Ах, |
+ (1 — А) х 2 |
может и не быть. Мы получим геометрическое |
||||
представление о выпуклой функции, если представим множество X |
||||||
в виде плоскости, а / (х) — в виде |
поверхности |
над этой пло |
||||
скостью, обладающей тем свойством, |
что отрезок, соединяющий |
|||||
любые две точки этой поверхности, либо расположен над поверх ностью, либо принадлежит поверхности. Для строго выпуклой функции все точки отрезка, кроме концевых, лежат выше поверх ности.
Теорема 1.5. Если / (х) — выпуклая функция, определенная на замкнутом ограниченном выпуклом множестве X, то локальный минимум (строгий или нестрогий) функции / (х) совпадает с гло бальным минимумом функции / (х).
Доказательство. Хотямножество X задается в /г-мерном про странстве; рисунок, иллюстрирующий теорему, для наглядности выполнен в плоскости (рис. 1.4).
Пусть / (х) достигает локального минимума в точке х0, т. е. су
ществует такое е, что / (х) ^ / (х0) для всех х из е-окрестности |
||||
точки х0. |
Допустим, что существует точка х*, такая, что / (х*) < |
|||
< |
/ (х0). |
Все точки |
вида Ах* + (1 — X) х0 (0 ^ X ^ 1) принад |
|
лежат X, поскольку |
X — выпуклое множество. Сделаем X доста |
|||
точно малым, так чтобы |
точка х = Ах* + (1 — А) х0 попадала |
|||
в |
е-окрестность точки х0. |
Для этого необходимо, чтобы 0 ^ А < |
||
< |
е/1 х* — х0 |. По предположению х0 — точка локального мини |
|||
мума, следовательно, |
/ ( х ) ^ / ( х 0), или |
|
|
/( * ) > / (*о) = (1 - |
А) / (х о ) + А/ (х0) > (1 - |
А) / ( х о ) + А/ (х*) |
(1) |
для 0=g;A<-| 8— г . |
|
|
|
I X * — Х0 ) |
|
|
|
Из определения выпуклой функции следует, что |
|
||
/ (х )< А/ (х*) + (1 — А) / (х0) < А/ (х0) + (1 - |
А) / (х0) = / (х0). |
(2) |
|
30 |
ГЛ. 1. ОСНОВНЫЕ п о н я т и я |
Полученное противоречие доказывает теорему. Заметим, что мы не предполагали наличия в точке х* глобального минимума. Мы лишь допустили, что х* — любая точка, где / (х*) < / ( х 0).
Существование глобального минимума в замкнутой ограниченной области гарантируется теоремой Вейерштрасса.и
В противоположность выпуклой, вогнутой функцией называет ся такая функция, определенная на выпуклом множестве, что
/ [Лх, + (1 - X) х2] > Xf (Xl) + (1 — X) f (х2) (0 < X < 1) (3)
для любых Хь Х2 6 X.
Если в данном выше определении нестрогие неравенства заме нить на строгие, то функция будет называться строго вогнутой.
Теоремэ 1.6. |
Если / (х) |
— вогнутая |
функция, |
определенная |
|||||
на выпуклом многограннике J) |
X, то существует крайняя точка |
||||||||
множества X , в которой функция / (х) достигает глобального |
|||||||||
минимума. |
|
|
|
|
|
|
|
|
|
Доказательство. Пусть Vi, |
. . ., v ft |
— крайние |
точки множе |
||||||
ства X. Тогда любая точка х из X является выпуклой линейной |
|||||||||
комбинацией точек Vj, . . ., |
v^: |
|
|
|
|
||||
|
|
|
k |
h |
|
|
|
|
|
|
|
x = ' 2 i X ixi, |
|
2 ^ i = l> |
Xi^iO. |
|
|
||
|
|
i = i |
i= l |
|
|
|
|
||
!) Теорема верпа и в более |
общем случае, когда X — |
выпуклое, огра |
|||||||
ниченное и замкнутое множество. |
Д л я доказательства |
ее |
(в этом случае- |
||||||
надо воспользоваться тем, что а) для каждого |
х 6 X с |
Е п |
можно указат) |
||||||
не более |
п + 1 точек Vi, |
. . ., v n+1 |
из X , выпуклой линейной комбинацией |
||||||
которых |
является |
х; б) |
вогнутая |
функция |
/ (х) непрерывна в точках й |
||||
в) минимум / (х ) достигается на |
X |
.— П р и м . |
р е д . |
|
|
||||