Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

ВОЕНЫ АЛЛАХА1АЗАЗАЗАЗ / 10_Конусы_опорных_векторов_сент_9_2008

.pdf
Скачиваний:
27
Добавлен:
10.02.2015
Размер:
394.07 Кб
Скачать

О.А. Кашина, А.И. Кораблев

10. Конусы опорных векторов

Ранее в

параграфе 8 было

введено

множе-

ство T x

 

g : g En , g, y x

 

 

 

0, y D

векто-

ров, опорных в точке Изучим свойства этих

x

ко множеству

множеств.

D

E

n

 

.

 

Теорема 1.

 

В

 

любой точке

x E

n

 

множе-

 

 

 

 

 

 

ство

T x

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

кону-

сом.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

Пусть

g, q T x

,

t 0 ,

u 0 .

Для

любого

y D

имеем

g, y x 0

и

q, y x 0,

а

значит,

tg uq, y x 0

,

 

то

есть

t g u q T x .

Итак,

T x – выпуклый

 

 

конус.

 

 

Проверим

его

замкнутость.

Пусть

 

g

пре-

дельная точка

конуса

T x .

Это

означает, что

существует

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

gk

 

 

 

T x

 

 

 

 

 

 

 

 

 

 

 

 

k 1,2,...

 

 

 

 

такая,

что

lim g

k

g .

Для любой

точки

y D

 

 

k

 

 

 

 

 

 

 

 

 

 

 

 

 

 

справедливы

неравенства

gk , y x

0, k 1,2,...

 

Следовательно,

lim

gk , y x

g, y x 0,

то есть

 

 

 

k

 

 

 

 

 

 

 

 

 

 

x .

 

g T (x) . Что и

означает

замкнутость

 

T

 

Легко увидеть, что справедливо следующее утверждение.

Теорема 2. Пусть B и D – множества из En ,

52

B

D

. Тогда

T x, D T

x,

B

Методы оптимизации: Часть I

.

Следующая теорема непосредственно вытекает из теорем 2 и 1.

 

Теорема 3.

 

m

Тогда

T x, Di

 

i 1

Пусть DiT x, D

n

, i 1, ...,

E

.

 

m

,

D

m

 

 

D

 

i 1

i

 

 

.

Задача построения конуса векторов опорных для данного множества в данной точке, вообще говоря, является достаточно сложной. Не существует явных формул или конечных алгоритмов, решающих эту задачу в общем случае. Однако для некоторых классов множеств эта задача решается сравнительно просто. Рассмотрим далее несколько случаев таких множеств, которые нам потребуются в дальнейшем.

Теорема 4. Пусть

D y : y E

,

n

 

f

y

0

,

где функция f определена, является выпуклой и

непрерывно

 

дифференцируемой

на

E n ,

точка x

такова,

 

что f x 0 .

Тогда

f x T x .

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

точка

y D , то есть

f y 0 .

Учитывая, что

по

условиям

f x 0 ,

имеем

f

y f x 0 .

Отсюда

и

из теоремы 4.1

следует

 

f

 

x , y x 0. Что

 

и

требовалось.

 

 

 

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

53

О.А. Кашина, А.И. Кораблев

ванных системами выпуклых неравенств. Нам понадобится следующее условие.

Условие Слейтера.

функции

fi

,

i 1, ..., m

неравенств

 

fi x 0, i

Пусть на

. Говорят,

1, ..., m ,

E

n

определены

 

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

условию

Слейтера

относительно

некоторого

множества

B из

E n ,

если

существует точка

z B

такая,

что

fi z 0

для всех

i 1, ..., m.

 

Если

данная

система

неравенств

удовлетво-

ряет

условию Слейтера относительно

B E

n

, то

 

будем просто говорить,

что

она удовлетворяет

условию Слейтера.

 

 

 

Для системы выпуклых неравенств выпол-

нение условия Слейтера

обеспечивает

непустоту

внутренности множества

D

решений

системы.

То есть

n

,

f

y 0,

int D y : y E

 

 

i

 

i

1, ...,

m

.

Теорема 5.

Пусть D En

– множество

ре-

шений

системы

fi y 0,

i 1, ..., m , удовлетво-

ряющей

условию

Слейтера,

все

функции

fi

вы-

пуклы и непрерывно дифференцируемы. Пусть

точка

