Категории: ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника |
Отделимость и борные гиперплоскости 49Теорема: Пусть – замкнутое выпуклое множество из и Тогда существует единственная точка с минимальным расстоянием до . Эта точка находится на минимальном расстоянии от тогда и только тогда, когда (*) для всех Если представить что – ближайшая точка, не соответствующая условиям (*) получим: (точка – ближе к ) Пусть и – непустые множества из .
Гиперплоскость разделяет и , если для всех и для всех (c) (d)
Рис. 2.8. Различные типы разделения множеств, а — несобственная отделимость; b — собственная отделимость; с — строгая отделимость; d — сильная отделимость. Определение: Пусть – непустое множество в и ( – граница множества ) Гиперплоскость называется опорной к в точке , если либо , т.е. для всех либо , т.е. для всех Если к тому же , то называют собственной опорной гиперплоскостью к в точке
Теорема: выпуклое множество имеет опорные плоскости в любой граничной точке 4. Выпуклые конусы Непустое множество из называют конусом с вершиной в начале координат, если из того, что , следует, что для всех Если – выпуклое множество, то оно называется выпуклым конусом 5. Экстремальные точки и экстремальные направления Определение: Пусть – непустое выпуклое множество в Вектор называется экстремальной точкой множества , если представление , где , справедливо только при Определение: Пусть – непустое выпуклое множество в Ненулевой вектор из называется направлением множества , если для любого точка в при всех Два направления и называют различный, если для любых Направление множества называется экстремальным, если оно не может быть представлено в виде положительной линейной комбинации двух различных направлений, т.е. если , то при (0. 0) – экстремальные направления II Условия оптимальности. 1. Конусы возможных направлений Определение: Конусом возможных направлений в точке называется множество при всех для некоторого
Любой вектор из называется возможным направлением. При целых любое перемещение вдоль вектора из т. приведет в точку конус убывания функции, т.е. 50 - конус возможных направлений в т. Теорема: Пусть дифференцируема в некоторой точке . Если – точка локального минимума, то (т.е. конус убывания функции не пересекается с конусом возможных направлений) Теорема: Пусть задана задача Р: Минимизировать и обозначена через (т.е. – множество индексов , соответствующих активным ограничением) Предположим, что функций и при дифференцируемы в точке , а функции при непрерывны в точке . Если – точка локального минимума, то Здесь , для всех (т.е. - конус убывания функции (полупространство, антиградиент функции) - конус антиградиентов активных ограничений Пример: Минимизировать: При условий:
В этом случае: Рассмотрим точку В этой точке активно одно ограничение
В т. Для удобства перенесем начало координат в точку Точка – не оптимальна
Рассмотрим теперь точку Активны ограничения и Градиенты равны: Конусы и не пересекаются Точка (2,1) – точка оптимума 2.Условия Кука-Токкера(для задач с ограничениями-неравенствами) Рассмотрим задачу: Минимизировать: При условий: – непустое открытое множество Пусть – произвольная допустимая точка задачи 51 Предположим, что и для дифференцируемы в точке , а функции для непрерывны в этой точке. Пусть также векторы при линейно независимы. Если точка – точка локального оптимума, то существуют такие числа для , то:
Если, кроме того, функции для дифференцируемы в точке , то условие Кука-Таккера можно переписать в следующей форме: =0
В векторной форме: – матрица порядка n x m, у которой i-й столбец равен – m-мерный вектор (вектор множителей Лагранжа) (В рассмотренном примере в точке множители Лагранжа – условие оптимальности удовлетворяется). |
||
Последнее изменение этой страницы: 2016-06-10 lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда... |