2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Задача на выпуклые множества
Сообщение14.06.2018, 22:00 


07/09/17
34
Добрый день,

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

Задача

Пусть $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$ точек.

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

 Профиль  
                  
 
 Re: Задача на выпуклые множества
Сообщение15.06.2018, 00:03 
Заслуженный участник


26/05/14
981
Я бы начал с треугольника на плоскости.

 Профиль  
                  
 
 Re: Задача на выпуклые множества
Сообщение15.06.2018, 00:04 
Заслуженный участник


18/01/15
3075
Во-первых, рассмотрите случай $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$ относительно этого центра тяжести, то полученная фигура всегда целиком содержится в исходной. Пардон.

 Профиль  
                  
 
 Re: Задача на выпуклые множества
Сообщение15.06.2018, 00:54 
Заслуженный участник


10/01/16
2315
vpb в сообщении #1320046 писал(а):
Рассмотрел,

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

 Профиль  
                  
 
 Re: Задача на выпуклые множества
Сообщение15.06.2018, 14:38 


07/09/17
34
DeBill в сообщении #1320050 писал(а):
Однако, его решение проходит и для $k = d+1$ (и, гомотетию, реально, он и сделал относительно центра масс


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

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

 Профиль  
                  
 
 Re: Задача на выпуклые множества
Сообщение15.06.2018, 15:14 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Задача на выпуклые множества
Сообщение15.06.2018, 15:26 


07/09/17
34
slavav в сообщении #1320155 писал(а):
Вам нужны теоремы (Хелли, Каратеодори) которые упоминают размерность.


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

 Профиль  
                  
 
 Re: Задача на выпуклые множества
Сообщение15.06.2018, 15:42 
Аватара пользователя


14/12/17
1471
деревня Инет-Кельмында
Условия намекают на последовательность {$b_i$}, которая либо содержит, либо сходится к решению.

 Профиль  
                  
 
 Re: Задача на выпуклые множества
Сообщение15.06.2018, 22:41 
Заслуженный участник


26/05/14
981
stiv1995 в сообщении #1320160 писал(а):
Ну ладно, спасибо, через Хелли я решил.
Любопытно, как вы это сделали?

 Профиль  
                  
 
 Re: Задача на выпуклые множества
Сообщение25.06.2018, 12:07 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Задача на выпуклые множества
Сообщение25.06.2018, 12:20 
Заслуженный участник


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group