Конус. Теорема Фаркаша - Минковского

Определение 3.6. Множество КÌ Е_n называется конусом, если из справедливости хÎ К следует справедливость lхÎ К для любого l> 0.

К₁ Определение 3.7. Выпуклым конусом называется конус, который одновременно

K₂ является выпуклым множеством. На рисунке 3.8. множества К₁ и К₂ являются выпуклыми конусами. Однако К₁ È К₂ хотя и является конусом, но уже не являетсявыпуклым.

Рис. 3.8. Определение 3.8. Пусть К –выпуклый конус, тогда множество К^*={y / < x, y> ³ 0, " xÎ K, yÎ E_n} называется сопряженным конусом.

А В Геометрически это определение означает,

А' К что угол между любыми векторами xÎ K и

К^* В ' уÎ K^* не превосходит p/2. На рисунке 3.9 К состоит из векторов угла Ð АОВ, К^*

О состоит из векторов угла Ð А'ОВ'. Из

Рис. 3.9. рисунка видно, что Ð А'ОВ=Ð АОВ' = p /2.

Лемма 3.1. Сопряженный конус является замкнутым выпуклым конусом.

Доказательство. Пусть у Î K^*, l > 0, тогда для любого х Î K выполняется < х, у> ³ 0, откуда < х, lу> ³ 0, следовательно lу Î K^* и aÎ [0, 1]. Для любогох Î K< х, у> ³ 0, < х, z> ³ 0, поэтому< х, (1-a)y + az > ³ 0, откуда следует выпуклость K^*. Остается доказать, что K^* замкнутое множество. Пусть у – предельная точка множества K^*, тогда в K^* существует последовательность {y_k}, для которой y_k у. Для членов этой последовательности< y_k, х> ³ 0 для любого хÎ K, т. е. Î K^*. Таким образом, лемма доказана.

Лемма 3.2. Если К – выпуклый конус, то К^* =( )^*.

Доказательство. Пусть К= , тогда, если у Î ()^*(т. е. < х, у> ³ 0, " х Î ), то < х, у> ³ 0, " х Î К, т. е. уÎ К ^*.Откуда следует, что ( )^*.Ì.К^*.

Покажем справедливость обратного включения.

Пусть уÎ К ^*, или < х, у> ³ 0, " х Î К. Так как предельный переход не меняет знака неравенства, то < х, у> ³ 0 будет справедливо и для всех х Î , откуда следует, что уÎ К ^* и, следовательно. К^*Ì.( )^*. Оба включения дают утверждение леммы.

Геометрическая иллюстрация двойственных конусов дает возможность предполагать, что двойственный к двойственному конусу есть исходный. Этот факт доказывает следующая теорема двойственности.

Теорема 3.11. (Теорема двойственности). Пусть К выпуклый конус, тогда (К^*)^*= .

Доказательство. Пусть хÎ , тогда для любого уÎ К ^*< х, у> ³ 0, По определению (К^*)^*={z / < z, y> ³ 0, " yÎ K^*. Тогда хÎ (К ^*)^*, следовательно Ì (К^*)^*

Докажем, что (К^*)*\ =Æ, откуда и будет следовать утверждение теоремы. Предположим противное, т. е. (К^*)*\ ¹ Æ и существует vÎ. (К^*)* \ . По теореме отделимости 3.7 и следующему за ней замечанию существует вектор С¹ 0_n такой, что для всех хÎ справедливо < c, x> < < c, v>;.

Положим С' = -С, тогда для всех хÎ выполняется неравенство

< c^’, x> < < c^’, v>. (3.31)

Подставим х=0_nÎ в это неравенство, получим < c^’, v> < 0.

Так как vÎ. (К^*)*, тоиз предыдущего неравенства следует, что С' Ï К^*.

C другой стороны, если хÎ , то lх Î К для любого l > 0, поэтому в (3.31) х можно заменить на lх, тогда получим

l < c^’, x> > < c^’, v> для " l > 0, хÎ .

Это возможно лишь в том случае, когда < c^’, x> > 0 для всякого хÎ , но тогда с' Î К^*. Полученное противоречие показывает несправедливость предположения, но тогда (К^*)^*= .

Следствие 3.3. Если К замкнутый конус, то (К^*)^*= К.

Определение 3.9. Пусть а_i (i= ) векторы из пространства Е_n. Многогранным конусом К будем называть множество вида

К={х / x= l_i а_i , l_i³ 0, (i= , хÎ Е_n },

Обозначим А=(а₁, а₂, …, а_m), l=(l₁, l_2, …, l _m).^т, тогда для конуса К можно записать К={x/x=Al, l_i³ 0_m, хÎ Е_n }.

На рисунке 3.10 приведен пример многогранного конуса К. Он состоит из всех векторов, лежащих между векторами а₁ и а₃. Вектор х можно представить в виде

х= l₁а₁+0а₂+ l₃а₃, где l_i, l₃³ 0.

. а₃

l₃ а₂ х

а₁

Рис.3.10

Лемма 3.3. Многогранный конус является выпуклым конусом.

Доказательство. Надо доказать, что К конус и что К выпуклое множество. Действительно, если х Î К, т. е. x= l_i а_i , l_i³ 0, i= , l x= ll_i а_i, где l l_i³ 0, i= при l> 0/

Следовательно, lх Î К, К – конус. Пусть х, у Î К, a Î [0, 1 ], тогда

x= l_i а_i , l_i³ 0, у = l’_i а_i , l’_i ³ 0, i= ,

z=(1-a)х +ay = ((1-a)l_i+al_i) а_i , где (1-a)l_i+al_i³ 0, i= , Таким образом, zÎ К, т. е. К- выпуклый конус.

Вектор хÎ К может иметь не единственное представление через а_i , i= Так на рисунке 3.10 вектор х выражен через а₁ и а₃ Его можно также выразить через а₁ и а₂. Число таких представлений может быть сколь угодно велико. Из этого множества представлений выделим следующие.

Лемма 3.4. Для любой точки х Î К, К - многогранный конус, существует её представление через систему линейно независимых векторов а_i, i Î w, т.е.

x= l_i а_i , (3.32)

где w = {I / i= 1, 2,..., m, l_i³ 0}. Если а_i, i Î w - система линейно независимых векторов, то получим требуемое. Иначе найдутся такие a_i, i Î w, не все равные нулю, что 0_m= l_i а_i , (3.33)

Умножая равенство (3.33) на р ³ 0 и складывая с разложением (3.32), получим x= ( l_i + рa_i)а_i , (3.34)

Не ограничивая общности можно считать, что среди a_i есть отрицательные числа. Если их нет, то в разложении (3.33) знаки a_i можно поменять на противоположные. Начнем увеличивать значение р от 0 до момента, когда некоторые l_i + рa_i обратятся в 0. Это произойдет при p= min (-l_i/a_i), i Î w, a_i< 0. Удаляем из w все те i, для которых l_i + рa_i =0.

Таким образом, число элементов в разложении вектора х (3.32), уменьшилось по крайней мере на 1. Если векторы а_i , i Î w вновь линейно зависимы, то описанную процедуру сокращения числа элементов повторяем. В силу конечности m придем к разложению вектора х по системе линейно независимых векторов.

Следствие 3.4. Пусть W ={ w }-множество всех таких подмножеств wÌ {1, 2, …, m}, что система векторов а_i, i Î w, линейно независима, тогда К = È К(w), где

wÎ W

К(w) = { x / x= l_i а_i}.

Лемма 3.5. Пусть система векторов а_i , i Î w, линейно независима, тогда конус К(w) замкнут.

Доказательство. Обозначим Аw = (а_i), i Î w, т.е. Аw матрица, столбцами которой являются векторы а_i , i Î w.

Пусть х_k Î К(w), тогда х_k = Аw l_k , где вектор l_k в этомразложении единственный. Умножая обе части этого выражения слева на А^Тw , получим

А^Тw х_k = А^Тw Аw l_k (3.35)

Так как А^Тw Аw не вырождена, то

l_k = (А^Тw Аw) ^-1 А^Тw х_k (3.36)

Если х_k , то l_k впредыдущем равенстве стремится к

= (А^Тw Аw) ^-1 А^Тw (3.37)

Значит =Аw и, следовательно, Î К(w). Лемма доказана.

Теорема 3.12. Многогранный конус К является замкнутым выпуклым конусом.

Доказательство. По лемме 3.3. конус есть выпуклый конус. Так как объединение конечного числа замкнутых множеств есть множество замкнутое, то из следствия 3.4 и леммы 3.5. получаем, что К также замкнутое множество.

Теорема 3 13. (Фаркаша – Минковского). Пусть конус К={х / хÎ Е_n, A^Tх³ 0_n }, тогда сопряженный конус К^* равен = {у / уÎ Е_n , у=Al, l ³ 0_n, }

Доказательство. По теореме 3.12 замкнутый выпуклый конус. Сопряженный к нему конус имеет вид:

^* = { x/xÎ E_n, < x, Al > ³ 0, " l ³ 0_m } =

= { x/xÎ E_n, < A^T x, l> ³ 0, " l ³ 0_m } ( 3.38)

В силу произвольности l³ 0_m , получаем

^* = { x/xÎ E_n, A^T x³ 0} = К.

Применяя теорему 3.11 получаем ^* = ^** = . Что и требовалось доказать.

Следствие 3.6. Пусть х, bÎ Е_n, uÎ Е_m, B – матрица размерности m × n. Если < b, x> ³ 0 для всех х, удовлетворяющих системе Bх³ 0_m, то система B^Tu=b разрешима при u ³ 0_m.

Доказательство. Положим в теореме 3.13 A^T=В, тогда получаем, что < b, x> ³ 0 для всех хÎ К, т. е. bÎ K^*.

B = Au = B^Tu.

Следствие 3.7. Для любой матрицы B и любого вектора v имеет место следующая альтернатива:

либо имеет решение система (3.39)

Bx ³ 0_m

< b, x> < 0, (3.39)

либо имеет неотрицательное решение система (3.40)

B^Tu=b

u ³ 0 (3.40)

Доказательство. Также, как и выше, положим А^Т = В. Из первой системы следует, что bÏ K*, т.е. не может быть представлено в виде b=B^Tu, u ³ 0_m. И наоборот, если система B^Tu=b разрешима при u ³ 0_m, то bÎ K^*, но тогда < b, x> ³ 0для любого хÎ К, но тогда первая система не разрешима.