Выпуклые конусы (определения и основные свойства)



Pdf көрінісі
Дата15.10.2018
өлшемі165.1 Kb.

Выпуклые конусы (определения и основные свойства)

Волошинов В.В.

Выпуклый конус является одним из основных объектов,

используемых в теории

оптимизационных моделей. В данном разделе курса даются определения и формулируются

основные свойства выпуклых конусов, которые понадобятся при получении необходимых

условий оптимальности.

Определение D.C.1. Множество KP

R

n

называется конусом если для любого вектора xPK



и числа αą0 αxPK.

Содержание следующего утверждения часто используется как определение выпуклого

конуса.

Утверждение P.C.1. Если конус K является выпуклым множеством, то для любых



двух векторов x

1

, x



2

PK и чисел α

1

, α


2

ě 0 таких, что α

1



2



ą0, то вектор α

1

x



1

2



x

2

принадлежит K.



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

Если одно из чисел α

i

равно нулю, то утверждение следует из



определения C.1. В случае, когда оба коэффициента положительны, доказательство следует

из следующего соотношения:

α

1

x



1

2



x

2

“ pα



1

2



q

ˆ

α



1

α

1



2

x



1

`

α



2

α

1



2

x



2

˙

Вектор, стоящий справа принадлежит K по следующим причинам: 1) α



1

i

.



α

i



α

1



2

ą 0 pi“1, 2q

и α

1

1



1

2



“1; 2) α

1

i



x

i

P K pi “ 1, 2q по определению C.1. Осталось воспользоваться выпуклостью



K и определением C.1.

b

В теории задач оптимизации важное значение имеют конечно-порожденные и конечно-



гранные (полиэдральные) конуса.

Определение D.C.2. Пусть ta

i

u

iPI



Ă

R

n



, |I|ă8 конечный набор векторов. Тогда

конечно-порожденным конусом является множество

Conepta

i

u



iPI

q

.



"

x “



ř

iPI


α

i

a



i

, α


i

ě0

*



(C.1)

(“порожден” набором векторов a

i

).

Конечно-гранным (полиэдральным) конусом является множество



Hpta

i

u



iPI

q

.



“ tx : a

i



x ě 0 @iPIu

(C.2)


(вектора a

i

- нормали граней конуса)



Очень часто, например, в книге [3], оба типа конусов называют полиэдральными, т.к.

конечно-порожденный допускает “конечно-гранное” представление и, наоборот, конечно-

гранный “порождается” некоторым конечным набором векторов.

В теории оптимизации и выпуклом анализе важную роль играет понятие сопряженного

конуса.

Определение D.C.3. Пусть K конус в



R

n

. Конусом, сопряженным к K, называют



множество

K

˚



.

“ tx


˚

P

R



n

:

⟨x



˚

, x


⟩ ě 0 @xPK.u

Перечислим основные свойства сопряженных конусов.

1


2

Утверждение P.C.2. Для любого конуса K, сопряженный конус K

˚

является замкнутым



и выпуклым конусом

Доказательство. Следует непосредственно из определений.

b

Утверждение P.C.3. Пусть конус K



1

является подмножеством конуса K

2

, K


1

ĎK

2



. Тогда

K

˚



2

ĎK

˚



1

(“обратное” включение для сопряженных конусов).

Доказательство. Следует непосредственно из определений.

b

Определение D.C.4. Множество всех предельных точек произвольного множества M P



R

n

называется замыканием M и обозначается Ď



M .

Заметим, что по определению, M Ă Ď

M для любого M.

Утверждение P.C.4. Для любого конуса K, сопряженный к нему конус совпадает с

конусом, сопряженным к замыканию K, K

˚



`

s

K



˘

˚

.



Доказательство. Проверим, что s

K тоже конус. Пусть ˜

xP s

K, т.е. ˜



x“ lim

kÑ8


x

k

, где x



k

PK.


Тогда, очевидно, что @αą0 α˜

x“ lim


kÑ8

αx

k



. Но, т.к. K конус, то αx

k

PK для всех k“1, 2, . . . . Но



это означает, что α˜

xP s


K.

Из очевидного включения KĎ s

K и утверждения P.C.3 следует, что

`

s



K

˘

˚



ĎK

˚

. Проверим,



что на самом деле имеет место равенство

`

s



K

˘

˚



“K

˚

. Рассмотрим произвольный вектор x



˚

PK

˚



,

тогда @xP s

K существует последовательность tx

k

u



