Génération de vecteurs aléatoires avec contraintes

J'ai besoin de créer des vecteurs aléatoires de nombres réels a_i satisfaisant aux contraintes suivantes:

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.

Quel serait l'algorithme typique pour générer efficacement ce type de vecteur?

Si je vous comprends bien, seuls les points d'un petit volume d'espace à n dimensions répondent à vos contraintes.

Votre première contrainte la contraint à l'intérieur d'une hypersphère, ce qui me rappelle la FAQ comp.graphics.algorithms "Points aléatoires uniformes sur la sphère" et Comment générer des points uniformément distribués dans la boule d'unité 3D? La deuxième contrainte tranche un peu en dehors de l'hypersphère, et les autres contraintes diminuent encore davantage le volume qui répond à vos contraintes.

Je pense que la chose la plus simple à faire est l'une des approches suggérées par la FAQ:

• choisissez un cadre de sélection arbitraire aligné sur l'axe qui, nous en sommes sûrs, contient tout le volume. Dans ce cas, -c <a_1 <c, -c <a_2 <c, ... -c <a_n <c contient tout le volume contraint, car il contient l'hypersphère décrite par la première contrainte, et les autres contraintes continuent de se tailler loin à ce volume.
• L'algorithme sélectionne uniformément les points dans cette boîte englobante. Dans ce cas, l'algorithme définit indépendamment chaque coordonnée d'un vecteur candidat sur un certain nombre aléatoire uniformément réparti indépendant de -c à + c. (Je suppose que vous voulez des points distribués avec une densité égale dans tout ce volume. Je suppose que vous pourriez faire en sorte que l'algorithme sélectionne certaines ou toutes les coordonnées avec une distribution de Poisson ou une autre distribution non uniforme, si vous aviez une raison de le faire).
• Une fois que vous avez un vecteur candidat, vérifiez chaque contrainte. Si l'un d'eux échoue, revenez en arrière et choisissez un autre point.
• Une fois que vous avez un vecteur candidat, stockez-le quelque part pour une utilisation ultérieure.
• Si vous n'avez pas assez de vecteurs stockés, revenez en arrière et essayez d'en générer un autre.

Avec un générateur de nombres aléatoires de qualité suffisamment élevée, cela vous donne un ensemble de coordonnées stockées qui répondent à vos critères avec une densité uniforme (attendue).

Hélas, si vous avez une dimensionnalité relativement élevée n (c'est-à-dire si vous construisez chaque vecteur à partir d'une liste de coordonnées relativement longue), la sphère inscrite (et encore moins votre volume réduit) a une part étonnamment petite du volume total de la zone de délimitation totale, il peut donc être nécessaire d'exécuter de nombreuses itérations, la plupart générant des points rejetés en dehors de votre zone contrainte, avant de trouver un point à l'intérieur de votre zone contrainte. Étant donné que les ordinateurs de nos jours sont assez rapides, cela sera-t-il assez rapide?