Как найти расстояние между множествами

Расстояние Хэмминга. На универсальном множестве зададим с помощью характеристической функции подмножества и :

, .

Под Расстоянием Хэмминга между множествами и понимают величину:

.

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

1) ;

2) ;

3) ;

4) для любых подмножеств , где оператор «» связан с вводимым понятием расстояния.

Если , то расстояние Хэмминга удовлетворяет условиям 1 – 4.

Для конечного множества мощности можно определить Относительное расстояние Хэмминга: . Очевидно,

Пример 35. На универсальном множестве зададим подмножества и :

, .

Применяя формулу расстояния Хэмминга между множествами, получим: , а для относительного расстояния Хэмминга имеем:

Обобщение понятия расстояния Хэмминга. Пусть нечёткие множества и заданы на универсальном множестве мощности . Тогда Обобщённое расстояние Хэмминга между нечёткими множествами и определяется по формуле:

.

Обобщённое относительное расстояние Хэмминга определяет величина

.

Очевидно,

Обобщённое евклидово расстояние. Расстояние Хэмминга называется также линейным расстоянием. Обобщённое евклидово или квадратичное расстояние между нечёткими множествами определяется по формуле:

.

Очевидно, . Величина называется Обобщённой евклидовой нормой, а величина – Обобщённым относительным евклидовым расстоянием.

Выбор того или иного расстояния зависит от природы рассматриваемой проблемы. Каждое из этих расстояний обладает своими преимуществами и недостатками, которые становятся очевидными в приложениях.

Случай бесконечного универсального множества. Расстояния , и норма могут быть определены и в случае, когда – бесконечное множество.

Если – счётное множество, то , аналогично, При условии, что ряды в этих формулах сходятся.

Если , то

,

При условии, что несобственные интегралы в этих формулах сходятся.

Легко показать, что только для чёткого множества , ближайшего к нечёткому множеству , евклидово расстояние от до заданного нечёткого минимально.

< Предыдущая		Следующая >

6.5 Операции над нечеткими множествами

Рассмотрим операции над нечеткими множествами.

Дополнение. Пересечение. Объединение.

Пусть дано множество и два его нечетких подмножества:

Дополнением нечеткого множества называют множество

Пересечением нечетких множеств и называют нечеткое множество

Объединением нечетких множеств и называют нечеткое множество

Продемонстрируем операции над множествами средствами программы MathCad.

Пример 6.5

Приводим листинги операций дополнения, пересечения, объединения для нечетких множеств в виде матриц примера 6.1. (рис.6.7, рис. 6.8):

Дополнения нечетких множеств. – единичная матрица.

,

,

,

Пример 6.6

Приводим листинги операций дополнения, пересечения, объединения для нечетких множеств примера 6.2 с треугольными функциями принадлежности. (рис.6.9, рис. 6.10,6.11 )

Дополнение множеств

Объединение и пересечение множеств

Пересечение множеств

Расстояние между множествами

Чтобы определить расстояние между элементами множества , надо наложить метрику на это множество. Рассмотрим следующие метрики. Математическим прообразом реального трехмерного пространства является пространство Евклида. Пространство Евклида обозначают обычно . Для линейных дискретных пространств, особенностью которых является то, что координаты векторов могут принимать лишь дискретные значения, известно пространство Хемминга. Если рассмотреть функции принадлежности всех множеств на универсальном множестве , то они образуют функциональное множество всех функций, определенных на , и принимающих значения на отрезке . Метрика на множестве — это функция , сопоставляющая каждой паре элементов действительное число по правилу выбранного пространства.

Чтобы найти расстояние между множествами и используются метрики, представленные в таблице 6.2:

Пример. 6.7

Для нечетких множеств и примера 6.1. построим расстояние между множествами в среде MathCad. Обозначим – расстояние по Хеммингу, — расстояние по Евклиду (см. рис. 6.2):

,

,

Определение понятия «обычное множество, ближайшее к нечеткому»

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

Геометрический смысл понятия «обычное множество , ближайшее к нечеткому множеству » иллюстрирует рис. 6.12.

Значения при различном расположении точек графиков функций:

— функция , — функция

Как видно на рисунке, справедливы неравенства

независимо от того или

Если — обычное множество, то оно является ближайшим к самому себе. Это следует непосредственно из определения.

Пример 6.8

Для множеств и примера 6.1 построим в MathCad множества и – ближайшие к нечетким, воспользуемся встроенной функцией

if (условие, результат1, результат2)

результат 1 – если условие выполнено, результат 2 в противном случае.

– множества ближайшие к нечетким и

,

,

,

Напомним,
что
в точечном евклидовом пространстве Eⁿ
расстояние
между точками
P(x₁,
x₂,…
x_n),
Q(y₁,
y₂,…
y_n)
вычисляется по формуле

(P,
Q)
= ,