8

k“1


ĂK такая, что lim

kÑ8


x

k

“x. Т.к.



x

k

PK,



то

⟨x

˚



, x

k

⟩ě0. Поэтому ⟨x



˚

, x


⟩“ lim

kÑ8


⟨x

˚

, x



k

⟩ ě 0. Последнее неравенство выполнено для любых

x

˚

PK



˚

, xP s


K, т.е. x

˚

P



`

s

K



˘

˚

. Утверждение доказано.



b

Конус, сопряженный к сопряженному, принято называть дважды сопряженным конусом и

обозначать K

˚˚

или pK



˚

q

˚



:

pK

˚



q

˚

.



“ txP

R

n



:

⟨x, x


˚

⟩ ě 0 @x


˚

PK

˚



.u

(C.3)


Следующее утверждение заслуживает того, чтобы считать его теоремой.

Теорема T.C.1. Если K выпуклый конус в

R

n

, то pK



˚

q

˚



“ s

K (дважды сопряженный

является замыканием исходного конуса).

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

Вначале проверим, что s

KĎ pK


˚

q

˚



. Пусть xP s

K, т.е. x“ lim

kÑ8

x

k



для

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

k

u

8



k“1

ĂK. Тогда

@x

˚

PK



˚

ñ

⟨x



˚

, x


k

⟩ě0 @x


k

PK ñ lim


kÑ8

⟨x

˚



, x

k

⟩ “ ⟨x



˚

, x


⟩ ě 0,

т.е. xP s

K ñ xP pK

˚

q



˚

. Проверим, что не может быть строгого включения s

KĂ pK

˚

q



˚

.

Рассмотрим произвольный вектор ˜



xR s

K. Покажем, что ˜

xR pK

˚

q



˚

, используя теорему о

строгой отделимости замкнутого выпуклого множество s

K и не принадлежащей ему точки

˜

x. По этой теореме существует вектор ˜



x

˚

и число εą0 такие, что



@xP s

K

⟨˜x



˚

, x


⟩ ě ⟨˜x

˚

, ˜



x

⟩ ` ε


(C.4)

Покажем, что из (C.4) следует ˜

x

˚

PK



˚

. Действительно, значения

⟨˜x

˚

, x



⟩ ограничены снизу

для всех точек из конуса s

K, содержащего (по определению замыкания) конус K. Если для

некоторого x

o

PK

⟨˜x



˚

, x


o

⟩ă0, то при αÑ`8, α¨x

o

PK и значения



⟨˜x

˚

, α¨x



o

⟩ будут неограниченно

стремиться к ´8, что противоречит (C.4).

Далее, поскольку нулевой вектор 0 принадлежит s

K (замыканию конуса), то полагая в (C.4)

x“0 получим

⟨˜x

˚

, ˜



x

⟩ă0. Т.к. ˜x

˚

PK

˚



, то последнее строгое неравенство влечет ˜

xR pK


˚

q

˚



.

Итак, мы убедились, что ˜

xR s

Kñ˜


xR pK

˚

q



˚

, т.е. s


KĚ pK

˚

q



˚

, что вместе с ранее установленным

обратным включением s

KĎ pK


˚

q

˚



доказывает теорему.

b

Следующие



утверждения

устанавливают

основные

правила


вычисления

конусов,


сопряженных к пересечению и сумме конусов.

3

Определение D.C.5. Суммой Минковского (далее просто - суммой) двух множеств M

1

и M


2

из векторного пространства

R

n

называется множество всевозможных сумм x



1

`x

2



, где x

i

PM



i

:

M



1

‘M

2



.

“ tx


1

`x

2



: x

1

PM



1

, x


2

PM

2



u .

Теорема T.C.2. (о сопряженном к сумме) Для любых двух конусов K

1

, K


2

из

R



n

верно


равенство pK

1

‘K



2

q

˚



“ K

˚

1



ŞK

˚

2



.

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

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

следует


непосредственно

из

определений.



Действительно, если x

˚

PK



˚

1

ŞK



˚

2

, то



⟨x

˚

, x



i

⟩ě0 @x


i

PK

i



pi“1, 2q. Поэтому,

⟨x

˚



, x

⟩“⟨x


˚

, x


1

`x

2



⟩ě0

@xPK


1

‘K

2



, т.е. K

˚

1



ŞK

˚

2



Ă pK

1

‘K



2

q

˚



.

Обратно, если x

˚

P pK


1

‘K

2



q

˚

