Генерация случайных векторов с ограничениями

10

Мне нужно создать случайные векторы действительных чисел a_i, удовлетворяющие следующим ограничениям:

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.

Какой будет типичный алгоритм для эффективной генерации такого вектора?

LouisChiffre
источник
1
Что вы подразумеваете под четвертым ограничением «Величина a есть ..»
М. Тиббитс
Моя ошибка. Готовое описание. Спасибо за ответ.
Луи Шиффр
Как это a_iследует за распределением p_iи также меньше c? Это потому что раздача p_iтоже меньше того c? В каком дистрибутиве вы думаете?
deps_stats
@deps_stats. Очень хорошие очки. Псевдокод был не очень понятен. Я имею в виду распределение Пуассона. Каждый элемент следует распределению Пуассона с другой лямбда. Имея это в виду, я предполагаю, что первое условие (a_i <c) не является необходимым, поскольку я могу просто изменить масштаб a_i в конце поколения, чтобы удовлетворить его.
Луи Шиффр
Позвольте мне спросить что - то еще ... Являются c, A, Bи лямбды фиксированной?
deps_stats

Ответы:

4

Если я вас правильно понимаю, только точки в небольшом объеме n-мерного пространства соответствуют вашим ограничениям.

Ваше первое ограничение ограничивает его внутреннюю часть гиперсферы, что напоминает мне часто задаваемые вопросы о comp.graphics.algorithms «Однородные случайные точки на сфере» и Как генерировать равномерно распределенные точки в 3-мерном единичном шаре? Второе ограничение немного выделяется из гиперсферы, а другие ограничения еще больше сокращают объем, соответствующий вашим ограничениям.

Я думаю, что самое простое, что можно сделать, это один из подходов, предложенных в FAQ:

  • выберите произвольную ограничивающую рамку , выровненную по оси, которая , как мы уверены, содержит весь объем. В этом случае -c <a_1 <c, -c <a_2 <c, ... -c <a_n <c содержит весь ограниченный том, поскольку он содержит гиперсферу, описанную первым ограничением, а другие ограничения сохраняют единицы прочь в этом объеме.
  • Алгоритм равномерно выбирает точки по всему ограничивающему прямоугольнику. В этом случае алгоритм независимо устанавливает каждую координату вектора-кандидата на некоторое независимое равномерно распределенное случайное число от -c до + c. (Я предполагаю, что вы хотите, чтобы точки распределялись с одинаковой плотностью по всему этому объему. Полагаю, вы могли бы заставить алгоритм выбрать некоторые или все координаты с распределением Пуассона или другим неравномерным распределением, если у вас была причина для этого).
  • Если у вас есть вектор-кандидат, проверьте каждое ограничение. Если это не сработает, вернитесь и выберите другую точку.
  • Если у вас есть вектор-кандидат, сохраните его где-нибудь для дальнейшего использования.
  • Если у вас недостаточно сохраненных векторов, вернитесь и попробуйте сгенерировать еще один.

С достаточно качественным генератором случайных чисел это дает вам набор сохраненных координат, которые соответствуют вашим критериям с (ожидаемой) равномерной плотностью.

Увы, если у вас относительно высокая размерность n (т. Е. Если вы строите каждый вектор из относительно длинного списка координат), вписанная сфера (а тем более уменьшенный объем) имеет удивительно небольшую часть общего объема общая ограничивающая рамка, поэтому может потребоваться выполнить много итераций, большинство из которых генерируют отклоненные точки за пределами вашей ограниченной области, прежде чем найти точку внутри вашей ограниченной области. Поскольку компьютеры в наши дни довольно быстрые, будет ли это достаточно быстро?

Дэвид Кэри
источник
Так что вы предлагаете эффективно пробовать пространство. У меня похожая проблема, за исключением того, что нахождение ограничивающего прямоугольника не может быть выполнено статически (IE не может быть жестко запрограммирован). Исходя из опыта, это ломается, если ваши ограничения имеют форму. f1(x1) + f2(x2) == CЕсть предложения?
Groostav
Да, метод выборки не работает, если у вас есть ограничения равенства ("=="). Ограничения, такие как точки, которые находятся на поверхности сферы или на поверхности цилиндра и т. Д. (Радиус == R), а не внутри сферы (радиус <= R). Равномерный выбор точек по всему объему никогда не будет (вероятность близка к 0) достичь желаемой поверхности. Таким образом, вам нужно каким-то образом выбирать только точки, которые находятся на этой поверхности - то есть, чтобы найти точки [x1, x2, x3], такие, что f1 (x1) + f2 (x2) == C, вы можете случайно выбрать x1, а затем принудительно x2 = обратный_f2 (C - f1 (x1)).
Дэвид Кэри,
Для частного случая равномерно распределенных точек на поверхности сферы см. «Равномерные случайные точки на сфере» .
Дэвид Кэри,
@Groostav: Возможно, ваш вопрос достаточно отличается от исходного вопроса, чтобы вы могли опубликовать его как новый вопрос верхнего уровня? «Мне только что сказали, что я должен опубликовать дополнительный вопрос, почему и как?»
Дэвид Кэри,