если
координаты точек заданы относительно
ортонормированной системы координат.
Мы можем рассматривать это расстояние,
как функцию, сопоставляющую двум точкам
P
и Q
число (P,
Q).
Функция 
обладает следующими свойствами:

1.
(P,
Q)
=
(Q,
P);

2.
(P,
Q)
+
(Q,
R)

(P,
R)
(неравенство треугольника);

3.
(P,
Q)

0, и (P,
Q)
=
0 
P
=
Q.

Пусть
теперь M
– произвольное множество, элементы
которого будем называть точками. Пусть
на M
задана функция ,
сопоставляющая любым двум точкам P,
QM
число (P,
Q),
которое называется расстоянием между
этими точками, и такая что выполнены
свойства (аксиомы) 1,
2,
3.
Тогда пара (M,
)
называется метрическим
пространством,
а функция 
– метрикой.

Примеры
1. Пусть V
– произвольное подмножество евклидова
пространства. Расстояние между двумя
точками P,
QV
будем считать
таким же, как во всем пространстве. Тогда
(V,
)
– метрическое пространство. Метрика

называется
индуцированной
из Eⁿ.

2
.
Сфера S²
в трехмерном геометрическом пространстве.
Расстояние ₁
между P,
Q
S²
определяется
как длина кратчайшей кривой по поверхности,
соединяющей P
и Q.
Как известно, этой кривой
является дуга большой окружности
(у которой радиус равен радиусу сферы).

Мы
также можем определить расстояние
как в примере 1: (P,
Q)
– это длина
хорды PQ.
Тогда (S²,
₁)
и (S²,
)
– это разные метрические пространства.

3.
Определим
на плоскости расстояние между точками
A(x₁,
y₁),
B(x₂,
y₂)
по формуле ₂(A,
B)=|x₂

x₁|+|y₂

y₁|.
Получается, что ₂(A,
B)
равно длине ломаной AMB,
изображённой на следующем чертеже.

У
пражнение.
Самостоятельно
про-верьте, что для плоскости с метрикой
₂
выполняются
все аксиомы метрического пространства.

Диаметром
множества
V
в метрическом пространстве (M,
)
называется
точная верхняя грань расстояний между
точками этого множества:

