Pertimbangkan benda cembung K yang
f ( L ) = E ( √x T ⋅ x )
Saya baik-baik saja dengan perkiraan faktor konstan terhadap ukuran.
Beberapa catatan - Tebakan intuitif pertama bahwa itu sendiri adalah jawabannya salah. Sebagai contoh, anggap sebagai silinder tipis dalam dimensi yang sangat tinggi. Kemudian kita bisa mendapatkan sedemikian rupa sehingga dengan membiarkan memiliki volume yang lebih dekat ke asalnya.K K L f ( L ) < f ( K ) L
cg.comp-geom
approximation
convex-geometry
Ashwinkumar BV
sumber
sumber
Jawaban:
Jika kami membatasi K dan L sebagai ellipsoid, maka masalah Anda dapat diselesaikan dengan akurasi dengan SDP. Saya tahu ini bukan yang Anda tanyakan pada awalnya, tetapi sepertinya kami tidak memiliki solusi bahkan untuk kasus terbatas ini, dan mungkin ini dapat membantu secara umum.K L
Jadi katakanlah E adalah input ellipsoid dan kami mencari untuk menemukan ellipsoid J yang optimal . Terdapat peta linear F st E = F B 2 dan peta G st J = G B 2 , di mana B 2 adalah bola satuan. Kemudian E x ∼ J [ ‖ x ‖ 2 2 ] = 1E J F E=FB2 G J=GB2 B2 n Tr(GTG). JugaE⊆J⇔J∘⊆E∘, di manaE∘adalahbadan kutubdariE. Dengan mudah,E∘={x:xTFTFx≤1}danJ∘={x:xTGTGx≤1}Ex∼J[∥x∥22]=1nTr(GTG) E⊆J⇔J∘⊆E∘ E∘ E E∘={x:xTFTFx≤1} J∘={x:xTGTGx≤1} . Ini mengikuti bahwa J ∘ ⊆ E ∘ (dan karenanya E ⊆ J ) jika dan hanya jika G T G - F T F adalah matriks semidefinit positif.J∘⊆E∘ E⊆J GTG−FTF
Jadi SDP didefinisikan oleh: diberi simetris PSD matriks M , menemukan matriks PSD simetris N st N - M adalah PSD dan T r ( N ) diminimalkan. N dapat ditemukan dengan memecahkan SDP dan kemudian sebuah SVD akan memberikan sumbu dan sumbu panjang J .M N N−M Tr(N) N J
sumber
(Seperti yang disebutkan dalam komentar, pendekatan berikut tidak bekerja. Objek yang diperoleh tidak cembung. Ini mencirikan objek "berbentuk bintang" dengan jarak minimum yang diharapkan.)
Saya pikir objek yang optimal adalah penyatuan K dan beberapa bola berpusat pada titik asal. Inilah pikiran saya. Menurut definisi Anda tentang f ( L ) , f ( L ) ∼ ∫ S d - 1 ∫ r L 0 x d ( x d / x d L )K f(L) d x rLv o l ( L ) dxdS∼∫ S d-1r 2 Lv o l ( L ) dS∼∫ S d - 1 r 2 L dS∫ S d - 1 r L d S d e f = g(L), di
manarLadalah jarak dari titik asal ke permukaanLsepanjang arah tertentu. Saya menggunakan∼bukannya =, karena saya menjatuhkan beberapa konstanta. Sekarang kita ingin meminimalkang(L)di bawah kendala yangrL≥rKbersama segala arah. Perhatikan bahwa jikarKbersama beberapa arah lebih kecil darig(
Memang, pertimbangkan objek cembung lain K ′ sehingga g ( K ′ ) = g ( K ) . Kemudian K ∗ ⊆ K ′ , karena jika tidak kita dapat menumbuhkan bagian K ′ di dalam K ∗ untuk membuat g ( K ′ ) lebih kecil. Di sisi lain, K ′ ⊆ K ∗ , karena jika tidak, dengan ide yang sama, kita dapat mengecilkan bagian dari K ′ ∖ K di luar K ∗K′ g(K′)=g(K) K∗⊆K′ K′ K∗ g(K′) K′⊆K∗ K′∖K K∗ to make g(K′)g(K′) smaller.
So there is a unique optimal solution.
sumber
The following solution is based on the this assumpotion/conjecture [to be proved]:
Conjecture: The expectation of a convex function on conv(K⋃K′) is smaller than the larger between the expectation on K and the expectation on K′.
[We will need the above only for K,K′ convex, but is might be true in general]
Take now any set K and apply a rotation R to it centered on the origin, obtaining R(K). You are going to have f(K)=f(R(K)), because the rotation leaves the length of the elements of K invariant. If I am right about the conjecture, f(conv(K⋃R(K)))≤f(K). Since for any optimal L you could consider L′=⋃RR(L)=conv(⋃RR(L)), where ⋃R indicates the union over all rotations, and have f(L)≥f(L′)≥f(L), it would seem that the optimal L can be chosen to be the smallest sphere containing K.
sumber