, то



⟨x

˚

, x



1

`x

2



⟩ě0 @x

i

PK



i

pi“1, 2q. Т.к. каждый из векторов

x

i

PK



i

можно выбрать сколь угодно близким нулю (умножая на число εą0, εÑ0), то из

последнего неравенства следует, что

⟨x

˚



, x

i

⟩ě0 @x



i

PK

i



pi“1, 2q, т.е. x

˚

PK



˚

i

pi“1, 2q. ‘Значит



x

˚

PK



˚

1

ŞK



˚

2

и мы получаем обратное включение pK



1

‘K

2



q

˚

ĂK



˚

1

ŞK



˚

2

.



Заметим, что непосредственно из определений, для любых двух конусов K

1

, K



2

из

R



n

, легко


установить (нестрогое) включение

K

˚



1

‘K

˚



2

Ď pK


1

ŞK

2



q

˚

(C.5)



Для получения необходимых условий оптимальности нужны условия, обеспечивающие

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

требуется, но общее свойство выпуклых замкнутых конусов.

Теорема T.C.3. (общий вид конуса, сопряженного к пересечению конусов) Для

любых двух выпуклых замкнутых конусов K

1

, K



2

из

R



n

верно равенство

pK

1

ŞK



2

q

˚



“ pK

˚

1



‘K

˚

2



q

(C.6)


(справа - замыкание суммы сопряженных конусов)

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

Поскольку K

i

замкнутый выпуклый конус, то, по теореме T.C.1, -



K

i

“Ď



K

i

“ pK



˚

i

q



˚

. Поэтому, применяя теорему T.C.2 к паре конусов K

˚

1

и K



˚

2

, получим



K

1

ŞK



2

“ pK


˚

1

q



˚

Ş pK


˚

2

q



˚

“ pK


˚

1

‘K



˚

2

q



˚

.

Далее, применяя теорему T.C.1 к конусу pK



˚

1

‘K



˚

2

q



˚

, из последнего равенства получаем

требуемое

pK

1



ŞK

2

q



˚

`



pK

˚

1



‘K

˚

2



q

˚

˘



˚

“ K


˚

1

‘K



˚

2

.



Теорема доказана.

b

Обсудим немного эту очень важную теорему.



Приведем пример, показывающий, что предположение о замкнутости конусов K

1

и K



2

существенно. Рассмотрим два конуса на плоскости

R

2

:



K

1

.



“ tpx

1

, x



2

q : x


1

ě0, x


2

ě0u , K


2

.

“ tpx



1

, x


2

q : x


1

ă0, x


2

ě0u


Ť tp0, 0qu

K

2



здесь является выпуклым незамкнутым конусом. Легко проверить, что

K

˚



1

“ K


1

, K


˚

2

“ tpx



˚

1

, x



˚

2

q : x



˚

1

ď0, x



˚

2

ě0u .



В этом примере K

1

ŞK



2

“ tp0, 0qu пересечение конусов совпадает с нулевым вектором

(началом координат), “сопряженным” к любому вектору из

R

2



, поэтому pK

1

ŞK



2

q

˚



R

2



. C

другой стороны сумма конусов K

˚

1

‘K



˚

2

“ tpx



1

, x


2

q : x


2

ě0u есть полупространство в

R

2

и, в



данном примере, (C.5) выполнено как строгое включение.

Для практического применения формулы (C.6) важен случай, когда можно гарантировать

замкнутость векторной суммы сопряженных конусов. В этом случае замыкания суммы не

требуется и вычисление сопряженного (к пересечению) конуса упрощается. Проблема в том,

что несмотря на замкнутость (см. утверждение P.C.2) “складываемых” конусов K

˚

1



, K

˚

2



их

сумма может быть незамкнутым множеством уже в трехмерном пространстве

R

3

.



4

Для примера рассмотрим

K

1

.



px, y, zq : y



2

ďz¨x, xě0

