Gerando vetores aleatórios com restrições

10

Preciso criar vetores aleatórios de números reais a_i atendendo às seguintes restrições:

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.

Qual seria o algoritmo típico para gerar eficientemente esse tipo de vetor?

random-generation LouisChiffre
fonte
11
O que você quer dizer com a quarta restrição, "A magnitude de a é ..."
M. Tibbits
Meu erro. Descrição finalizada. Obrigado pelo feedback.
21411 LouisChiffre
Como isso a_isegue a distribuição p_ie também é menos isso c? Isso p_iocorre porque a distribuição também é menor que isso c? Em qual distribuição você está pensando?
deps_stats
@deps_stats. Muito bons pontos. O pseudo-código não era muito claro. A distribuição que tenho em mente é a distribuição de poisson. Cada elemento segue uma distribuição de poisson com uma lambda diferente. Com isso em mente, acho que a primeira condição (a_i <c) não é necessária, pois posso apenas redimensionar a_i no final da geração para satisfazê-la.
LouisChiffre
Deixe-me perguntar algo mais ... Você o c, A, Be lambdas fixo?
deps_stats

Respostas:

4

Se bem entendi, apenas pontos em um pequeno volume de espaço n-dimensional atendem às suas restrições.

Sua primeira restrição o restringe ao interior de uma hiperesfera, o que me lembra as perguntas frequentes comp.graphics.algorithms "Pontos aleatórios uniformes na esfera" e Como gerar pontos uniformemente distribuídos na bola unitária em 3-d? A segunda restrição corta um pouco da hiperesfera, e as outras restrições diminuem ainda mais o volume que atende às suas restrições.

Eu acho que a coisa mais simples a fazer é uma das abordagens sugeridas pelo FAQ:

  • escolha uma caixa delimitadora alinhada ao Eixo arbitrária que, com certeza, contém todo o volume. Nesse caso, -c <a_1 <c, -c <a_2 <c, ... -c <a_n <c contém todo o volume restrito, uma vez que contém a hiperesfera descrita pela primeira restrição, e as outras restrições permanecem inalteradas longe nesse volume.
  • O algoritmo escolhe pontos uniformemente em toda a caixa delimitadora. Nesse caso, o algoritmo define independentemente cada coordenada de um vetor candidato para algum número aleatório uniformemente distribuído independente de -c a + c. (Suponho que você queira pontos distribuídos com densidade igual ao longo deste volume. Suponho que você possa fazer com que o algoritmo selecione algumas ou todas as coordenadas com uma distribuição de Poisson ou outra distribuição não uniforme, se você tiver algum motivo para isso).
  • Depois de ter um vetor candidato, verifique cada restrição. Se falhar em algum deles, volte e escolha outro ponto.
  • Depois de ter um vetor candidato, armazene-o em algum lugar para uso posterior.
  • Se você não tiver vetores armazenados suficientes, volte e tente gerar outro.

Com o gerador de números aleatórios de qualidade suficientemente alta, isso fornece um conjunto de coordenadas armazenadas que atendem aos seus critérios com densidade uniforme (esperada).

Infelizmente, se você possui uma dimensionalidade relativamente alta n (isto é, se você constrói cada vetor a partir de uma lista relativamente longa de coordenadas), a esfera inscrita (muito menos o seu volume reduzido) possui uma parte surpreendentemente pequena do volume total de a caixa delimitadora total, portanto, pode ser necessário executar muitas iterações, a maioria delas gerando pontos rejeitados fora da área restrita, antes de encontrar um ponto dentro da área restrita. Como os computadores hoje em dia são bem rápidos, isso será rápido o suficiente?

David Cary
fonte
Então, o que você está sugerindo é efetivamente provar o espaço. Eu tenho um problema semelhante, exceto encontrar uma caixa delimitadora não pode ser feito estaticamente (IE, não pode ser codificado). Por experiência, isso ocorre se suas restrições são da forma f1(x1) + f2(x2) == CAlguma sugestão aqui?
Groostav
Sim, o método de amostragem não funciona se você tiver restrições de igualdade ("=="). Restrições, como pontos que estão na superfície de uma esfera ou na superfície de um cilindro, etc. (raio == R), em vez de dentro da esfera (raio <= R). A seleção uniforme de pontos em todo o volume "nunca" (probabilidade próxima de 0) atinge a superfície desejada. Então, de alguma forma, você só precisa escolher pontos que estão nessa superfície - ou seja, para encontrar os pontos [x1, x2, x3] tais que f1 (x1) + f2 (x2) == C, você pode escolher aleatoriamente x1 e forçar x2 = inverso_f2 (C - f1 (x1)).
David Cary
Para o caso especial de pontos uniformemente distribuídos na superfície de uma esfera, consulte "Pontos aleatórios uniformes na esfera" .
David Cary
@Groostav: Talvez sua pergunta seja diferente o suficiente da pergunta original para que você possa publicá-la como uma nova pergunta de nível superior? "Acabei de me dizer que tenho que postar uma pergunta de acompanhamento, por que e como?"
David Cary