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

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 ⊆ $K$$x\in K$$-x\in K$$L$$K\subseteq L$

$f(L)=\mathbb{E}(\sqrt{x^T \cdot x})$ , 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 ) $K$$K$$L$$f(L)<f(K)$$L$

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.$K$$L$

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, że$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$ (a zatem ) wtedy i tylko wtedy, gdy jest dodatnią macierzą półfinałową.$E \subseteq J$$G^TG - F^TF$

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 $M$$N$$N - M$$\mathsf{Tr}(N)$$N$$J$

(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 - 1 ∫ r L 0 x d ( x d / x d L$K$$f(L)$rLL∼g(L)rL≥rKrKg(K)/2ϵ≤g(K)/2-rKg(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$ 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 momencie$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$ znajduje się w odległości od początku, tj. to suma i piłki o promieniu .$g(K^*)/2$$K^*$$K$$g(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 $K'$$g(K') = g(K)$$K^*\subseteq K'$K ∗ g ( K ′ ) K ′ ⊆ K ∗ K ′ ∖ K K ∗ g ( K ′$K'$$K^*$$g(K')$$K'\subseteq K^*$$K'\setminus K$$K^*$$g(K')$

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 $\textrm{conv}(K\bigcup K')$$K$$K'$

[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 ( $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$L $f(L)\geq f(L') \geq f(L)$$L$$K$.