Отделимость и борные гиперплоскости 49

Теорема:

Пусть – замкнутое выпуклое множество из и

Тогда существует единственная точка с минимальным расстоянием до . Эта точка находится на минимальном расстоянии от тогда и только тогда, когда

(*) для всех

Если представить что – ближайшая точка, не соответствующая условиям (*) получим:

(точка – ближе к )

Пусть и – непустые множества из .

Гиперплоскость

разделяет и , если для всех и для всех

(c) (d)

Рис. 2.8. Различные типы разделения множеств, а — несобственная отдели­мость; b — собственная отделимость; с — строгая отделимость; d — сильная отделимость.

Определение:

Пусть – непустое множество в и

( – граница множества )

Гиперплоскость называется опорной к в точке , если либо , т.е. для всех

либо , т.е. для всех

Если к тому же , то называют собственной опорной гиперплоскостью к в точке

Теорема: выпуклое множество имеет опорные плоскости в любой граничной точке

4. Выпуклые конусы

Непустое множество из называют конусом с вершиной в начале координат, если из того, что , следует, что для всех

Если – выпуклое множество, то оно называется выпуклым конусом

5. Экстремальные точки и экстремальные направления

Определение: Пусть – непустое выпуклое множество в

Вектор называется экстремальной точкой множества , если представление , где

, справедливо только при

Определение: Пусть – непустое выпуклое множество в

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

Два направления и называют различный, если для любых

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

, то при

(0. 0)

– экстремальные направления

II Условия оптимальности.

1. Конусы возможных направлений

Определение: Конусом возможных направлений в точке называется множество при всех для некоторого

Любой вектор из называется возможным направлением.

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

конус убывания функции, т.е. 50

- конус возможных направлений в т.

Теорема: Пусть дифференцируема в некоторой точке . Если – точка локального минимума, то

(т.е. конус убывания функции не пересекается с конусом возможных направлений)

Теорема: Пусть задана задача Р:

Минимизировать и обозначена через

(т.е. – множество индексов , соответствующих активным ограничением)

Предположим, что функций и при дифференцируемы в точке , а функции при непрерывны в точке .

Если – точка локального минимума, то

Здесь , для всех (т.е. - конус убывания функции (полупространство, антиградиент функции)

- конус антиградиентов активных ограничений

Пример:

Минимизировать:

При условий:

В этом случае:

Рассмотрим точку

В этой точке активно одно ограничение

В т.

Для удобства перенесем начало координат в точку

Точка – не оптимальна

Рассмотрим теперь точку

Активны ограничения и

Градиенты равны:

Конусы и не пересекаются

Точка (2,1) – точка оптимума

2.Условия Кука-Токкера(для задач с ограничениями-неравенствами)

Рассмотрим задачу:

Минимизировать:

При условий:

– непустое открытое множество

Пусть – произвольная допустимая точка задачи 51

Предположим, что и для дифференцируемы в точке , а функции для непрерывны в этой точке.

Пусть также векторы при линейно независимы.

Если точка – точка локального оптимума, то существуют такие числа для , то:

Если, кроме того, функции для дифференцируемы в точке , то условие Кука-Таккера можно переписать в следующей форме:

=0

В векторной форме:

– матрица порядка n x m, у которой i-й столбец равен

– m-мерный вектор (вектор множителей Лагранжа)

(В рассмотренном примере в точке множители Лагранжа – условие оптимальности удовлетворяется).