Menghasilkan vektor acak dengan kendala

10

Saya perlu membuat vektor acak bilangan real a_i memenuhi batasan berikut:

abs(a_i) < c_i;      
sum(a_i)< A;        # sum of elements smaller than A
sum(b_i * a_i) < B; # weighted sum is smaller than B 
aT*A*a < D          # quadratic multiplication with A smaller than D

where c_i, b_i, A, B, D are constants.

Apa yang akan menjadi algoritma khas untuk menghasilkan vektor jenis ini secara efisien?

random-generation LouisChiffre
sumber
1
Apa yang Anda maksud dengan batasan keempat, "Besarnya adalah ..."
M. Tibbits
Kesalahanku. Deskripsi selesai. Terima kasih untuk umpan baliknya.
LouisChiffre
Bagaimana itu a_imengikuti distribusi p_idan juga kurang dari itu c? Itu karena distribusinya p_ijuga kurang dari itu c? Di distribusi mana Anda berpikir?
deps_stats
@deps_stats. Poin yang sangat bagus. Kode palsu tidak terlalu jelas. Distribusi yang saya pikirkan adalah distribusi poisson. Setiap elemen mengikuti distribusi poisson dengan lambda yang berbeda. Dengan mengingat hal itu saya kira syarat pertama (a_i <c) tidak diperlukan karena saya hanya bisa menskala ulang a_i pada akhir generasi untuk memuaskannya.
LouisChiffre
Izinkan saya bertanya sesuatu yang lain ... Apakah itu c, A, Bdan lambdas tetap?
deps_stats

Jawaban:

4

Jika saya mengerti Anda dengan benar, hanya titik dalam beberapa volume kecil ruang n-dimensi yang memenuhi kendala Anda.

Batasan pertama Anda membatasi ke interior sebuah hypersphere, yang mengingatkan saya pada FAQ comp.graphics.algorithms "Seragam titik acak pada bola" dan Bagaimana cara menghasilkan titik yang terdistribusi secara merata dalam bola unit 3-d? Kendala kedua memotong sedikit keluar dari hypersphere, dan kendala lainnya semakin jauh mengurangi volume yang memenuhi kendala Anda.

Saya pikir hal paling sederhana untuk dilakukan adalah salah satu pendekatan yang disarankan oleh FAQ:

  • pilih beberapa kotak pembatas Axis-aligned sewenang - wenang yang kami yakin berisi seluruh volume. Dalam hal ini, -c <a_1 <c, -c <a_2 <c, ... -c <a_n <c berisi seluruh volume yang dibatasi, karena berisi hypersphere yang dijelaskan oleh kendala pertama, dan kendala lainnya terus mengecil pergi pada volume itu.
  • Algoritme secara seragam memilih titik di seluruh kotak pembatas itu. Dalam hal ini, algoritme secara independen menetapkan setiap koordinat dari vektor kandidat ke beberapa nomor acak yang terdistribusi seragam secara independen dari -c ke + c. (Saya berasumsi Anda ingin titik didistribusikan dengan kepadatan yang sama di seluruh volume ini. Saya kira Anda dapat membuat algoritma memilih beberapa atau semua koordinat dengan distribusi Poisson atau distribusi non-seragam lainnya, jika Anda memiliki alasan untuk melakukan itu).
  • Setelah Anda memiliki vektor kandidat, periksa setiap kendala. Jika gagal salah satu dari mereka, kembali dan pilih titik lain.
  • Setelah Anda memiliki vektor kandidat, simpan di suatu tempat untuk digunakan nanti.
  • Jika Anda tidak memiliki cukup vektor yang tersimpan, kembali dan coba buat vektor lain.

Dengan generator angka acak berkualitas tinggi yang cukup, ini memberi Anda satu set koordinat tersimpan yang memenuhi kriteria Anda dengan kepadatan seragam (diharapkan).

Sayangnya, jika Anda memiliki dimensi relatif tinggi n (yaitu, jika Anda membuat setiap vektor dari daftar koordinat yang relatif panjang), bidang bertuliskan (apalagi volume yang dipangkas) memiliki bagian yang sangat kecil dari total volume kotak pembatas total, jadi mungkin perlu menjalankan banyak iterasi, kebanyakan dari mereka menghasilkan poin yang ditolak di luar area terbatas Anda, sebelum menemukan titik di dalam area terbatas Anda. Karena komputer sekarang ini cukup cepat, apakah itu cukup cepat?

David Cary
sumber
Jadi apa yang Anda sarankan efektif untuk mencicipi ruang. Saya punya masalah yang sama kecuali menemukan kotak pembatas tidak dapat dilakukan secara statis (IE, tidak dapat dikodekan). Dari pengalaman, ini rusak jika kendala Anda dalam bentuk f1(x1) + f2(x2) == CAda saran di sini?
Groostav
Ya, metode pengambilan sampel tidak berfungsi jika Anda memiliki kendala kesetaraan ("=="). Batasan seperti titik yang ada di permukaan bola, atau di permukaan silinder, dll. (Jari-jari == R), bukan di dalam bola (jari-jari <= R). Memilih poin yang sama di seluruh volume akan "tidak pernah" (probabilitas mendekati 0) mengenai permukaan yang Anda inginkan. Jadi Anda perlu memilih titik yang ada di permukaan itu - yaitu, untuk menemukan titik [x1, x2, x3] sedemikian rupa sehingga f1 (x1) + f2 (x2) == C, Anda dapat secara acak memilih x1 dan kemudian memaksa x2 = inverse_f2 (C - f1 (x1)).
David Cary
Untuk kasus khusus dari titik-titik yang terdistribusi secara merata pada permukaan bola, lihat "Titik acak seragam pada bola" .
David Cary
@Groostav: Mungkin pertanyaan Anda cukup berbeda dari pertanyaan awal sehingga Anda bisa mempostingnya sebagai pertanyaan tingkat atas yang baru? "Aku baru saja diberitahu bahwa aku harus mengirim pertanyaan lanjutan, mengapa dan bagaimana?"
David Cary