d(V)
= sup;sdo10(P
(P,
Q).

Расстоянием
между двумя множествами
V,
W
называется
точная нижняя грань расстояний между
точками этих множеств:

(V,
W)
= inf;sdo10(P(V
(P,
Q).

В
частности, если одно из множеств состоит
из одной точки, то получаем определение
расстояния
от точки до множества.

П
очему
в этом определении супрэмум, а не
максимум, инфинум, а не минимум? Поясним
на примере.

Пример.
Пусть V
– это открытый (без границы) круг радиуса
1 на плоскости с центром в начале
координат, а W
= Q(2,0).
Тогда d(V)
= 2,
хотя таких точек, расстояние между
которыми равно 2 в V
нет. Таким образом, максимум не
достигается. Аналогично, (Q,
V)
= 1,
хотя такой точки PV,
что (Q,
P)
= 1
не существует. Значит, минимум не
достигается.

Отметим,
что если множества пересекаются, то
расстояние между ними равно нулю.
Обратное неверно. Например, если W
есть прямая x
=
1, то (V,
W)
= 0,
но V
W=.

Определение.
Множество V
в метрическом пространстве (M,
)
называется
ограниченным,
если d(V)<.

Заметим,
что и всё метрическое пространство
может быть ограниченным, как например,
(S²,
₁).

Упражнение.
Чему равны
диаметры метрических пространств (S²,
₁)
и (S²,
)?

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Пусть

A
,

B
и

C
– конечные нечеткие множества, заданные на универсальном множестве

X
. Введем понятие расстояния

ρ

A
,
B

между нечеткими множествами. При введении расстояния обычно предъявляются следующие требования:

• ρ

  A
  ,
  B

  ≥
  0
  – неотрицательность;

• ρ

  A
  ,
  B

  =
  ρ

  B
  ,
  A

  – симметричность;

• ρ

  A
  ,
  B

  ≤
  ρ

  A
  ,
  C

  +
  ρ

  B
  ,
  C

  – транзитивность;

• ρ

  A
  ,
  A

  =
  0
  – самоподобие.

Расстояние Хемминга(линейное расстояние) определяется как:

ρ

A
,
B

=

∑

i
=
1

n

μ
A

x
i

−

μ
B

x
i

,

0
≤
ρ

A
,
B

≤
n
.

Относительное расстояние Хемминга определяется как:

ρ

rel

A
,
B

=

1
n

∑

i
=
1

n

μ
A

x
i

−

μ
B

x
i

=

1
n

ρ

A
,
B

,

0
≤

ρ

rel

A
,
B

≤
1
.

Евклидово (квадратичное расстояние) определяется как:

e

A
,
B

=

∑

i
=
1

n

μ
A

x
i

−

μ
B

x
i

2

,

0
≤
e

A
,
B

≤

n

.

Относительное Евклидово расстояние определяется как:

e

rel

A
,
B

=

1
n

∑

i
=
1

n

μ
A

x
i

−

μ
B

x
i

2

=

e

A
,
B

n

,

0
≤

e

rel

A
,
B

≤
1
.

В случае бесконечных счетных нечетких множеств

A
,
B
расстояние Хемминга и квадратичное расстояние определяются аналогично, с учетом сходимости соответствующих сумм:

ρ

A
,
B

=

lim

n
→
∞

∑

i
=
1

n

μ
A

x
i

−

μ
B

x
i

,

ρ

rel

A
,
B

=

lim

n
→
∞

1
n

∑

i
=
1

n

μ
A

x
i

−

μ
B

x
i

,

e

A
,
B

=

lim

n
→
∞

∑

i
=
1

n

μ
A

x
i

−

μ
B

x
i

2

,

e

rel

A
,
B

=

lim

n
→
∞

1
n

∑

i
=
1

n

μ
A

x
i

−

μ
B

x
i

2

.

В случае бесконечных несчетных нечетких множеств

A
,
B
, с ограниченным носителем

a
;
b

, расстояние Хемминга и квадратичное расстояние определяются следующим образом:

ρ

A
,
B

=

∫
a
b

μ
A

x

−

μ
B

x

dx

,

ρ

rel

A
,
B

=

1

b
−
a

∫
a
b

μ
A

x

−

μ
B

x

dx

,

e

A
,
B

=

∫
a
b

μ
A

x

−

μ
B

x

2

dx

,

e

rel

A
,
B

=

1

b
−
a

∫
a
b

μ
A

x

−

μ
B

x

2

dx

.

В случае бесконечных несчетных нечетких множеств

A
,
B
, носители которых неограниченны (варианты

−
∞
;
a

,

a
;
∞

,

−
∞
;
+
∞

, расстояние Хемминга и квадратичное расстояние определяются аналогично с условием сходимости соответствующих несобственных
интегралов:

ρ

A
,
B

=

∫

−
∞

a

μ
A

x

−

μ
B

x

dx

,

ρ

A
,
B

=

∫
a
∞

μ
A

x

−

μ
B

x

dx

,

ρ

A
,
B

=

∫

−
∞

∞

μ
A

x

−

μ
B

x

dx

,

e

A
,
B

=

∫

−
∞

a

μ
A

x

−

μ
B

x

2

dx

,

e

A
,
B

=

∫
a
∞

μ
A

x

−

μ
B

x

2

dx

,

e

A
,
B

=

∫

−
∞

∞

μ
A

x

−

μ
B

x

2

dx

.

При задании несчетных нечетких множеств с неограниченными носителями относительные оценки

ρ

rel

A
,
B

и

e

rel

A
,
B

в качестве меры расстояний между нечеткими множествами не используются. Однако, если это необходимо, то относительную меру
расстояния можно ввести, используя другое определение или другое понятие сходимости [26].

Выбор того или иного расстояния – абсолютного или относительного, Хемминга или Евклидова зависит от природы рассматриваемой
проблемы. Каждое из этих расстояний обладает определенными преимуществами и недостатками, которые становятся очевидными при
практическом решении той или иной технической задачи. В зависимости от специфики решаемой проблемы для нечетких множеств можно
ввести и другие понятия меры расстояния [17], [26].

Пример.
A
=
0,1
/
1
+
0,5
/
2
+
1
/
3
,

B
=
0,2
/
2
+
1
/
3
+
0,7
/
4
.

ρ

A
,
B

=

0,1
−
0

+

0,5
−
0,2

+

1
−
1

+

0
−
0,7

=
0,1
+
0,3
+
0
+
0,7
=
1,1
.

ρ

rel

A
,
B

=

1
4

0,1
−
0

+

0,5
−
0,2

+

1
−
1

+

0
−
0,7

=

1
4

0,1
+
0,3
+
0
+
0,7

=
0,
275
.

e

A
,
B

=

0,1
−
0

2

+

0,5
−
0,2

2

+

1
−
1

2

+

0
−
0,7

2

=

0,
01
+
0,
09
+
0
+
0,
49

=
0,
768
.

e

rel

A
,
B

=

0,1
−
0

2

+

0,5
−
0,2

2

+

1
−
1

2

+

0
−
0,7

2

4

=

0,
01
+
0,
09
+
0
+
0,
49

4

=
0,
384
.

Введем далее индекс нечеткостиили показатель размытости нечеткого множества. Если объект

x
обладает свойством

R
, порождающим нечеткое множество

A
лишь в частной мере, т.е.

0
≤

μ
A

x

≤
1
, то внутренняя неопределенность, двусмысленность объекта

x
в отношении свойства

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

A
, обладающих свойством

R
, и классу объектов

A
ˉ

, не обладающих свойством

R
. Эта двусмысленность максимальна, когда степени принадлежности объекта обеим классам равны, т.е.

μ
A

x

=

μ

A
ˉ

x

=
0,5
, и минимальна, когда объект принадлежит только одному классу, т.е. либо

μ
A

x

=
1
и

μ

A
ˉ

x

=
0
, либо

μ
A

x

=
0
и

μ

A
ˉ

x

=
1
. В общем случае показатель размытости нечеткого множества

A
можно определить в виде функционала

d

A

, удовлетворяющего следующим условиям:

• d

  A

  =
  0
  тогда, когда

  A
  – обычное множество с

  μ
  A

  x

  ∈

  0
  ;
  1

  ;

• d

  A

  максимально тогда, когда

  μ
  A

  x

  =
  0,5
  для всех

  ∀
  x
  ∈
  X
  ;

• d

  A

  ≤
  d

  B

  , если

  A
  является заострением
  B
  , т.е. выполняется

μ
A

x

≤

μ
B

x

,

если

μ
B

x

<
0,5
,

μ
A

x

≥

μ
B

x

,

если

μ
B

x

>
0,5
,

μ
A

x

∈

0
;
1

,

если

μ
B

x

=
0,5
;

• d

  A

  ≤
  d

  A
  ˉ

  – симметричность относительно точек перехода;

• d

  A
  ∪
  B

  +
  d

  A
  ∩
  B

  =
  d

  A

  +
  d

  B

  .

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

d

A

, либо некоторые условия усиливаются или ослабляются в зависимости от решаемой задачи. Обычно оперируют индексами нечеткости
(показателями размытости), которые можно определить, используя понятие расстояния.

Обычное множество, ближайшее к нечеткому. Пусть

A
– нечеткое множество, определенное на универсальном множестве

X
. Какое обычное множество

A
ˉ

⊂
X
является ближайшим к

A
, т.е. находится на наименьшем евклидовом расстоянии от нечеткого множества

A
? Такое множество будет обладать следующей характеристической функцией:

μ

A
—

x
i

=

0,

если

μ
A

x
i

≤
0,5
,

1,

если

μ
A

x
i

>
0,5
.

Обычно принимают

μ

A
—

x
i

=
0
если

μ
A

x
i

=
0,5
. Используя понятие обычного множества, ближайшего к нечеткому, введем следующие индексы нечеткости нечеткого множества

A
.

Линейный индекс нечеткости:

• d

  A

  =

  2
  n

  ρ

  A
  ,

  A
  ˉ

  для конечного нечеткое множества

  A
  ;

• d

  A

  =

  lim

  n
  →
  ∞

  2
  n

  ∑

  i
  =
  1

  n

  μ
  A

  x
  i

  −

  μ

  A
  —

  x
  i

  для бесконечного счетного нечеткого множества

  A
  ;

• d

  A

  =

  2

  b
  −
  a

  ∫
  a
  b

  μ
  A

  x
  i

  −

  μ

  A
  —

  x
  i

  dx

  для бесконечного несчетного нечеткого множества

  A
  с носителем

  a
  ;
  b

  .

Квадратичный индекс нечеткости:

• d

  A

  =

  2

  n

  e

  A
  ,

  A
  ˉ

  для конечного нечеткое множества

  A
  ;

• d

  A

  =

  lim

  n
  →
  ∞

  2

  n

  ∑

  i
  =
  1

  n

  μ
  A

  x
  i

  −

  μ

  A
  —

  x
  i

  2

  для бесконечного счетного нечеткого множества

  A
  ;

• d

  A

  =

  2

  b
  −
  a

  ∫
  a
  b

  μ
  A

  x
  i

  −

  μ

  A
  —

  x
  i

  2

  dx

  для бесконечного несчетного нечеткого множества

  A
  с носителем

  a
  ;
  b

  .

Линейный и квадратичный индексы нечеткости нечеткого множества

A
можно определить, используя операцию дополнения.

Линейный индекс нечеткости с дополнением:

• d

  A

  =

  2
  n

  ∑

  i
  =
  1

  n

  min

  μ
  A

  x
  i

  ;

  μ

  A
  ˉ

  x
  i

  для конечного нечеткого множества

  A
  ;

• d

  A

  =

  lim

  n
  →
  ∞

  2
  n

  ∑

  i
  =
  1

  n

  min

  μ
  A

  x
  i

  ;

  μ

  A
  ˉ

  x
  i

  для бесконечного счетного нечеткого множества

  A
  ;

• d

  A

  =

  2

  b
  −
  a

  ∫
  a
  b

  min

  μ
  A

  x

  ;

  μ

  A
  ˉ

  x

  dx

  для бесконечного несчетного нечеткого множества

  A
  с носителем

  a
  ;
  b

  .

Квадратичный индекс нечеткости с дополнением:

• d

  A

  =

  2

  n

  ∑

  i
  =
  1

  n

  min

  μ
  A
  2

  x
  i

  ;

  μ

  A
  ˉ

  2

  x
  i

  – для конечного нечеткое множества

  A
  ;

• d

  A

  =

  lim

  n
  →
  ∞

  2

  n

  ∑

  i
  =
  1

  n

  min

  μ
  A
  2

  x
  i

  ;

  μ

  A
  ˉ

  2

  x
  i

  – для бесконечного счетного нечеткого множества

  A
  ;

• d

  A

  =

  2

  b
  −
  a

  ∫
  a
  b

  min

  μ
  A
  2

  x

  ;

  μ

  A
  ˉ

  2

  x

  dx

  – для бесконечного несчетного нечеткого множества

  A
  с носителем

  a
  ;
  b

  .

С ближайшим обычным множеством связаны свойства:

• A
  ∩
  B

  ˉ

  =

  A
  ˉ

  ∩

  B
  ˉ

  ;

• A
  ∪
  B

  ˉ

  =

  A
  ˉ

  ∪

  B
  ˉ

  ;

• ∀
  x
  ∈
  X
  :

  μ
  A

  x

  −

  μ

  A
  —

  x

  =

  μ

  A
  ∩

  A
  ˉ

  x

  .

На основании последнего свойства линейный индекс нечеткости можно представить в следующем виде:

d

A

=

2
n

∑

i
=
1

n

∣

μ
A

x
i

−

μ

A
—

x
i

∣
=

2
n

∑

i
=
1

n

μ

A
∩

A
ˉ

x
i

,

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

d

A

=
d

A
_

. Следовательно, операции пересечения и объединения не дают эффекта увеличения или понижения нечеткости.

Векторный индикатор нечеткости – это нечеткое множество с функцией принадлежности

2μ

A
∩

A
ˉ

x

.

Если система может пребывать в

N
различных состояниях с вероятностями

p
1

…

p
N

, то энтропия системы определяется как:

H

p
1

,
…
,

p
N

=
−

∑

i
=
1

N

p
i

ln

p
i

.

Энтропия минимальна

H
=
0
при достоверно известном и неизменном состоянии системы, т.е. когда для одного из состояний

p
r

=
1
,

1
≤
r
≤
N
, а для остальных состояний

p
i

=
0
,

i
≠
r
,
i
∈

1
;
2
;
.
.
.
;
N
−
1
;
N

. Энтропия максимальна

H
=
ln
N
при равновероятных состояниях системы

p
1

=

p
2

=
…
=

p
N

=

1
N

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

0
≤
H
≤
1
:

H

p
1

,
…
,

p
N

=
−

1

ln
N

∑

i
=
1

N

p
i

ln

p
i

Если нечеткое множество

A
задано на конечном счетном универсальном множестве

X
, то степень нечеткости данного нечеткого множества можно оценить через энтропию. При этом для всех

N
элементов носителя нечеткого множества

S
A

вводится частота:

π
A

x
i

=

μ
A

x
i

∑

i
=
1

N

μ
A

x
i

,
i
=
1
…
N
.

Очевидно, что

∑

i
=
1

N

π
A

x
i

=
1
. Это позволяет рассматривать введенную частоту как аналог вероятности и по аналогии посчитать энтропию нечеткости данного
множества:

H

π
A

x
1

,
…
,

π
A

x
N

=
−

1

ln
N

∑

i
=
1

N

π
A

x
i

ln

π
A

x
i

.

Методы Оптимизации. Даниил Меркулов. Отделимость. Проекция. Опорная гиперплоскость

Interior

Внутренность множества

Внутренностью множества $S$ называется следующее множество:
$$mathbf{int} (S) = {mathbf{x} in S mid exists varepsilon &gt; 0, B(mathbf{x}, varepsilon) subset S}$$
где $B(mathbf{x}, varepsilon) = mathbf{x} + varepsilon B$ — шар с центром в т.$mathbf{x}$ и радиусом $varepsilon$

Относительная внутренность множества

Относительной внутренностью множества $S$ называется следующее множество:
$$mathbf{relint} (S) = {mathbf{x} in S mid exists varepsilon &gt; 0, B(mathbf{x}, varepsilon) cap mathbf{aff} (S) subseteq S}$$

• Любое непустое выпуклое множество $S subseteq mathbb{R}^n$ имеет непустую относительную внутренность $mathbf{relint}(S)$

Projection

Расстояние между точкой и множеством

Расстоянием $d$ от точки $mathbf{y} in mathbb{R}^n$ до замкнутого множества $S subset mathbb{R}^n$ является:
$$d(mathbf{y}, S, | cdot |) = inf{|x — y| mid x in S }$$

Проекция точки на множество

Проекцией точки $mathbf{y} in mathbb{R}^n$ на множество $S subseteq mathbb{R}^n$ называется точка $pi_S(mathbf{y}) in S$: $$| pi_S(mathbf{y}) — mathbf{y}| le |mathbf{x} — mathbf{y}|, forall mathbf{x} in S$$

• Если множество — открыто, и точка в нем не лежит, то её проекции на это множество не существует
• Если точка лежит в множестве, то её проекция — это сама точка
• $$pi_S(mathbf{y}) = underset{mathbf{y}}{operatorname{argmin}} |mathbf{x}-mathbf{y}|$$
• Пусть $S subseteq mathbb{R}^n$ — выпуклое замкнутое множество. Пусть так же имеются точки $mathbf{y} in mathbb{R}^n$ и $mathbf{pi} in S$. Тогда если для всех $mathbf{x} in S$ справедливо неравенство: $$langle pi -mathbf{y}, mathbf{x} — pirangle ge 0, $$ то $pi$ является проекцией точки $mathbf{y}$ на $S$, т.е. $pi_S (mathbf{y}) = pi$
• Пусть $S subseteq mathbb{R}^n$ — афинное множество. Пусть так же имеются точки $mathbf{y} in mathbb{R}^n$ и $mathbf{pi} in S$. Тогда $pi$ является проекцией точки $mathbf{y}$ на $S$, т.е. $pi_S (mathbf{y}) = pi$ тогда и только тогда, когда для всех $mathbf{x} in S$ справедливо равенство: $$langle pi -mathbf{y}, mathbf{x} — pirangle = 0 $$

Пример 1

Найти $pi_S (y) = pi$, если $S = {x in mathbb{R}^n mid |x — x_c| le R }$, $y notin S$

Решение:

• Из рисунка строим гипотезу: $pi = x_0 + R cdot frac{y — x_0}{|y — x_0|}$

• Проверяем неравенство для выпуклого замкнутого множества: $(pi — y)^T(x — pi) ge 0$

$$left( x_0 — y + R frac{y — x_0}{|y — x_0|} right)^Tleft( x — x_0 — R frac{y — x_0}{|y — x_0|} right) =$$
$$left( frac{(y — x_0)(R — |y — x_0|)}{|y — x_0|} right)^Tleft( frac{(x-x_0)|y-x_0|-R(y — x_0)}{|y — x_0|} right) =$$
$$frac{R — |y — x_0|}{|y — x_0|^2} left(y — x_0 right)^Tleft( left(x-x_0right)|y-x_0|-Rleft(y — x_0right) right) = $$

$$frac{R — |y — x_0|}{|y — x_0|} left( left(y — x_0 right)^Tleft( x-x_0right)-R|y — x_0| right) =$$

$$left(R — |y — x_0| right) left( frac{(y — x_0 )^T( x-x_0)}{|y — x_0|}-R right)$$

Первый сомножитель отрицателен по выбору точки $y$. Второй сомножитель так же отрицателен, если применить к его записи теорему Коши — Буняковского: $$(y — x_0 )^T( x-x_0) le |y — x_0||x-x_0|$$
$$frac{(y — x_0 )^T( x-x_0)}{|y — x_0|} — R le frac{|y — x_0||x-x_0|}{|y — x_0|} — R = |x — x_0| — R le 0$$

Пример 2

Найти $pi_S (y) = pi$, если $S = {x in mathbb{R}^n mid c^T x = b }$, $y notin S$

Решение:

• Из рисунка строим гипотезу: $pi = y + alpha c$. Коэффициент $alpha$ подбирается так, чтобы $pi in S$: $c^T pi = b$, т.е.: $$c^T (y + alpha c) = b$$
  $$c^Ty + alpha c^T c = b$$
  $$c^Ty = b — alpha c^T c$$

• Проверяем неравенство для выпуклого замкнутого множества: $(pi — y)^T(x — pi) ge 0$
  $$(y + alpha c — y)^T(x — y — alpha c) = $$
  $$ alpha c^T(x — y — alpha c) = $$
  $$ alpha (c^Tx) — alpha (c^T y) — alpha^2 c^Tc) = $$
  $$ alpha b — alpha (b — alpha c^T c) — alpha^2 c^Tc = $$
  $$ alpha b — alpha b + alpha^2 c^T c — alpha^2 c^Tc = 0 ge 0$$

Пример 3

Найти $pi_S (y) = pi$, если $S = {x in mathbb{R}^n mid Ax = b, A in mathbb{R}^{m times n}, b in mathbb{R}^{m} }$, $y notin S$

Решение:

• Из рисунка строим гипотезу: $pi = y + sumlimits_{i=1}^malpha_i A_i = y + A^T alpha$. Коэффициент $alpha$ подбирается так, чтобы $pi in S$: $A pi = b$, т.е.: $$c^T (y + A^T alpha) = b$$
  $$A(y + A^Talpha) = b$$
  $$Ay = b — A A^Talpha$$

• Проверяем неравенство для выпуклого замкнутого множества: $(pi — y)^T(x — pi) ge 0$
  $$(y + A^Talpha — y)^T(x — y — A^Talpha) = $$
  $$ alpha^T A(x — y — A^Talpha) = $$
  $$ alpha^T (Ax) — alpha^T (A y) — alpha^T AA^T alpha) = $$
  $$ alpha^T b — alpha^T (b — A A^Talpha) — alpha^T AA^T alpha = $$
  $$ alpha^T b — alpha^T b + alpha^T AA^T alpha — alpha^T AA^T alpha = 0 ge 0$$

Separation

Отделимые множества

Множества $S_1$ и $S_2$ называются отделимыми, если существуют $mathbf{p} neq mathbf{0} in mathbb{R}^n$ и $beta in mathbb{R}$, что:
$$langle mathbf{p}, mathbf{x_1}rangle le beta le langle mathbf{p}, mathbf{x_2}rangle, ;; forall mathbf{x_1} in S_1, ;; forall mathbf{x_2} in S_2$$

Собственно отделимые множества

Множества $S_1$ и $S_2$ называются собственно отделимыми, если они отделимы и дополнительно можно указать такие $mathbf{x_1} in S_1, mathbf{x_2} in S_2$
$$langle mathbf{p}, mathbf{x_1}rangle &lt; langle mathbf{p}, mathbf{x_2}rangle$$

Строго отделимые множества

Множества $S_1$ и $S_2$ называются строго отделимыми, если существует $mathbf{p} neq mathbf{0} in mathbb{R}^n$, что:
$$langle mathbf{p}, mathbf{x_1}rangle &lt; langle mathbf{p}, mathbf{x_2}rangle, ;; forall mathbf{x_1} in S_1, ;; forall mathbf{x_2} in S_2$$

Сильно отделимые множества

Множества $S_1$ и $S_2$ называются сильно отделимыми, если существуют $mathbf{p} neq mathbf{0} in mathbb{R}^n$ и $beta in mathbb{R}$, что:
$$ underset{mathbf{x_1} in S_1}{operatorname{sup}} langle mathbf{p}, mathbf{x_1}rangle < beta < underset{mathbf{x_2} in S_2}{operatorname{inf}}langle mathbf{p}, mathbf{x_2}rangle, ;; forall mathbf{x_1} in S_1, ;; forall mathbf{x_2} in S_2$$

Расстояние между множествами

Расстоянием между множествами $S_1$ и $S_2$ называется число:
$$d(S_1, S_2,| cdot |) = underset{mathbf{x_1} in S_1, mathbf{x_2} in S_2}{operatorname{inf}} |mathbf{x_1} — mathbf{x_2}|$$

• Если $X$ и $Y$ — непустые выпуклые множества в $mathbb{R}^n$ и $X cap Y = emptyset$, тогда $X$ и $Y$ — отделимы.
• Если $X$ — непустое выпуклое замкнутое множество в $mathbb{R}^n$ и $mathbf{y} notin X$, тогда точку $mathbf{y}$ можно строго отделить от множества $X$.

Supporting hyperplane

Опорная гиперплоскость

Гиперплоскость $Gamma_{p,beta} = left{mathbf{x} in mathbb{R}^n : langle p, mathbf{x} rangle &gt; beta right}$ называется опорной к множеству $S$ в граничной точке $mathbf{a} in partial S$, если $$langle p, mathbf{x} rangle ge beta = langle p, mathbf{a} rangle ;; forall mathbf{x} in S$$

Опорная гиперплоскость называется собственно опорной, если, кроме того, можно указать $mathbf{x_0} in S: langle p, mathbf{x_0} rangle &gt; beta$

• В любой граничной (относительно граничной) точке выпуклого множества существует опорная (собственно опорная) гиперплоскость.
• Касательная плоскость к поверхности $F(x) = 0,$ где $F: mathbb{R}^n rightarrow mathbb{R}^1$ в точке $x_0$ определяется уравнением: $$nabla F(x_0)^T(x-x_0) = 0$$
• Касательная плоскость к графику функции $f(x),$ где $f: mathbb{R}^n rightarrow mathbb{R}^1$ в точке $x_0$ определяется уравнением: $$phi(x) = f(x_0) + nabla f(x_0)^T(x-x_0) = 0$$

Пример 4

Построить гиперплоскость, разделяющую $S_1$ и $S_2$:
$$S_1 = left{ x in mathbb{R}^2 mid x_1 x_2 ge 1, x_1 &gt; 0right}, ;;; S_2 = left{ x in mathbb{R}^2 mid x_2 le frac{4}{x_1 — 1} +9right}$$

Решение:

• Найдем $partial S_1 cap partial S_2$:
  $$
  begin{cases}
  x_1 x_2 = 1
  x_2 = frac{4}{x_1 — 1} +9
  end{cases}
  $$

$$
begin{cases}
x_1 = frac{1}{3}
x_2 = 3
end{cases}
$$
т.е. множества пересекаются в точке $x_0 = (frac{1}{3}, 3)$

• Построим касательные плоскости к обеим поверхностям в точке пересечения:
  $$
  begin{cases}
  nabla F_1(x_0)^T(x-x_0) = 0
  nabla F_2(x_0)^T(x-x_0) = 0
  end{cases}
  $$

$$
begin{cases}
3 x_1 + frac{1}{3}x_2 — 2 = 0 \
-6 x_1 — frac{2}{3}x_2 + 4 = 0
end{cases}
$$

Итого, получаем: $9x_1 + x_2 = 6$, т.е. $p = (9,1), beta = 6$

Пример 5

Построить опорную гиперплоскость для множества $S = left{ x in mathbb{R}^2 mid e^{x_1} le x_2right}$ в граничной точке $x_0 = (0,1)$

Решение:

• Имеем поверхность $F(x_1, x_2) = e^{x_1} — x_2, ;;; nabla F = (e^{x_1}, -1), ;;; nabla F(x_0) = (1,-1)$
• Тогда $$nabla F(x_0)^T(x-x_0) = 0$$
  $$(1,-1)^T (x_1, x_2 — 1) = 0$$
• Искомая опорная гиперплоскость: $x_1 — x_2 + 1 = 0$

Пример 6

Построить опорную гиперплоскость для множества $S = left{ x in mathbb{R}^3 mid x_3 ge x_1^2 + x_2^2right}$ так, чтобы она отделяла его от точки $x_0 = left(-frac{5}{4}, frac{5}{16}, frac{15}{16}right)$

Решение:

• Заметим, что здесь $x_0 notin partial S$. А значит, таких гиперплоскостей много. Возможный вариант: искать опорную гиперплоскость в точке $pi_S(x_0) = pi in S$. Значит, $Gamma_{p, beta} = left{ x in mathbb{R}^3 mid p^Tx = beta, p^T pi = beta right}$

• Будем искать $pi$, решая задачу минимизации:

$$underset{x in partial S}{operatorname{min}}|x — x_0|^2$$
$$underset{x in partial S}{operatorname{min}}(x — x_0)^T(x — x_0)$$

Учитывая структуру множества $partial S = {x in mathbb{R}^3 mid x_3 = x_1^2 + x_2^2}$, можем перейти к задаче безусловной минимизации.

$$ left( x_1 + frac{5}{4} right)^2 + left( x_2 — frac{5}{16} right)^2 + left( x_1^2 + x_2^2 — frac{15}{16} right)^2 rightarrow operatorname{min}$$

Единственным решением которой является точка $pi = left( -1, frac{1}{4}, frac{17}{16}right)$.

• Тогда $p = x_0 — pi = left( -frac{1}{4}, frac{1}{16}, -frac{1}{8}right), ;; beta = p^T pi = frac{17}{128}$

Домашнее задание 3

1. Найти $pi_S (y) = pi​$, если $S = {x in mathbb{R}^n mid c^T x ge b }​$

2. Найти $pi_S (y) = pi$, если $S = {x in mathbb{R}^n mid x = x_0 + X alpha, X in mathbb{R}^{n times m}, alpha in mathbb{R}^{m}}$, $y notin S$

3. Построить гиперплоскость, разделяющую $S_1$ и $S_2$:
   $$S_1 = left{ x in mathbb{R}^n mid x_1^2 + x_2^2 + ldots + x_n^2 le 1right}, ;;; S_2 = left{ x in mathbb{R}^n mid x_1^2 + x_2^2 + ldots + x_{n-1}^2 + 1 le x_n right}$$

4. Построить опорную гиперплоскость для множества $S = left{ x in mathbb{R}^3 mid frac{x_1^2}{4}+frac{x_2^2}{8}+frac{x_3^2}{25} le 1 right}$ в граничной точке $x_0 = left(-1, frac{12}{5}, frac{sqrt{3}}{2}right)$

5. Пусть $S subset mathbb{R}^n$ — замкнутое выпуклое множество, $mathbf{x} in S$. Найти множество $Y subset mathbb{R}^n$ такое, что $forall mathbf{y} in Y$ выполнено $mathbf{x} = pi_S(mathbf{y})$

6. Пусть даны $mathbf{x} in mathbb{R}^n$ и выпуклый конус $K subseteq mathbb{R}^n$. Пусть $Y = mathbf{x} + K$, $mathbf{y} in Y$. Найти множество $X subset mathbb{R}^n,$ такое, что $mathbf{x} in X, forall mathbf{y} in Y: x = pi_X(mathbf{y})$

В качестве решения необходимо предоставить либо:

• .pdf файл, сверстанный с помощью $ LaTeX ​$ с решениями задач
• .ipynb с оформленным решением