( ,

K

2



.

“ tpx, y, zq : xď0, y“z“0u “ Cone

$



&



%

¨



˚

˝

´1



0

0

˛



,



/

.

/



-

Оба указанных конуса замкнуты, но их сумма - нет (ниже символ “z” означает теоретико-

множественную разность: AzB

.

“ tx : xPA & x R Bu ):



K

1

‘K



2

“ tpx, y, zq : zě0u z tpx, y, zq : y‰0, z“0u

(Попробуйте доказать, что в

R

2



сумма любых двух выпуклых замкнутых

конусов является замкнутой)

Для исключения подобных аномальных ситуаций принято, либо делать дополнительные

предположения,

гарантирующие замкнутость суммы сопряженных конусов (например,

условия Слейтера), либо рассматривать класс конусов, сумма которых всегда замкнута.

Примером второго подхода является класс оптимизационных моделей порождающих

полиэдральные конуса.

(Попробуйте доказать, что сумма любых двух конечно-порожденных конусов

всегда замкнута.)

Теорема T.C.4. (достаточное условие замкнутости суммы сопряженных “типа

условия Слейтера”) Пусть конуса K

1

, K


2

из

R



n

нельзя отделить друг от друга ненулевым

линейным функционалом (см.

материал про теоремы отделимости).

Тогда K

˚

1



‘K

˚

2



-

замкнут.


Доказательство. Покажем, что если множество K

˚

1



‘K

˚

2



не замкнуто, то найдется ненулевой

вектор z


˚

P

R



n

, z


˚

‰0, такой что

⟨z

˚

, x



1

⟩ ě ⟨z


˚

, x


2

⟩ @x


i

PK

i



pi“1, 2q.

(C.7)


Нетрудно проверить (устремляя поочередно x

i

pi“1, 2q к нулю “вдоль” соответствующего



конуса K

i

), что выполнение (C.7) эквивалентно тому, что



DzP

R

n



, z‰0 такой, что z

˚

PK



˚

1

, ´z



˚

PK

˚



2

.

(C.8)



Итак, пусть K

˚

1



‘K

˚

2



не замкнуто, т.е.

существует последовательность tx

˚

k

u ĂK



˚

1

‘K



˚

2

,



сходящаяся к вектору

r

x



˚

, не принадлежащему векторной сумме K

˚

1

‘K



˚

2

:



x

˚

k



“x

˚

1k



`x

˚

2k



, x

˚

ik



PK

˚

i



pk “ 1, 2, . . .q, lim

kÑ8


x

˚

k



r

x



˚

,

r



x

˚

RK



˚

1

‘K



˚

2

.



(C.9)

Вначале, покажем, что обе последовательности tx

˚

ik

u неограниченны.



Действительно,

если,


например,

tx

˚



1k

u

ограничена,



то

из

неё



можно

выделить


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

␣x

˚



1k

1

(



Ă tx

˚

1k



u ,

сходящуюся

к

некоторой



точке

r

x



˚

1

.



Благодаря

замкнутости K

˚

1

,



r

x

˚



1

PK

˚



1

. Далее, из (C.9) следует сходимость подпоследовательности

␣x

˚

2k



1

( :


lim

k

1



Ñ8

x

˚



2k

1



r

x

˚



2

.



r

x

˚



´

r

x



˚

1

. Благодаря замкнутости K



˚

2

,



r

x

˚



2

PK

˚



2

. В итоге мы получили, что вектор

r

x

˚



может быть представлен в виде суммы векторов из K

˚

1



и K

˚

2



:

r

x



˚

1

`



r

x

˚



2

r



x

˚

1



` p

r

x



˚

´

r



x

˚

1



q “

r

x



˚

, где


r

x

˚



i

PK

˚



i

. Но это противоречит последнему “невключению” (C.9).

Итак, переходя если надо к подпоследовательности, без o.o. (ограничения общности) можно

считать, что }x

˚

1k

} ÝÝÝÑ



kÑ8

`8. Но в этом случае, из существования предела в (C.9) получим:

lim

kÑ8


ˆ

x

˚



1k

}x

˚



1k

}

