Разделительная и опорная гиперплоскость двух выпуклых множеств

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

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

: , ,

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

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

Теорема 1. Каждая опорная гиперплоскость выпуклого множества S содержит его крайнюю точку.

Теорема 2. Выпуклое множество S является средневзвешенным множеством из его крайних точек.

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

Теорема о минимаксе

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

Теорема. Всякая конечная антагонистическая игра имеет цену, и у каждого игрока существует по меньшей мере одна оптимальная стратегия.

Исходные предпосылки. Пусть — конечная игра, а — смешанное расширение этой игры. При доказательстве теоремы удобно вести рассуждения в терминах S-игры, поэтому через обозначим эквивалентную S-игру.

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

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

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

. (1)

Действительно, если неравенство (1) имеет место, то

. Таким образом, доказательство теоремы будет сводиться к доказательству неравенства (1).

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

Множество T является выпуклым. Рассмотрим произвольные точки и этого множества. Уравнение отрезка, соединяющего эти две точки, будет иметь вид:

, , .

Проектируя это уравнение на i-ую ось и учитывая теорему на стр.14, получаем

(2) Следовательно, любая точка рассматриваемого отрезка принадлежит T и множество T выпуклое.

Множество T не пересекается с множеством . Это следует из того, что любая точка множества имеет по крайней мере одну координату, большую или равную (следствие 1 из теоремы «Если S — произвольная точка m-мерного пространства и — многомерная переменная, то имеет место соотношение , а значит T и не имеют общих точек.

Поскольку T и — выпуклые непересекающиеся области, то существует разделяющая их гиперплоскость такая, что множество T и окажутся в разных полупространствах, определяемых этой гиперплоскостью. Следовательно, существует такое и число c, что уравнение (3) будет уравнением разделяющей гиперплоскости, причем

для ; для . (4)

Покажем, что . Пусть — точка, у которой i-ая координата равна 1, а остальные равны малой величине . Рассмотрим точку . Так как ее максимальная координата равна (следствие 2 из теоремы «Если S — произвольная точка m-мерного пространства и — многомерная переменная, то имеет место соотношение »), то точка . Следовательно,