Задача на выпуклые множества

[stiv1995]

Добрый день,

нашел следующую задачу:

Задача

Пусть $A$ - компактное выпуклое множество в $\mathbb{R}^{d}$. Доказать, что найдется вектор $b \in \mathbb{R}^{d}$ такой, что $b - \frac{1}{d} A \subset A$.

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

Попытки решения

Во-первых, я решил задачу, используя теорему Хелли. Но доказать из первых принципов не получилось. Смог только показать утверждение для $A = \text{conv}\{x_1, \ldots, x_k \}, k \le d$. Конструкция следующая:

Определим вектор $b = \alpha x_1 + \alpha x_2 + \ldots + \alpha x_k $, где $\alpha = \frac{1}{k}(1 + \frac{1}{d}) \ge \frac{1}{d}$. Тогда $\forall x \in A$ имеем

$$b - \frac{1}{d}x = \frac{1}{k} \left(1 + \frac{1}{d}\right) \sum\limits_{i=1}^k x_i - \frac{1}{d} \sum\limits_{i=1}^k \beta_i x_i = \sum\limits_{i=1}^k \left(\frac{1}{k} \left(1 + \frac{1}{d}\right) - \frac{1}{d} \beta_i \right) x_i \in A$$

где $\beta_i \ge 0, \sum\limits_{i=1}^k \beta_i = 1$.

Но такая конструкция не работает, если точек $A$ - выпуклая оболочка более $d$ точек.

Не могли бы вы подсказать направления решения?

[slavav]

Я бы начал с треугольника на плоскости.

[vpb]

Во-первых, рассмотрите случай $d=2$ для начала (дальнейшее будет не сложным обобщением). Во-вторых, в качестве $b$ всегда (а не только для треугольников) можно взять центр тяжести фигуры. Доказательство --- от противного. Для этого, в частности, попробуйте доказать, что если выпуклая фигура на плоскости содержит точку $(1,0)$, и лежит целиком в полуплоскости $x\geq-1/2$, то ее центр тяжести лежит в полуплоскости $x\geq0$. (Теорема Хелли для доказательства этого не нужна, но, видимо, нужен тот факт, что через любую точку вне выпуклой фигуры на плоскости проходит прямая такая, что фигура лежит целиком по одну сторону от прямой (или, возможно, некоторые точки фигуры лежат на самой прямой).)

-- 14.06.2018, 23:11 --

slavav в сообщении #1320045 писал(а):

Я бы начал с треугольника на плоскости

Действительно. Я невнимательно посмотрел, мне показалось, что случай симплекса ТС уже рассмотрел. Ан нет. Рассмотрел, но не $d$-мерного, а $d-1$-мерного.

-- 14.06.2018, 23:24 --

Ч-черт, я кажется вообще написал с ошибками... В общем, ТС, я сейчас тороплюсь, Вы уж поразбирайтесь сами, но в общем примерно так, как я написал. Смысл таков, что если взять центр тяжести исходной фигуры, и выполнить гомотетию с коэффициентом $-1/d$ относительно этого центра тяжести, то полученная фигура всегда целиком содержится в исходной. Пардон.

[DeBill]

vpb в сообщении #1320046 писал(а):

Рассмотрел,

Однако, его решение проходит и для $k = d+1$ (и, гомотетию, реально, он и сделал относительно центра масс)

[stiv1995]

DeBill в сообщении #1320050 писал(а):

Однако, его решение проходит и для $k = d+1$ (и, гомотетию, реально, он и сделал относительно центра масс

Да, для $d$-мерного симплекса задача решена. И про центр масс я тоже подозревал, только не понятно, как это формально показать. Центр масс выражается в общем случае через кратный интеграл, что с этим интегралом делать? Вообще интересно почему для выпуклой комбинации из более чем $d+1$ точки приведенное доказательство не проходит.

Есть еще вот такая идея: рассмотрим $d = 2$. Что если для произвольного выпуклого множества вписать и описать вокруг него треугольники максимальной и минимальной площади соответственно. Можно ли потом показать что внешний треугольник, сжатый в два раза, будет лежать внутри внутреннего треугольника?

[slavav]

Надо искать свойства центра масс выпуклого множества. Проведём через центр масс прямую, рассмотрим её пересечение с нашим множеством - это отрезок. Центр масс не может лежать слишком близко к концу этого отрезка. А степень этого "не может" зависит от размерности пространства. Значит что простыми свойствами выпуклости вы не обойдётесь. Вам нужны теоремы (Хелли, Каратеодори) которые упоминают размерность.

[stiv1995]

slavav в сообщении #1320155 писал(а):

Вам нужны теоремы (Хелли, Каратеодори) которые упоминают размерность.

Странно, тогда не понятно зачем в книге эта задача дана сразу после определения выпуклого множества. Ну ладно, спасибо, через Хелли я решил.

[eugensk]

Условия намекают на последовательность {$b_i$}, которая либо содержит, либо сходится к решению.

[slavav]

stiv1995 в сообщении #1320160 писал(а):

Ну ладно, спасибо, через Хелли я решил.

Любопытно, как вы это сделали?

[DeBill]

Т.е., для симплекса задача решена. Решение ТС в огеометриченном виде выглядит так:
гомотетия с центром в центре масс и к-том $-\frac{1}{d}$ переводит симплекс ("треугольник") внутрь себя (в "серединный треугольник"). Но что делать в общем случае?
Тут один мой коллега выдал замечательную идею. Именно, впишем в заданное выпуклое тело симплекс максимального объема. Из максимальности следует: для каждой его вершины плоскость, параллельная противоположной грани, является касательной (опорной) для тела. Пересечение полупространств, соответствующих этим опорным плоскостям, есть СИМПЛЕКС, подобный максимальному (и содержащий тело). Но тогда та самая гомотетия ТС, построенная по СИМПЛЕКСУ, переведет его в максимальный (а тело - внутрь максимального - который - внутре тела). Победа!
Конечно, нетривиальный вопрос - в существовании максимального. Можно - либо аппроксимировать наше тело изнутри выпуклыми многогранниками (для многогранника макс есть - ибо конечный перебор), и делать предельный переход, либо рассматривать функцию "объем" от $d+1$ аргументов (точек на границе), и ссылаться на теорему Вейерштрасса. Но идея хороша.

[slavav]

Да, это работает. Доказательство не элементарное, но без привлечения Хелли. Спасибо!