Wypukły korpus z minimalną oczekiwaną normą l2

23

Rozważmy wypukłe ciało wyśrodkowane na początku i symetryczne (tj. Jeśli to ). Chcę znaleźć inne ciało wypukłe tak aby i następująca miara zostały zminimalizowane:x K - x K L K L.KxKxKLKL

xf(L)=E(xTx) , gdzie jest punktem losowo wybranym losowo z L.x

Nic mi nie jest ze stałym przybliżeniem współczynnika do miary.

Kilka uwag - Pierwsze intuicyjne przypuszczenie, że sama jest odpowiedzią, jest złe. Na przykład należy uważać za cienki cylinder o bardzo dużych wymiarach. Następnie możemy uzyskać tak, że , pozwalając mieć większą objętość zbliżoną do źródła.K L f ( L ) < f ( K ) LKKLf(L)<f(K)L

Ashwinkumar BV
źródło
Mimo że nic nie jest warte, problem wygląda na trudny. Nawet w 3D nie jest oczywiste, jak to rozwiązać.
Sariel Har-Peled
Czy to oczywiste, jak zrobić to optymalnie w 2D? Oczywiście w 2d stałe przybliżenie współczynnika jest nieciekawe.
Ashwinkumar BV
To nie jest dla mnie oczywiste. Przybliżenie współczynnika stałego jest oczywiste w każdym wymiarze poprzez przybliżenie kształtu przez elipsoidę www.math.sc.edu/~howard/Notes/john.pdf. Stała zależałaby od wymiaru.
Sariel Har-Peled
Bardziej interesuje mnie przybliżenie współczynnika stałego, gdy stała nie zależy od wymiaru.
Ashwinkumar BV
1
Naturalnie. Ale pozwolę sobie to cofnąć - nawet obudowa elipsoidy nie jest oczywista. Jeśli chcesz zaatakować ten problem, byłaby to pierwsza wersja do zbadania. Intuicyjnie musisz zdecydować, które wymiary zignorować, a które rozszerzyć. Wydaje się, że naturalnym rozwiązaniem jest wypukły kadłub połączenia elipsoidy z inną elipsoidą, gdzie osie nowej elipsoidy są albo równe jakiemuś parametrowi r, albo są równe drugiej elipsoidzie.
Sariel Har-Peled

Odpowiedzi:

1

Jeśli ograniczymy i do obu elipsoid, problem można rozwiązać z dowolną dokładnością za pomocą SDP. Wiem, że nie o to pytałeś pierwotnie, ale wydaje się, że nie mamy rozwiązania nawet w tej ograniczonej sprawie i być może może to w ogóle pomóc.L.KL

Więc powiedzmy, że jest elipsoida wejście i szukamy aby znaleźć optymalną otaczającą elipsoidy . Istnieje mapa liniowa st i mapa st , gdzie jest kulą jednostkową. Następnie . Ponadto , gdzie jest korpus polarny z . Dogodnie i . Wynika, żeEJFE=FB2GJ=GB2B2EJJEEEE={x:xTFTFx1}J={x:xTGTGx1}JEEJGTGExJ[x22]=1nTr(GTG)EJJEEEE={x:xTFTFx1}J={x:xTGTGx1}JE (a zatem ) wtedy i tylko wtedy, gdy jest dodatnią macierzą półfinałową.EJGTGFTF

Zatem SDP jest zdefiniowany przez: biorąc pod uwagę symetryczną macierz PSD , znajdź symetryczną macierz PSD st oznacza PSD i jest zminimalizowane. można znaleźć rozwiązując SDP i wówczas SVD da osi i osi długości .N N - M T r ( N ) N JMNNMTr(N)NJ

Sasho Nikolov
źródło
0

(Jak wspomniano w komentarzach, następujące podejście nie działa. Uzyskany obiekt nie jest wypukły. Charakteryzuje on obiekt w kształcie gwiazdy o minimalnej oczekiwanej odległości.)

Myślę, że optymalnym obiektem byłoby połączenie i trochę piłki wycentrowanej na początku. Oto moje przemyślenia. Według twojej definicji , gdzie to odległość od początku do powierzchni wzdłuż określonego kierunku. Użyłem zamiast =, ponieważ upuściłem niektóre stałe. Teraz chcemy zminimalizować pod ograniczeniami, któref ( L ) f ( L ) S d - 1r L 0 x d ( x d / x d L )Kf(L)rLLg(L)rLrKrKg(K)/2ϵg(K)/2-rKg(K)(rL+ϵ)2

