Corps convexe avec norme l2 minimale attendue

Considérons un corps convexe centré à l'origine et symétrique (ie si alors ). Je souhaite trouver un corps convexe différent tel que et la mesure suivante soit minimisée:$K$$x\in K$$-x\in K$$L$$K\subseteq L$

$f(L)=\mathbb{E}(\sqrt{x^T \cdot x})$ , où est un point choisi uniformément au hasard parmi L.$x$

Je suis d'accord avec l'approximation à facteur constant de la mesure.

Quelques notes - La première supposition intuitive que lui-même est la réponse est fausse. Par exemple, considérons comme un cylindre mince de très grande dimension. On peut alors obtenir tel que en laissant avoir plus de volume près de l'origine.$K$$K$$L$$f(L)<f(K)$$L$

Si nous limitons et à la fois des ellipsoïdes, votre problème peut être résolu avec une précision quelconque avec un SDP. Je sais que ce n'est pas ce que vous avez demandé à l'origine, mais il semble que nous n'ayons pas de solution même pour ce cas restreint, et cela peut peut-être aider en général.$K$$L$

Alors disons que est l'ellipsoïde d'entrée et nous cherchons à trouver un optimal renfermant ellipsoïde . Il existe une carte linéaire st et une carte st , où est la balle unitaire. Alors . Aussi , où est le corps polaire d' . Idéalement, et . Il s'ensuit que$E$$J$$F$$E = FB_2$$G$$J = GB_2$$B_2$$\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$ (et donc ) si et seulement si est une matrice semi-définie positive.$E \subseteq J$$G^TG - F^TF$

Donc, le SDP est défini par: étant donné une matrice PSD symétrique , trouver une matrice PSD symétrique st est PSD et est minimisé. peut être trouvé en résolvant le SDP et un SVD donnera les axes et axes de longueurs .$M$$N$$N - M$$\mathsf{Tr}(N)$$N$$J$

(Comme mentionné dans les commentaires, l'approche suivante ne fonctionne pas. L'objet obtenu n'est pas convexe. Il caractérise cependant un objet "en forme d'étoile" avec la distance minimale attendue.)

Je pense que l'objet optimal serait une union de et d'une boule centrée à l'origine. Voici mes pensées. Par votre définition de , où est la distance entre l'origine et la surface de dans une direction particulière. J'ai utilisé au lieu de =, car j'ai laissé tomber certaines constantes. Maintenant, nous voulons minimiser sous les contraintes$K$$f(L)$

$$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$ dans n'importe quelle direction. Notez que si dans une certaine direction est plus petit que , alors nous pouvons le rendre légèrement plus grand, disons l'augmenter de , pour faire plus petit. En effet, nous l'énumérateur de , moins d'un facteur de l'augmentation du dénominateur. Par conséquent, nous pouvons penser à "déformer" progressivement (en augmentant légèrement à plusieurs reprises l'objet et en mettant à jour ) pour réduire sa valeur . Soit l'objet final convexe. Ensuite, tout point sur$r_K$$g(K)/2$$\epsilon \le g(K)/2 -r_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$ est à la distance de l'origine, c'est-à-dire que est l'union de et d'une boule de rayon .$g(K^*)/2$$K^*$$K$$g(K^*)/2$

En effet, considérons un autre objet convexe tel que . Puis , car sinon nous pouvons agrandir la partie de à intérieur de pour rendre plus petit. En revanche, , car sinon, par la même idée, on peut réduire la partie de dehors de pour rendre plus petit. Il existe donc une solution optimale unique.$K'$$g(K') = g(K)$$K^*\subseteq K'$$K'$$K^*$$g(K')$$K'\subseteq K^*$$K'\setminus K$$K^*$$g(K')$

La solution suivante est basée sur cette hypothèse / conjecture [à prouver]:

Conjecture : L'attente d'une fonction convexe sur est plus petite que la plus grande entre l'attente sur et l'attente sur .$\textrm{conv}(K\bigcup K')$$K$$K'$

[Nous aurons besoin de ce qui précède uniquement pour convexe, mais cela pourrait être vrai en général]$K,K'$

Prenez maintenant n'importe quel ensemble et appliquez-lui une rotation centrée sur l'origine, obtenant . Vous allez avoir , car la rotation laisse la longueur des éléments de invariante. Si j'ai raison sur la conjecture, . Puisque pour tout optimal, vous pouvez considérer , où indique l'union sur toutes les rotations, et avoir , il semblerait que le optimal puisse être choisi pour être la plus petite sphère contenant$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$.