Considere um corpo convexo centrado na origem e simétrico (ou seja, se então ). Desejo encontrar um corpo convexo diferente tal que e a seguinte medida seja minimizada:
x , onde é um ponto escolhido uniformemente aleatoriamente em L.
Eu estou bem com a aproximação constante do fator à medida.
Algumas notas - O primeiro palpite intuitivo de que é a resposta está errada. Por exemplo, considere um cilindro fino em dimensão muito alta. Então podemos obter tal que deixando ter mais volume próximo da origem.
cg.comp-geom
approximation
convex-geometry
Ashwinkumar BV
fonte
fonte
Respostas:
Se restringirmos e a serem ambos elipsóides, seu problema poderá ser resolvido com precisão com um SDP. Sei que não foi o que você pediu originalmente, mas parece que não temos solução, mesmo para este caso restrito, e talvez possa ajudar em geral.LK L
Então, digamos que é o elipsóide de entrada e estamos procurando encontrar um elipsóide ótimo . Existe um mapa linear st e um mapa st , onde é a bola unitária. Então . Também , onde é o corpo polar de . Convenientemente, e . Segue queJ F E = F B 2 G J = G B 2 B 2 E x ∼ J [ ″ x ² 2 2 ] = 1E J F E=FB2 G J=GB2 B2 E⊆J⇔J∘⊆E∘E∘EE∘={x:xTFTFx≤1}J∘={x:xTLTLx≤1}J∘⊆E∘E⊆JLTLEx∼J[∥x∥22]=1nTr(GTG) E⊆J⇔J∘⊆E∘ E∘ E E∘={x:xTFTFx≤1} J∘={x:xTGTGx≤1} J∘⊆E∘ (e, portanto, ) se e somente se for uma matriz semidefinida positiva.E⊆J GTG−FTF
Portanto, o SDP é definido por: dada uma matriz PSD simétrica , encontre uma matriz PSD simétrica st é PSD e é minimizado. pode ser encontrado através da resolução de SDP e, em seguida, uma SVD dará os eixos e eixos de comprimentos .N N - M T r ( N ) N JM N N−M Tr(N) N J
fonte
(Conforme mencionado nos comentários, a seguinte abordagem não funciona. O objeto obtido não é convexo. No entanto, caracteriza um objeto "em forma de estrela" com a distância mínima esperada.)
Eu acho que o objeto ideal seria uma união de e alguma bola centrada na origem. Aqui estão os meus pensamentos. Pela sua definição de , que é a distância da origem à superfície de ao longo de uma direção específica. Eu usei vez de =, porque deixei cair algumas constantes. Agora queremos minimizar sob as restrições quef ( L ) f ( G ) ~ ∫ S d - 1 ∫ R G 0 x d ( x d / x d L )K f(L) RLL~g(G)rL≥rKrKg(K)/2£≤g(K)/2-rKg(K)(rL+ϵ)2
De fato, considere outro objeto convexo tal que . Então , pois caso contrário, podemos aumentar a parte de dentro de para tornar menor. Por outro lado, , porque, caso contrário, pela mesma idéia, podemos reduzir a parte de fora de para tornar menor. Portanto, existe uma solução ideal exclusiva. g ( K ′ ) = g ( K ) K ∗ ⊆ K ′ K ′ K ∗ g ( K ′ )K′ g(K′)=g(K) K∗⊆K′ K′ K∗ g(K′) K ' ∖ K K * g ( K ' )K′⊆K∗ K′∖K K∗ g(K′)
fonte
A seguinte solução é baseada nesta premissa / conjectura [a ser comprovada]:
Conjectura : A expectativa de uma função convexa em é menor que a maior entre a expectativa em e a expectativa em .K K ′conv(K⋃K′) K K′
[Vamos precisar do acima exposto apenas para convexo, mas isso pode ser verdade em geral]K,K′
Pegue agora qualquer conjunto e aplique uma rotação centrada na origem, obtendo . Você terá , porque a rotação deixa o comprimento dos elementos de invariáveis. Se estou certo sobre a conjectura, . Como para qualquer ideal, você pode considerar , onde indica a união em todas as rotações e possui , parece que o ideal pode ser escolhido para ser a menor esfera contendoR 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 ( LK R R(K) f(K)=f(R(K)) K f(conv(K⋃R(K)))≤f(K) L L′=⋃RR(L)=conv(⋃RR(L)) ⋃R f(L)≥f(L′)≥f(L) L K .
fonte