Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 5
Текст из файла (страница 5)
-'-Лтхт-, 'Л „!хтко т-!-! где Л1)О, ~, Л1=-1. Необходимо показатьо что хсХ. =1 ЕСЛИ ОКаааЛОСЬ, ЧтО Лт 1=- 1, тОГда Х == ХтЧ!. ПО УСЛОВИЮ х +!АХ, следовательно, в этом случае и хСХ. Если же Л У1(1, то представим х в внде ! А! 7т х=(Л1+... +~ ) ! Л и х! — ' ... -,'—, х ) + 1 ! т 1 ° ° "; т + Лть1хт1-1 (Л! ! ' ' ' .' Лт) *+ Лт11хть1 — (1 Лт~-1) х + Лгич1хт+1 Так как Х выпукло по первому определению, то по индуктивному предполон!ени!о х С Х. Заметим, что в силу условия О ( Лт+! ( 1 имеем О ( 1 — Л е! ( 1. Поэтому из выпуклости Х по первому определению и принадлежности точек х и х э! множеству Х следует, что х с Х. Индукция завершена и эквивалентность определений доказана.
Пример 9. Гнперплоскость сх = л есть выпуклое мноькество; с — заданный вектор, з — скаляр, х — любая точка гиперплоскости. Доклзлтьльство. Пусть х, и хх — произвольные точки гиперплоскости, т. е. сх, =-зи схз = я. Тогда точках = Лх, + (1 — Л) хэ тоже принадлел!ит гиперплоскости, поскольку сх = с (Лх! + (1 — Л) 1!э] = Лз + (1 — Л) з = г. Пример 10. Полупространство сх ( х (или сх < л) есть выпуклое множество, поскольку из сх! (х и сх, < я следует, что точка х = Лх! + (1 — Л) хч принадлежит полупространству сх ( з, так как сх = Лсх, + (1 — Л) сх, (~ л. Лгммл.
Пересечение выпуклых множеств выпукло. Доказательство очевидно. Точка х выпукчого множества Х называется крайней точкой, если из условия х = Лх, + (1 — Л) хч и О < Л < 1 следует, что либо х = х, =- хч, либо х, !т Х, хэ й Х '). 1) Обычно используется эявпвалеятяос опроделеяие; х — крайняя точка выпуклого мпоя!ества Х, если ес нельзя представить з вице линейной выпуклой комбинации двух точек из Х. — Прим. ред, гл. !. оспояиыв понятия Заметны, что крайняя точка выпуклого множества всегда является граничной точкой миоисества, ко обратное неверно.
Рассмосрим систему уравнений Ах = Ъ (А есть (т х п)-матрица), которую ею!дно записать в виде а,.х =- Ь! (с = 1,..., т), где а; есть с-я вектор-строка матрицы А. Множество точек, удов- летворяющих с-му уравнению, образует гиперплоскость асх=Ь, Коли зсе уравнения независимы, .то число и — т называется размерностью выпуклого множества (х ! Ах = Ъ). Пусть дано мно'кество Р, но обязательно вьспуклое. Для етого множества мопсно найти выпуклое ьсножество Х, содержащее Р, т.
е. хсР=>х~Х. Выпуклой оболочкой множества Р называется !) пересечение всех выпуклых множеств Хо содержащих Р. Выпуклая оболочка конечного числа точек называется выпуклым многогранником, натянутым на зги точки. Очевидно, что выпуклый многогранник натянут на свои крайние точки. Рассмотрим понятие минимума функции р (х). Часто в литературе под минимумом функции понимается локальный или относительный минимум, поскольку сравнивасотся значения функции лишь в небольшой окрестности. Определим зто понятие более точно: функция / (х) достигает строгого локального минимума в точке хе, если существует з ) О, такое, что р (хе) ) р (х) для всех х иэ е-окрестности точки х,.
Функция /(х) достигает локального минимума в точке хе, если существует е > О, такое, что р' (хе) < ( р'(х), для всех х из е-окрестности точки хе. В математическом программировании нас интересует глобальный минимулс функции, определенной на ьшожестве Х, т. е. мы хотим найти такую точку хе, что у (хе) ( р'(х) для всех х ~ Х. Поскольку в общем случае локальный и глобальный минимумы функции но совпадасот, возмовспым путем для нахождения глобального минимума может оказаться сравнение всех локальных миипмумов. Вместе с тем, как будет показано, для определенного класса фуикцпй, называемых выпуклыми, глобальпый минимум функции совпадает с локальным.
!) Легко видеть, по это оиредедекие ехзпеадеитне следующему: выпуклой оболочкой множестве р называется совокупность всевозможных точек Я вида ~~' ь;хо где ьс .ь О, ~~ "в!= с, х! Е Р.— Прим. ред. с=! =1 1 4. КОНУСЫ, ВЫИУКЛ1пг МКО1КЬГТВЛ П З11ПУК;!ЫК ФУПКПИИ зв Функция ! (х), определенная на выпуклом засожестве Х, называется выпуклой, если ~ (Лх1 + (1 — Л) хг) ~ ~Лу (х,) + (1 — Л) 1' (хг) (О ( Л < 1) ° для любых х,, х, ~ Х. Функция 1 (х), опРеделенная на выпуклом множестве Х называется строго выпуклой, если ~ (Лх, + (1 — Л) хг) < Ц (х,) -'; (1 — Л) ! (хг) (О < Л < 1) для любых двух различных х„хг с Х.
Заметим, что выпуклая функция всегда определена па выпуклом множестве, поскольку в невыпуклом множестве точки Лх1+ (1 — Л) хг может и не быть. Мы получим гсомстрическое представление о выпуклой функции, если представим множество Х в виде плоскости, а 1(х) — в виде поворхпости пад атой плоскостью, облада1ощей тем свойством, что отрезок, соединя1ощий любые две точки етой поверхности, либо расположон пал поверхностью, либо припалчсжит поверхпости. Для строго выпуклой функции все точки отрезка, кроме концевых, ложат вышо поверхности.
Твогвмх 1.5. Если ! (х) — выпуклал функция, определенная на замкнутом ограниченном выпуклом множес1пве Х, то локальный минимум (строгий или нестрогий) функции 1 (х) совпадает с глобальным минимумом функции у (х). Докхзхткльство. Хотя множество Х задается з и-мерном пространстве, рисунок, иллюстрирующий теорему, для наглядности выполнен в плоскости (рнс. 1.4).
Пусть ~ (х) достигает локального минимума в точке х,, т. е. существует такое з, что ! (х) ) ~ (х,) для всех х из г-окрестности точки хг. Допустим, что существует точка хе, такая, что 1 (хв) ( (! (х,). Все точки вила Лх*+ (1 — Л) х, (О ( Л ~ (1) припал- лежат Х, посколы1у Х вЂ” выпуклое множество. Влезаем Л достаточно малым, так чтобы точка х = Лхв — ' (1 — Л) хг попадала в з-окрестность точки х,. Для етого необходимо, чтобы О ( Л < ( е!~ хе — хг (. По предположению х, — точка локального мини- мума, следоватольпо, 1(х) ) ! (х,), илп ~(х)= 1(хг)=-(1 — Л)~(хг)--Ц(хг))(1 — Л))(хг) ~ Ц(х') (1) Цг О(Л() * )х* — хг/ Из определения выпуклой функции следует, что /(х)(Л1(х*) 1.
('1 — Л) !(хг) (34(хг)-)-(1 — Л) !(хг) 1(х,) (2) гл. !. осповныв поннтня зо Полученное противоречие доказывает теорему. Заметим, что мы не предполагали наличия в точке х* глобального минимума. Мы лишь допустили, что х* — любая точка, где 1 (х*): / (хе). хе л Р и с. 1.5. Р я с. 1.4 Существование глобального минимума в замкнутой ограниченной области гарантируется теоремой Вейерштрасса. ° В противополоп ность выпуклой, вогнутой функцией называется такая функция, определенная на выпуклом множестве, что 1 Р,х, + (1 — Л) хз] ~ ~Ц (х,) + (1 — Л) 1 (х,) (О ( Л ~ 1) (3) для лгобых х„х, Е Х, Если в данном выше определении нестрогие неравенства заыенить на строгие, то функция будет называться строго вогнутой.
Твогкма 1.6. Если 1' (х) — вогнутая функц я, определенная на выпуклом многограннике ') Х, то существует крайняя точка множества Х, в которой функция 1(х) достигает глобального минимулга. Доказхтвльство. Пусть т!,..., ть — крайние точки ьгножества Х.
Тогда любая точка х из Х является выпуклой линейной! комбинацией точек т„..., ть.' ь ь х=- ~ Л!ты ~.'. Л1=1, Л;= О. г=! 1=1 ') Теорема верна и в болев общем случае, когда Х вЂ” вьгпуклое, огра ннчсппое и замкнутое ьпюжество. Для доказательства ее (в зтом случае- надо воспользоваться тем, что а) для каждого х б Хс-.. Е" можно указат) не более п + 1 точек т„..., т„ь, нз Х, выпуклой лнпещюй комбннацвеь которых является х; б) вогнутая функция ((х) пепрсрывна в точках й в) мвякмум ( (х) достигается на Х.— Прим.
ред. кОнусы, Выпуклые множестВА и Выпуклые Функции З1 Отсюда в силу вогпутости 1(х) получаем г ь А ~(х) = Г ( ~ Х~/к)) г Л;/(У;)) ~ 1Н [ппп ~ (Ур)! = = ш1В ~ (у~) ~~ )л =-. ВВ1 ~ (тр), а 1=! и теорема доказана. ° пп'и ! х — Ь ! = ! а — Ь |, ге с' т. е, а — ближайшая к Ь точка мноягества С'. Рассмотрим гипер- плоскость В, перпендикулярную к вектору Ь вЂ” а.
Уравнение этой гиперплоскости имеот вид (Ь вЂ” а)ту = й, (4) где Й вЂ” константа, а у — точка гиперплоскости. Пусть В проходит через середину отрезка аЬ, т. е. через точку г7г (Ь + а). Тогда из (4) получим (Ъ вЂ” а)ч(Ь-; а) =й, (5ь и уравнопис гиперплоскости примет следующий вид: (Ь вЂ” а) у= — (Ь вЂ” а) (Ь,,'-а). Твогезет 1.7. (О разделяющей гиперплоскостп.) Пусть С— вамкнутог выпуклое множество и Ь вЂ” некоторая точка; тогда либо Ь принадлежит С, либо суи1еспгвугт такая гипгрплоскость Н, чпго Ъ лежит по одну сторону от этой гипврплоскости, о всг точки множества С вЂ” по другую сторону.
(Эта теорема по существу совпадает со слодствием 1.1, по доказывается иначе.) ДОКАзятельство. Определим для любой точки х ~ С фупкци~о расстояния 7 (х) = ! х — Ь !. Эта функция непрерывна на замкнутом множестве С. Если С вЂ” ограниченное множество, то по теореме Вейерштрасса фупкция р (х) достигает минимума в одной из точек С.
Если выпуклое хпюжество С неограниченно, то рассмотрим замкнутый шар В с центром в точке Ь, такой, что В Д С = С' ~ О (рис. 1.5). Поскольку шар В является выпуклым, замкнутым и ограниченным множеством, пересечение В Д С = С' есть также выпуклое, замкнутое и ограниченное множество. Очевидно, функция г (х) достигает минимума на С', Пусть гл. ь оспознгяв понятия 32 Точка Ь лежит в одном из полупрострапств, порождаемых Н: (Ь вЂ” а) Ь- —,(Ь вЂ” а)т (Ь+а). Покажем, что ин одна точка из С не припадлелсит тону же полу- пространству. !1рсдположии противное: пусть существует точка с Е С, расположенная по ту же сторону от Н, что и Ь.
Тогда из условия (7) следует (Ъ вЂ” а) с~ — (Ь вЂ” а)' (Ь+а). (8) гз (Л) = [Ла + (1 — Л) с — ЪР = = (аз+ с' — 2ас) Ла+(2ас — 2сз+ 2Ьс — 2аЬ) Л+(Ь вЂ” с)- = = (а — с)з Лз — 2 (а — с) (Ь вЂ” с) Л + (Ь вЂ” с)з, (9) 4з(Л) = О =~ Л = (а — с) (Ь вЂ” с)/(а — с)'-', .
(10) ~(з (Л) =2(а — )'- О. Таким образом, минимум расстояния от Ь до рассматриваемой (а — с) (Ь вЂ” с) прямой достигается в точке, соответствующей Л вЂ”.. (а — с)з Из соотношения (8) и того, что — (Ь вЂ” а) (Ь+а) — (а Ь вЂ” ас) =- — (Ь' — а' — 2а Ь ' 2ас) = = —,(Ь вЂ” а)') О, 2 т. с, '/з (Ь вЂ” а) (Ь+ а)» а Ь вЂ” а', следуот справедливость нера- венства атЬ вЂ” а' < (Ь вЂ” а)тс (а — с)т(Ъ вЂ” с) < (а — с)'. пли Поскольку с и а принадлежат выпуклому множеству С', любая точка Ла + (1 — Л) с для 0 < Л < 1 также принадлежит С'. По предположению мипимум расстояния между Ъ и л1обой точкой отрезка Ла + (1 — Л) с достигается в точке а, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
