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

23

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

f(L)=E(xTx), гдеx- точка, произвольно выбранная из L.

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

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

Ашвинкумар Б.В.
источник
Ничего не стоит, проблема выглядит сложной. Даже в 3d не очевидно, как это решить.
Сариэль Хар-Пелед
Очевидно ли, как это сделать в 2d оптимально? Конечно, в 2d приближение постоянного множителя неинтересно.
Ашвинкумар Б.В.
Это не очевидно для меня. Аппроксимация постоянным множителем очевидна в любом измерении путем аппроксимации формы эллипсоидом www.math.sc.edu/~howard/Notes/john.pdf. Константа будет зависеть от размера.
Сариэль Хар-Пелед
Меня больше интересует приближение постоянного фактора, где постоянная не зависит от размерности.
Ашвинкумар Б.В.
1
Естественно. Но позвольте мне взять его обратно - даже случай с эллипсоидом не очевиден. Если вы хотите атаковать эту проблему, это будет первая версия для изучения. Интуитивно вы должны решить, какие измерения игнорировать, а какие расширять. Кажется, естественным решением является выпуклая оболочка объединения эллипсоида с другим эллипсоидом, где оси нового эллипсоида либо равны одному параметру r, либо равны другому эллипсоиду.
Сариэль Хар-Пелед

Ответы:

1

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

EJFE=FB2GJ=GB2B2EJJEEEE={x:xTFTFx1}J={x:xTGTGx1}JEEJGTGExJ[x22]=1nTr(GTG)EJJEEEE={x:xTFTFx1} и . Отсюда следует, что (и, следовательно, ) тогда и только тогда, когда является положительной полуопределенной матрицей.J={x:xTGTGx1}JEEJGTGFTF

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

Сашо Николов
источник
0

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

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

f(L)Sd10rLxd(xd/xLd)dxrLvol(L)dxdSSd1rL2vol(L)dSSd1rL2dSSd1rLdS=defg(L),
rLLg(L)rLrK вдоль любого направления. Обратите внимание, что если вдоль некоторого направления меньше, чем , то мы можем сделать его немного больше, скажем, увеличить его на , чтобы уменьшить . Это потому, что мы увеличиваем перечислитель на , меньше, чем коэффициент увеличения знаменателя. Следовательно, мы можем думать о постепенном «деформировании» (путем многократного увеличения объекта и обновления ), чтобы уменьшить значение . Пусть - выпуклый объект в конце. Тогда любая точка наrKg(K)/2ϵg(K)/2rKg(K)g ( K ) K g ( ) g ( ) K K K g ( K ) / 2 K K g ( K ) / 2(rL+ϵ)2rL2=ϵ(2rL+ϵ)g(K)Kg()g()KKK находится на расстоянии от начала координат, т. е. является объединением и шара с радиусом .g(K)/2KKg(K)/2

Действительно, рассмотрим другой выпуклый объект такой, что . Тогда , так как в противном случае мы можем увеличить часть внутри чтобы уменьшить . С другой стороны, , потому что в противном случае, по той же идее, мы можем уменьшить часть вне чтобы уменьшить . Так что есть уникальное оптимальное решение. g ( K ) = g ( K ) K K K K g ( K ) K K K K K g ( K )Kg(K)=g(K)KKKKg(K)KKKKKg(K)

user7852
источник
1
Может быть, я что-то упускаю, но почему объект, сгенерированный таким образом, выпуклый?
mjqxxxx
@mjqxxxx Вы правы. Как я это пропустил ...
user7852
Как насчет следующей идеи: хорошо известно, что выпуклый объект может быть аппроксимирован некоторым эллипсоидом, то есть существует такой эллипсоид , что . Тогда аппроксимирует с приблизительным отношением . Для любого содержащего , . Поэтому, если мы сможем найти оптимальный эллипсоид содержащий , то . Я не знаю , как вычислить . Но я бы предположил, что его оси совпадают с осями и всеми собственными значениямиE KK EKе(EKKdEKf(K)dLKf(dEK)f(K)dLKЕdEKdELEf(E)d2f(L)EdEKf(E)d2f(L)EdEKdEK ниже некоторого порога повышаются до этого порога.
user7852
Я согласен, что если L не ограничено выпуклым телом, это объединение K и шара.
Ashwinkumar BV
Идея использования эллипсоида не даст вам постоянного фактора. В лучшем случае он может дать приближение. Моя гипотеза состоит в том, что выпуклая оболочка с шаром соответствующего радиуса является приближением с постоянным множителем. Я не уверен, как доказать или опровергнуть гипотезу. лdL
Ashwinkumar BV
0

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

Гипотеза : ожидание выпуклой функции на меньше, чем больше между ожиданием на и ожиданием на .K K conv(KK)KK

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

Теперь возьмем любое множество и примените к нему вращение с центром в начале координат, получив . Вы будете иметь , потому что вращение оставляет длину элементов инвариантной. Если я прав насчет гипотезы, . Так как для любого оптимального вы можете рассмотреть , где указывает объединение по всем поворотам, и иметь , может показаться, что оптимальный можно выбрать как наименьшую сферу, содержащуюKRR(K)f(K)=f(R(K))Kf(conv(KR(K)))f(K)LL=RR(L)=conv(RR(L))Rf(L)f(L)f(L)LK,

Marco
источник
Было бы достаточно доказать, что для ожидания выпуклой функции. Это кажется простым. Econv(A)EAEKKmax{EK,EK}
Марко
4
Я не совсем уверен, что получу ваш ответ. Но это определенно неверно, что L можно выбрать как наименьшую сферу, содержащую K. Рассмотрим длинный тонкий цилиндр с размерами длины . Тогда любая сфера содержащая должна иметь . Но если вы построите где U - сфера или радиус примерно вы получите примерно . (где - константы)t S K f ( S ) t L = c o n v ( K U ) c 1 t / d f ( L ) c 2 t / d c 1 , c 2dtSKf(S)tL=conv(KU)c1t/df(L)c2t/dc1,c2
Ashwinkumar BV