Выпуклое тело с минимальной ожидаемой нормой l2

Рассмотрим выпуклое тело $K$ центром в начале координат и симметричное (т. Е. Если $x\in K$ то $-x\in K$ ). Я хочу найти другое выпуклое тело $L$ такое, что $K\subseteq L$ и следующая мера минимизируется:

$f(L)=\mathbb{E}(\sqrt{x^T \cdot x})$, где$x$- точка, произвольно выбранная из L.

Я в порядке с постоянным коэффициентом приближения к мере.

Некоторые примечания - Первое интуитивное предположение, что сам $K$ является ответом, неверно. Например, рассмотрим $K$ как тонкий цилиндр с очень большими размерами. Тогда мы можем получить $L$ такой, что $f(L)<f(K)$ , позволяя $L$ иметь больший объем, близкий к началу координат.

Если мы ограничим и L обоими эллипсоидами, то ваша проблема может быть решена с любой точностью с помощью SDP. Я знаю, что это не то, что вы просили изначально, но, похоже, у нас нет решения даже для этого ограниченного случая, и, возможно, это может помочь в целом.$K$$L$

$E$$J$$F$$E = FB_2$$G$$J = GB_2$$B_2$E⊆J⇔J∘⊆E∘E∘EE∘={x:xTFTFx≤1}J∘={x:xTGTGx≤1}J∘⊆E∘E⊆JGT$\mathbb{E}_{x \sim J}[\|x\|_2^2] = \frac{1}{n}\mathsf{Tr}(G^TG)$$E \subseteq J \Leftrightarrow J^\circ \subseteq E^\circ$$E^\circ$$E$$E^\circ = \{x: x^TF^TFx \leq 1\}$ и . Отсюда следует, что (и, следовательно, ) тогда и только тогда, когда является положительной полуопределенной матрицей.$J^\circ = \{x: x^TG^TGx \leq 1\}$$J^\circ \subseteq E^\circ$$E \subseteq J$$G^TG - F^TF$

Таким образом, SDP определяется следующим образом: при заданной симметричной матрице PSD найти симметричную матрицу PSD st равно PSD, а минимизируется. может быть найден путем решения SDP и затем СВДА дадут ось и ось длину .N N - M T r ( N ) N $M$$N$$N - M$$\mathsf{Tr}(N)$$N$$J$

(Как уже упоминалось в комментариях, следующий подход не работает. Полученный объект не является выпуклым. Хотя он характеризует «звездообразный» объект с минимальным ожидаемым расстоянием.)

Я думаю, что оптимальным объектом был бы союз и некоторый шар с центром в начале координат. Вот мои мысли. По вашему определению , где - расстояние от начала координат до поверхности вдоль определенного направления. Я использовал вместо =, потому что я отбросил некоторые константы. Теперь мы хотим минимизировать при ограничениях, которыеF ( L ) F ( L ) ~ ∫ S d - 1 ∫ г л 0 х д ( х д / х д л$K$$f(L)$глл~г(л)гл≥гКгКг(К)/2epsileг(К)/2-гКg(K)(rL+ϵ)

$$f(L) \sim \int_{{\mathbb S}^{d-1}} \int_{0}^{r_L} x\frac{\mathrm{d}(x^d/x_L^d)}{\mathrm dx}\frac{r_L}{\mathrm{vol}(L)} \mathrm dx\mathrm dS \sim \int_{{\mathbb S}^{d-1}} \frac{r_L^2}{\mathrm{vol}(L)}dS \sim \frac{\int_{{\mathbb S}^{d-1}} r_L^2 dS}{\int_{{\mathbb S}^{d-1}} r_L dS} \stackrel{\mathrm{def}}{=} g(L),$$ $r_L$$L$$\sim$$g(L)$$r_L \ge r_K$ вдоль любого направления. Обратите внимание, что если вдоль некоторого направления меньше, чем , то мы можем сделать его немного больше, скажем, увеличить его на , чтобы уменьшить . Это потому, что мы увеличиваем перечислитель на , меньше, чем коэффициент увеличения знаменателя. Следовательно, мы можем думать о постепенном «деформировании» (путем многократного увеличения объекта и обновления ), чтобы уменьшить значение . Пусть - выпуклый объект в конце. Тогда любая точка на$r_K$$g(K)/2$$\epsilon \le g(K)/2 -r_K$$g(K)$g ( K ) K g ( ⋅ ) g ( ⋅ ) K ∗ ∂ K ∗ ∖ ∂ K g ( K ∗ ) / 2 K ∗ K g ( K ∗ ) /$(r_L+\epsilon)^2 -r_L^2 = \epsilon(2r_L + \epsilon)$$g(K)$$K$$g(\cdot)$$g(\cdot)$$K^*$$\partial K^*\setminus \partial K$ находится на расстоянии от начала координат, т. е. является объединением и шара с радиусом .$g(K^*)/2$$K^*$$K$$g(K^*)/2$

Действительно, рассмотрим другой выпуклый объект такой, что . Тогда , так как в противном случае мы можем увеличить часть внутри чтобы уменьшить . С другой стороны, , потому что в противном случае, по той же идее, мы можем уменьшить часть вне чтобы уменьшить . Так что есть уникальное оптимальное решение. g ( K ′ ) = g ( K ) K ∗ ⊆ K ′ K ′ K ∗ g ( K ′ ) K ′ ⊆ K ∗ K ′ ∖ K K ∗ g ( K ′$K'$$g(K') = g(K)$$K^*\subseteq K'$$K'$$K^*$$g(K')$$K'\subseteq K^*$$K'\setminus K$$K^*$$g(K')$

Следующее решение основано на этом предположении / предположении [будет доказано]:

Гипотеза : ожидание выпуклой функции на меньше, чем больше между ожиданием на и ожиданием на .K K $\textrm{conv}(K\bigcup K')$$K$$K'$

[Нам понадобится вышеупомянутое только для выпуклых, но это может быть верно в общем случае]$K,K'$

Теперь возьмем любое множество и примените к нему вращение с центром в начале координат, получив . Вы будете иметь , потому что вращение оставляет длину элементов инвариантной. Если я прав насчет гипотезы, . Так как для любого оптимального вы можете рассмотреть , где указывает объединение по всем поворотам, и иметь , может показаться, что оптимальный можно выбрать как наименьшую сферу, содержащую$K$$R$$R(K)$$f(K)=f(R(K))$$K$$f(\textrm{conv}(K\bigcup R(K)))\leq f(K)$$L$$L'=\bigcup_R R(L)=\textrm{conv}(\bigcup_R R(L))$$\bigcup_R$$f(L)\geq f(L') \geq f(L)$$L$$K$,