Zufallsvektoren mit Einschränkungen erzeugen

Ich muss Zufallsvektoren von reellen Zahlen a_i erstellen, die die folgenden Bedingungen erfüllen:

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.

Was wäre der typische Algorithmus, um diese Art von Vektor effizient zu erzeugen?

Wenn ich Sie richtig verstehe, erfüllen nur Punkte in einem kleinen Volumen des n-dimensionalen Raums Ihre Einschränkungen.

Ihre erste Einschränkung beschränkt sie auf das Innere einer Hypersphäre, was mich an die häufig gestellten Fragen zu " comp.graphics.algorithms " "Einheitliche zufällige Punkte auf der Kugel" und " Wie werden gleichmäßig verteilte Punkte in der 3-D-Einheitskugel erzeugt? " Erinnert . Die zweite Einschränkung schneidet ein wenig aus der Hypersphäre heraus, und die anderen Einschränkungen verschwinden weiter bei dem Volumen, das Ihren Einschränkungen entspricht.

Ich denke, das Einfachste ist einer der in den FAQ vorgeschlagenen Ansätze:

• Wählen Sie einen beliebigen achsenausgerichteten Begrenzungsrahmen , der sicher das gesamte Volumen enthält. In diesem Fall enthält -c <a_1 <c, -c <a_2 <c, ... -c <a_n <c das gesamte eingeschränkte Volumen, da es die durch die erste Einschränkung beschriebene Hypersphäre enthält und die anderen Einschränkungen weiter schnitzen weg bei dieser Lautstärke.
• Der Algorithmus wählt einheitlich Punkte in diesem Begrenzungsrahmen aus. In diesem Fall setzt der Algorithmus unabhängig jede Koordinate eines Kandidatenvektors auf eine unabhängige gleichmäßig verteilte Zufallszahl von -c bis + c. (Ich gehe davon aus, dass Sie Punkte mit gleicher Dichte in diesem Volumen verteilen möchten. Ich nehme an, Sie könnten den Algorithmus veranlassen, einige oder alle Koordinaten mit einer Poisson-Verteilung oder einer anderen ungleichmäßigen Verteilung auszuwählen, wenn Sie einen Grund dafür hätten.)
• Wenn Sie einen Kandidatenvektor haben, überprüfen Sie jede Einschränkung. Wenn einer von ihnen fehlschlägt, gehen Sie zurück und wählen Sie einen anderen Punkt.
• Wenn Sie einen Kandidatenvektor haben, speichern Sie ihn irgendwo für die spätere Verwendung.
• Wenn Sie nicht genügend gespeicherte Vektoren haben, gehen Sie zurück und versuchen Sie, einen anderen zu generieren.

Mit einem ausreichend hochwertigen Zufallszahlengenerator erhalten Sie einen Satz gespeicherter Koordinaten, die Ihre Kriterien mit (erwarteter) gleichmäßiger Dichte erfüllen.

Wenn Sie eine relativ hohe Dimensionalität n haben (dh wenn Sie jeden Vektor aus einer relativ langen Liste von Koordinaten konstruieren), hat die beschriftete Kugel (geschweige denn Ihr verkleinertes Volumen) einen überraschend kleinen Teil des Gesamtvolumens von Der gesamte Begrenzungsrahmen muss daher möglicherweise viele Iterationen ausführen, von denen die meisten abgelehnte Punkte außerhalb Ihres eingeschränkten Bereichs generieren, bevor ein Punkt innerhalb Ihres eingeschränkten Bereichs gefunden wird. Da Computer heutzutage ziemlich schnell sind, wird das schnell genug sein?