f(L)Sd10rLxd(xd/xLd)dxrLvol(L)dxdSSd1rL2vol(L)dSSd1rL2dSSd1rLdS=defg(L),
rLLg(L)rLrK wzdłuż dowolnego kierunku. Zauważ, że jeśli wzdłuż jakiegoś kierunku jest mniejszy niż , możemy go nieco zwiększyć, powiedzmy, zwiększ go o , aby . Jest tak, ponieważ zwiększamy wyliczający o , mniej niż współczynnik wzrostu mianownika. Dlatego możemy myśleć o stopniowym „deformowaniu” (poprzez kilkakrotne nieznaczne powiększanie obiektu i aktualizowanie ), aby zmniejszyć jego wartość . Niech będzie na końcu obiektem wypukłym. Następnie w dowolnym momencierKg(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 znajduje się w odległości od początku, tj. to suma i piłki o promieniu .g(K)/2KKg(K)/2

Rzeczywiście, rozważ inny wypukły obiekt taki, że . Następnie , ponieważ w przeciwnym razie możemy zwiększyć część wewnątrz aby zmniejszyć . Z drugiej strony, , ponieważ w innym przypadku, według tego samego pomysłu, możemy zmniejszyć część poza aby zmniejszyć . Istnieje więc unikalne optymalne rozwiązanie. g ( K ) = g ( K ) K K Kg(K)=g(K)KKK g ( K ) K K K K K g ( K )KKg(K)KKKKKg(K)

użytkownik7852
źródło
1
Może czegoś mi brakuje, ale dlaczego obiekt jest w ten sposób wypukły?
mjqxxxx,
@mjqxxxx Masz rację. Jak mi tego brakowało ...
user7852
A co z następującym pomysłem: dobrze wiadomo, że wypukły obiekt może być aproksymowany przez jakąś elipsoidę, tj. Istnieje elipsoida taka, że . Następnie aproksymuje o przybliżonym stosunku . Dla dowolnego zawierającego , . Jeśli więc znajdziemy optymalną elipsoidę zawierającą , to . Nie wiem, jak obliczyć . Ale zgaduję, że jego osie są wyrównane z osiami i wszystkimi wartościami własnymiE KK EKf(EKKdEKf(K)dLKf(dEK)f(K)dLKdEKdELEf(E)d2f(L)EdEKf(E)d2f(L)EdEKdEK poniżej pewnego progu jest podnoszony do tego progu.
user7852
Zgadzam się, że jeśli L nie jest ograniczony do ciała wypukłego, to jest to połączenie K i piłki.
Ashwinkumar BV
Pomysł użycia elipsoidy nie da ci stałego czynnika. W najlepszym wypadku może dać przybliżenie . Moje przypuszczenie jest takie, że wypukły kadłub z kulą o odpowiednim promieniu jest stałym przybliżeniem współczynnika. Nie jestem pewien, jak udowodnić lub obalić przypuszczenie. L.dL
Ashwinkumar BV
0

Poniższe rozwiązanie opiera się na założeniu / przypuszczeniu [do udowodnienia]:

Przypuszczenie : oczekiwanie funkcji wypukłej na jest mniejsze niż większe między oczekiwaniem na i oczekiwaniem na .K K conv(KK)KK

[Będziemy potrzebować powyższego tylko dla wypukłych , ale może to być prawda]K,K

Weź teraz dowolny zestaw i zastosuj do niego obrót wyśrodkowany na początku, uzyskując . Będziesz miał , ponieważ obrót pozostawia długość elementów niezmiennikaJeśli mam rację co do przypuszczenia, . Ponieważ dla każdego optymalnego można rozważyć , gdzie oznacza we wszystkich obrotach i ma , wydaje się, że optymalne można wybrać jako najmniejszą kulę zawierającąR R ( K ) f ( K ) = f ( R ( K ) ) K f ( conv ( K R ( K ) ) ) f ( K ) L L = R R ( L ) = conv ( R R ( L ) ) R f ( LKRR(K)f(K)=f(R(K))Kf(conv(KR(K)))f(K)LL=RR(L)=conv(RR(L))RL Kf(L)f(L)f(L)LK.

Marco
źródło
Wystarczy udowodnić, że na oczekiwanie funkcji wypukłej. To, że wydaje się łatwe. E K K max{ E K , E K }Econv(A)EAEKKmax{EK,EK}
Marco
4
Nie jestem do końca pewien, czy otrzymam twoją odpowiedź. Ale zdecydowanie nie jest prawdą, że L można wybrać jako najmniejszą kulę zawierającą K. Rozważ długi cienki walec o wymiarach długości . Wtedy każda kula zawierająca powinna mieć . Ale jeśli gdzie U jest kulą lub promieniem mniej więcej , otrzymasz grubsza . (gdzie są stałymi)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