Conjugate (dual) set

Пусть - произвольное непустое множество. Тогда cопряженное к нему множество определяется, как:

Double conjugate set

Множество называется вторым сопряженным к множеству , если:

Inter-conjugate and self-conjugate sets

  • Множества и называются взаимосопряженными, если .
  • Множество называется самосопряженным, если

Properties

  • Сопряженное множество всегда замкнуто, выпукло и содержит нуль.
  • Для произвольного множества :

  • Если , то
  • Если - замкнуто, выпукло, включает , то

Examples

1

Доказать, что

Решение:

  • Пусть и . Тогда в силу непрерывности функции , имеем: . Значит, , отсюда

2

Доказать, что

Решение:

  • Пусть , , т.е. .

    Значит, . Значит, , отсюда

3

Доказать, что если - шар радиуса по некоторой норме с центром в нуле, то

Решение:

  • Пусть . Возьмем вектор нормали , тогда для любого
  • Из всех точек шара возьмем такую , что скалярное произведение её на : было бы минимально, тогда это точка

    Значит,

  • Теперь пусть . Нам надо показать, что , т.е. . Достаточно применить неравенство Коши - Буняковского:

    Последнее исходит из того, что , а

    Значит,

Dual cones

Сопряженным конусом к конусу называется такое множество , что:

Чтобы показать, что это определение непосредственно следует из теории выше вспомним, что такое сопряженное множество и что такое конус

Dual cones properties

  • Если - замкнутый выпуклый конус. Тогда
  • Для произвольного множества и конуса :

  • Пусть - конусы в , тогда:

  • Пусть - конусы в . Пусть так же, их пересечение имеет внутреннюю точку, тогда:

Examples

Найти сопряженнй конус для монотонного неотрицательного конуса:

Решение:

Заметим, что:

Так как в представленной сумме в каждом слагаемом второй множитель положительный, то:

Значит,

Polyhedra

Множество решений системы линейных неравенств и равенств представляет собой многогранник:

Здесь , а неравенство - поэлементное.

Теорема:

Пусть . Сопряженным к многогранному множеству:

является полиэдр (многогранник):

Доказательство:

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

    Значит,

  • Пусть, напротив, . Для любой точки :

    Значит:

    Значит,

5

Найти и изобразить на плоскости множество, сопряженное к многогранному конусу:

Решение:

Используя теорему выше:

Лемма (теорема) Фаркаша (Фаркаша - Минковского)

Пусть . Тогда имеет решение одна и только одна из следующих двух систем:

при означает, что лежит в конусе, натянутым на столбцы матрицы

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

Следствие:

Пусть . Тогда имеет решение одна и только одна из следующих двух систем:

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