`



x

˚

2k



}x

˚

1k



}

˙

“ lim



kÑ8

x

˚



k

}x

˚



1k

}

“ 0



(C.10)

Положим, z

˚

ik

.



x

˚



ik

}x

˚



1k

}

pi“1, 2q. Т.к.



вектора x

˚

i



принадлежат конусам K

˚

i



, то z

˚

ik



PK

˚

i



. По

построению, }z

˚

1k

}“1, поэтому (еще раз переходя если нужно к подпоследовательности) без



5

о.о. можно считать, что z

˚

1k

сходится к некоторому



r

z

˚



PK

˚

1



, }

r

z



˚

}“1. Из (C.10) следует, что

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

˚

2k



сходится к ´

r

z



˚

PK

˚



2

, т.е. мы убедились в существовании вектора,

удовлетворяющего (C.8). Но это противоречит предположению о “неразделимости” конусов

K

˚



1

и K


˚

2

. Теорема доказана.



b

Типичным примером применения теорем T.C.3 и T.C.4 является следующее утверждение.

Утверждение P.C.5. Пусть один из двух конусов K

1

и K



2

имеет внутренние точки,

intK

1



∅ и intK

1

ŞK



2

∅. Тогда pK



1

ŞK

2



q

˚

“ K



˚

1

‘K



˚

2

.



Еще одним примером использования тех же теорем является

Утверждение P.C.6. Сопряженным

к

полиэдральному



конусу

Hpta


i

u

iPI



q

(см.


определение (C.2)) является конечно-порожденный конус Conepta

i

u



iPI

q вида (C.1).

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

Рассмотрим

вначале

“простейший”



полиэдральный

конус


Hpaq

.

“ tx :



⟨a, x⟩ě0u (полупространство). Проверим, что сопряженным к нему является

луч Conepaq

.

“ tt¨a : tě0u (это кажется очевидным, но все же...).



Нестрогое включение Conepaq Ď pHpaqq

˚

следует из определений. Допустим, что существует



вектор x

˚

P pHpaqq



˚

zConepaq . Поскольку вектор x

˚

не принадлежит замкнутому выпуклому



множеству Conepaq , то по теореме отделимости их можно строго отделить некоторым

линейным функционалом ℓpxq

.





r

x, x


⟩, т.е.

r



x, t¨a

⟩ “ ℓ pt¨aq ą ℓpx

˚

q “


r

x, x



˚

⟩ @tě0.


(C.11)

Из (C.11) следует, что

r

x, a



⟩ě0 (иначе, выбирая достаточно большое положительное значение

t, левая часть неравенства станет меньше правой), т.е.

r

xPHpaq . Но, полагая t“0, мы



получим

r



x, x

˚

⟩ă0, что противоречит (по определению сопряженного конуса) предположению



x

˚

P pHpaqq



˚

. Полученное противоречие доказывает равенство

pHpaqq

˚

“ Conepaq .



(C.12)

Основную часть доказательств проведем по индукции по числу элементов в множестве

I (без о.о.

удобно считать, что I“ t1, 2, . . ., |I|u).

Равенство (C.12) есть “база индукции”.

Допустим, что теорема верна для I из n элементов, т.е.

H

´

ta



i

u

i“1,2,...,n



¯

“ Cone


´

ta

i



u

i“1,2,...,n

¯

.

(C.13)



Пусть |I|“n`1. Заметим, что, по определению полиэдрального конуса,

H

´



ta

i

u



i“1,2,...,n`1

¯

“ H



´

ta

i



u

i“1,2,...,n

¯

ŞHpa


n`1

q

По теореме T.C.3 (об общем виде сопряженного к пересечению) из последнего выражения



получаем

´

H



´

ta

i



u

i“1,2,...,n`1

¯¯

˚



´´

H

´



ta

i

u



i“1,2,...,n

¯¯

˚



‘ pHpa

n`1


qq

˚

¯



,

что, с учетом (C.12) и (C.13) можно записать в виде

´

H

´



ta

i

u



i“1,2,...,n`1

¯¯

˚



“ Cone

´

ta



i

u

i“1,2,...,n



¯

‘Conepa


n`1

q,

По определению конечно-порожденного конуса, правая часть последнего равенства есть



замыкание конуса Cone

´

ta



i

u

i“1,2,...,n`1



¯

, но этот конус является замкнутым (см. упражнение

выше). Поэтому

H

´



ta

i

u



i“1,2,...,n`1

¯

“ Cone



´

ta

i



u

i“1,2,...,n`1

¯

Теорема доказана.



b

В качестве еще одного несложного упражнения докажите

Утверждение P.C.7. Сопряженным

к

конечно-порожденному



конусу

Conepta


i

u

iPI



q

является полиэдральный конус Hpta

i

u

iPI



q .

6

Список литературы

[1] Мину М. Математическое программирование. Теория и алгоритмы: Пер. с французского.

- М. Наука. Гл. ред. физ.-мат. лит., 1990. - 488 c.

[2] Поляк Б.Т. Введение в оптимизацию. - М. Наука. Гл. ред. физ.-мат. лит., 1983. - 384 c.

[3] Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. - М.:

Наука. Главная

редакция физико-математической литературы, 1980. - 320 с.





Достарыңызбен бөлісу:


©stom.tilimen.org 2019
әкімшілігінің қараңыз

    Басты бет