Выпуклые оболочки множеств и функций

В ряде случаев наряду со значениями х е М требуется включить в рассмотрение и все те значениях, которые могут быть получены из элементов множества М посредством операции усреднения. Ясно, что для выпуклого множества такое расширение эквивалентно, т. е. новых элементов, кроме тех, которые принадлежали М, при этом не добавится. Ведь по определению любой результат усреднения также принадлежит М. Иначе дело обстоит, если М не выпукло. Тогда в результате подобного расширения мы получим множество СоМ, включающее в себя М и еще некоторые элементы Е^п, не принадлежащие М. Множество СоМ называют выпуклой оболочкой М. Для выпуклого множества СоМ и М совпадают.

Определения. 1. Выпуклой оболочкой множества М называют множество, любой элемент которого может быть получен из элементов М посредством операции усреднения.

Формально у е СоМ, если найдутся такие х^[1] е Ми такие веса у_г, что.

• 2. Выпуклой оболочкой множества М называется минимальное выпуклое множество, включающее М, т. е. такое, что:
  • а) любой элемент М принадлежит СоМ;
  • б) изъятие из множества СоМ любого элемента превращает его в невыпуклое.

На рис. 2.5 показаны примеры множеств и их выпуклых оболочек.

Рис. 2.5. Примеры выпуклых оболочек множеств.

В формуле (2.6) не проставлено число слагаемых в правой части. Между тем важно знать, какое минимальное число элементов М необходимо иметь в этом выражении, чтобы получить любой элемент выпуклой оболочки. Ответ на этот вопрос дает теорема Каратеодори^[1]: для получения любого элемента выпуклой оболочки множества М, принадлежащего линейному векторному пространству размерности п, требуется усреднять не более (п + 1)-го элемента М. Таким образом, индекс i в правой части равенства (2.6) должен меняться от нуля до п.

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

Определения.

• 1. Выпуклой оболочкой функции fix), определенной на множестве х е е V^, называют минимальную выпуклую функцию, не меньшую, чем fix), Vx е V_x.
• 2. Выпуклой оболочкой функции на множестве V_x называют верхнюю границу выпуклой оболочки «подграфика».

Обозначают выпуклую оболочку функции как Co_Vxf (х).

Оба эти определения не конструктивны, т. е. не дают способа построить выпуклую оболочку функции. В этом смысле удобнее третье определение.

3. Функция Fix) называется выпуклой оболочкой fix) на V# если для любого х ее значение может быть получено как решение следующей задачи:

Из (2.7) следует, что при среднем значении аргумента, равному, максимум среднего значения функции fix) равен ординате выпуклой оболочки функции для среднего значения х, равного у (х = у).

Прокомментируем эти определения.

Прежде всего из неравенства (2.3) следует, что для выпуклой функции все у, кроме у₀, равны нулю, у₀ = 1, a Co_Vxfix) = fix), так как любое усреднение только уменьшает значение функции.

Число слагаемых в выражении (2.7) равно (п + 1), причем предполагается, что х g М^п. На первый взгляд, нужно было бы использовать (п + 2) слагаемых, ведь размерность «подграфика» на единицу больше размерности множества V_x и равна (п + 1). Дело, однако, заключается в том, что нам нужно использовать не любые элементы «подграфика», а лишь те, которые лежат на его верхней границе, размерность же множества таких элементов равна п. Например, на плоскости (п = 2) размерность верхней границы «подграфика» т. е. линии/(х), равна единице.

И последнее, множество V_x в (2.7) может быть и не выпуклым, ведь множество значений х, для которых определена Co_Vxfix), представляет собой выпуклую оболочку V_x (х = ?у, х') (см. рис. 2.3, б).

Не следует думать, что на тех участках, где Co_Vxfix) не совпадает с fix), она представляет собой плоскость. Это так лишь для п = 1. Для п = 2 функция fix) представляет собой поверхность в трехмерном пространстве. Пусть эта поверхность — винтообразная лента (рис. 2.6, а). Тогда выпуклая оболочка этой функции — круговой цилиндр. Другой пример, когда множество V_x — отдельные точки на плоскости. Тогда выпуклая оболочка Дх) представляет собой выпуклую комбинацию кусков плоскостей (рис. 2.6, б).

Рис. 2.6. Выпуклая оболочка винтообразной ленты (а) и функции, определенной в изолированных точках (б).

Пусть требуется при заданном среднем расходе энергии агрегатом х обеспечить максимум его средней производительности. Легко показать, что зависимость максимально возможной средней производительности / от среднего расхода энергии х совпадает с графиком выпуклой оболочки функции fix). При этом расход энергии меняется так, что в течение доли у, от продолжительности цикла он равен х_{.

• [1] Цирлин А. М. Методы усредненной оптимизации и их приложения. М.: Наука ;Физматлит, 1997.
• [2] Цирлин А. М. Методы усредненной оптимизации и их приложения. М.: Наука ;Физматлит, 1997.