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

Конец ознакомительного фрагмента.

Текст предоставлен ООО «ЛитРес».

Прочитайте эту книгу целиком, купив полную легальную версию на ЛитРес.

Стоимость полной версии книги 119,00р. (на 09.04.2014).

Безопасно оплатить книгу можно банковской картой Visa, MasterCard, Maestro, со счета мобильного телефона, с платежного терминала, в салоне МТС или Связной, через PayPal, WebMoney, Яндекс.Деньги, QIWI Кошелек, бонусными картойами или другим удобным Вам способом.

Ранее в параграфе 8 было введено множество векторов, опорных в точке ко множеству . Изучим свойства этих множеств.

Теорема 1. В любой точке множество является выпуклым замкнутым конусом.

Доказательство. Пусть , , . Для любого имеем и , а значит, , то есть . Итак, – выпуклый конус.

Проверим его замкнутость. Пусть – предельная точка конуса . Это означает, что существует последовательность

такая, что . Для любой точки справедливы неравенства

Следовательно, , то есть . Что и означает замкнутость .

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

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

. Тогда .

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

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

Тогда .

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

Теорема 4. Пусть , где функция определена, является выпуклой и непрерывно дифференцируемой на , точка такова, что . Тогда .

Доказательство. Пусть точка , то есть . Учитывая, что по условиям , имеем . Отсюда и из теоремы 4.1 следует . Что и требовалось.

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

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

Если данная система неравенств удовлетворяет условию Слейтера относительно , то будем просто говорить, что она удовлетворяет условию Слейтера.

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

То есть .

Теорема 5. Пусть – множество решений системы , удовлетворяющей условию Слейтера, все функции выпуклы и непрерывно дифференцируемы. Пусть точка такова, что . Тогда , где .

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

,

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

. (1)

Докажем теперь включение обратное (1). Предположим противное. Это означает, что существует вектор такой, что . (Очевидно, что .) Так как по теореме 9.6 множество является выпуклым и замкнутым, то в силу теоремы 8.1 найдется вектор строго опорный ко множеству в точке . Тогда для всех

. (2)

Отсюда при получаем

. (3)

Выберем произвольно и . Положим . Из неравенства (2) при получим . Отсюда . Устремляя в этом неравенстве к бесконечности, получим

. (4)

Так как , то . Из условия Слейтера следует, что нулевое значение функции не является минимальным. Поэтому .

Пусть вектор . Положим . Согласно включению (1) . Из замечания к теореме 8.2 следует, что вектор является строго опорным в точке ко множеству . Поэтому . Таким образом,

. (5)

Положим для произвольного . Тогда . Отсюда и из (4), (5) получаем . Таким образом, по теореме 5.2 вектор является релаксационным направлением функции в точке . Поэтому найдется такое , что

(6)

для всех . Так как – номер произвольного активного ограничения, то (6) выполняется для всех .

Пусть теперь , то есть . Тогда в силу непрерывности функции найдется такое , что для всех

. (7)

Положим . Тогда с учетом неравенства (6) получаем, что (7) справедливо для всех и всех .

Таким образом, согласно (7) справедливо включение для .

Из замечания к теореме 8.2 следует, что вектор (опорный к в точке ) является строго опорным ко множеству в точке . Поэтому , откуда ,

то есть . При получим , что противоречит (3). Полученное противоречие доказывает теорему.

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

Теорема 6. Пусть , где – матрица размерности , вектор ,

точка такова, что . Тогда совпадает с конической оболочкой системы векторов , где – -тая строка матрицы .

Заметим, что эта теорема, вообще говоря, не является частным случаем теоремы 5, так как в ней не предполагается выполнение условия Слейтера.

Дата добавления: 2014-11-25; Просмотров: 499; Нарушение авторских прав?; Мы поможем в написании вашей работы!