x D

такова, что

I x .

Тогда

T x

coneS

x

, где

S x fi x , i I x .

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

 

 

0,

 

,

coneS x g : g

ti fi x , ti

i I x

 

i I x

 

 

 

то из теорем 4, 3 и 1 следует, что

54

coneS x

T

x

Методы оптимизации: Часть I

.

(1)

Докажем теперь включение обратное (1).

Предположим противное. Это означает, что суще-

ствует вектор

h T x

такой, что

h coneS x .

(Очевидно, множество

что

c o n

h e S

0 .) Так как

по теореме

9.6

x является

выпуклым и

за-

мкнутым,

то в силу теоремы 8.1 найдется

вектор

s

строго

опорный

ко

множеству coneS x

в

точке

h .

Тогда для всех

g coneS x

 

 

 

 

 

 

 

s, g h

0 .

 

(2)

Отсюда при

g 0

получаем

 

 

 

 

 

 

 

s, h

0.

 

(3)

Выберем произвольно

i I x

и

t

0

.

Положим

g

i

 

 

 

чим

 

x . Из

неравенства

(2) при

g gi

полу-

t fi

 

 

0 . Отсюда

 

x

1

 

0.

 

 

 

 

s, fi

 

h

s,t fi x h

t

 

 

 

 

 

 

 

 

Устремляя в этом неравенстве получим

f x , s

0

i

 

t к бесконечности,

. (4)

Так как

i I x , то fi x 0 . Из условия Слейте-

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

значение

функции

fi

не

является

минимальным.

Поэтому

 

 

 

fi x 0.

 

 

55

О.А. Кашина, А.И. Кораблев

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Пусть

вектор

z int D . Положим

u z x .

Согласно включению (1)

 

 

 

 

Из замеча-

fi x T x .

ния к теореме 8.2 следует, что

вектор

 

 

 

fi x яв-

ляется

строго

опорным

в

точке

x ко

множеству

int D .

Поэтому

 

 

x

0 . Таким

образом,

fi x , z

 

 

 

 

 

 

 

0 .

 

 

 

 

(5)

 

 

 

 

 

 

fi x , u

 

 

 

 

 

Положим

s s u

для

произвольного

0 .

Тогда

 

 

, s

 

 

 

 

,u

. Отсюда

fi x

fi

x , s

fi x

и из (4), (5)

получаем

 

 

 

0

. Таким обра-

fi x , s

зом, по

теореме 5.2

вектор

s

является

релак-

 

сационным направлением функции fi

в

точке x .

Поэтому

найдется такое

i

0 ,

что

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

f

i

 

x t s

 

 

f

i

 

x

 

0

 

 

 

 

 

 

 

 

 

 

(6)

для всех

t 0, i . Так как

i

– номер произволь-

ного активного ограничения, то (6) выполняется

для всех

i I x .

 

 

 

 

Пусть теперь

i I x ,

то есть

fi

x 0 . То-

гда в силу непрерывности функции

fi найдется

такое i

0 , что

для всех

t 0, i

 

 

 

 

 

 

f

i

 

x t s

 

 

 

 

Положим min i .

 

 

 

i 1,...,m

 

венства (6) получаем,

что

0 .

(7)

Тогда с учетом нера-

(7) справедливо для

56

всех

t 0,

и всех

i

Методы оптимизации: Часть I

1,..., m .

Таким

включение

образом,

 

 

 

x t s

 

 

согласно

int D

для

t

(7)0,

справедливо

.

Из

замечания

вектор

h

(опорный

строго

опорным ко

Поэтому

h, x t s

ктеореме 8.2

кD в точке

множеству int Dx 0 , откуда

следует,

что

x )

является

в

точке

x .

h, s 0 ,

то есть

h, s u

0,

0

. При

0

получим

h, s

0

,

что противоречит (3). Полученное про-

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

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

A

Теорема 6. Пусть

 

n

, Ax b ,

где

D x : x E

– матрица размерности

m n , вектор

b E

m

,

 

точка

x D

такова, что

I x

.

Тогда T x

совпадает торов ai

с

,

i

конической

оболочкой

системы

век-

I x , где

ai – i -тая

строка

мат-

рицы

A

.

Заметим, что эта теорема, вообще

говоря,

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

так как

в ней не предполагается выполнение условия Слейтера.

57