ВОЕНЫ АЛЛАХА1АЗАЗАЗАЗ / 10_Конусы_опорных_векторов_сент_9_2008
.pdfО.А. Кашина, А.И. Кораблев
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