Generowanie losowych wektorów z ograniczeniami

10

Muszę utworzyć losowe wektory liczb rzeczywistych, spełniające następujące ograniczenia:

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.

Jaki byłby typowy algorytm do wydajnego generowania tego rodzaju wektora?

random-generation LouisChiffre
źródło
1
Co rozumiesz przez czwarte ograniczenie: „Wielkość a jest ..”
M. Tibbits,
Mój błąd. Gotowy opis. Dzięki za opinie.
LouisChiffre,
Jak to się a_idzieje po dystrybucji, p_ia także mniej c? To dlatego, że rozkład p_ijest mniejszy c? W jakiej dystrybucji myślisz?
deps_stats
@deps_stats. Bardzo dobre punkty. Pseudo kod nie był bardzo jasny. Rozkład, który mam na myśli, jest rozkładem Poissona. Każdy element ma rozkład Poissona z inną lambda. Mając to na uwadze, chyba pierwszy warunek (a_i <c) nie jest konieczny, ponieważ mogę po prostu przeskalować a_i pod koniec generacji, aby go spełnić.
LouisChiffre
Zadam coś innego ... Czy opisano c, A, Ba lambdas stałe?
deps_stats

Odpowiedzi:

4

Jeśli dobrze cię rozumiem, tylko punkty w niewielkiej objętości n-wymiarowej przestrzeni spełniają twoje ograniczenia.

Twoje pierwsze ograniczenie ogranicza je do wnętrza hipersfery, co przypomina mi comp.graphics.algorytmy FAQ „Jednolite losowe punkty na kuli” i jak generować równomiernie rozmieszczone punkty w trójwymiarowej kuli? Drugie ograniczenie nieco wycina się z hipersfery, a pozostałe ograniczenia dalej zmniejszają objętość, która spełnia twoje ograniczenia.

Myślę, że najprostszą rzeczą jest jedno z podejść sugerowanych przez FAQ:

  • wybierz dowolną obwiednię wyrównaną do osi która na pewno zawiera cały wolumin. W tym przypadku -c <a_1 <c, -c <a_2 <c, ... -c <a_n <c zawiera całą objętość objętą ograniczeniami, ponieważ zawiera hipersferę opisaną przez pierwsze ograniczenie, a pozostałe ograniczenia wciąż się miażdżą z dala od tego tomu.
  • Algorytm równomiernie wybiera punkty w tym polu ograniczającym. W tym przypadku algorytm niezależnie ustawia każdą współrzędną wektora kandydującego na pewną niezależną równomiernie rozmieszczoną liczbę losową od -c do + c. (Zakładam, że chcesz, aby punkty były rozmieszczone z jednakową gęstością w całym tym tomie. Przypuszczam, że możesz zmusić algorytm do wyboru niektórych lub wszystkich współrzędnych z rozkładem Poissona lub innym nierównomiernym rozkładem, jeśli miałbyś jakiś powód, aby to zrobić).
  • Po uzyskaniu wektora kandydata sprawdź każde ograniczenie. Jeśli któryś z nich zawiedzie, wróć i wybierz inny punkt.
  • Gdy masz wektor kandydujący, przechowuj go gdzieś do późniejszego wykorzystania.
  • Jeśli nie masz wystarczającej liczby zapisanych wektorów, wróć i spróbuj wygenerować kolejny.

Dzięki wystarczająco wysokiej jakości generatorowi liczb losowych daje to zestaw zapisanych współrzędnych, które spełniają twoje kryteria z (oczekiwaną) jednolitą gęstością.

Niestety, jeśli masz stosunkowo wysoką wymiarowość n (tj. Jeśli konstruujesz każdy wektor ze stosunkowo długiej listy współrzędnych), wpisana sfera (znacznie mniej zmniejszonej objętości) ma zaskakująco małą część całkowitej objętości całkowitą ramkę ograniczającą, więc może być konieczne wykonanie wielu iteracji, z których większość generuje odrzucone punkty poza ograniczonym obszarem, zanim znajdzie punkt w ograniczonym obszarze. Skoro komputery w dzisiejszych czasach są dość szybkie, czy to będzie wystarczająco szybkie?

David Cary
źródło
Sugerujesz więc, aby skutecznie wypróbować przestrzeń. Mam podobny problem z wyjątkiem tego, że znalezienie ramki granicznej nie może być wykonane statycznie (IE, nie może być zakodowane na stałe). Z doświadczenia f1(x1) + f2(x2) == Cwynika , że załamuje się, jeśli twoje ograniczenia mają formę Jakieś sugestie tutaj?
Groostav
Tak, metoda próbkowania nie działa, jeśli masz ograniczenia równości („==”). Ograniczenia, takie jak punkty, które znajdują się na powierzchni kuli lub na powierzchni cylindra itp. (Promień == R), a nie wewnątrz kuli (promień <= R). Jednolite wybranie punktów w całej objętości „nigdy” (prawdopodobieństwo bliskie 0) nie uderzy w pożądaną powierzchnię. Musisz więc w jakiś sposób wybierać tylko punkty znajdujące się na tej powierzchni - tzn. Aby znaleźć punkty [x1, x2, x3] takie, że f1 (x1) + f2 (x2) == C, możesz losowo wybrać x1, a następnie wymusić x2 = inverse_f2 (C - f1 (x1)).
David Cary
Aby zapoznać się ze szczególnym przypadkiem równomiernie rozmieszczonych punktów na powierzchni kuli, zobacz „Jednolite losowe punkty na kuli” .
David Cary
@Groostav: Być może twoje pytanie różni się na tyle od pierwotnego, że możesz je zadać jako nowe pytanie najwyższego poziomu? „Właśnie powiedziano mi, że muszę zadać pytanie uzupełniające, dlaczego i jak?”
David Cary