生成带有约束的随机向量

机器算法验证 随机生成
2022-03-02 23:05:29

我需要创建满足以下约束的实数 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.

有效生成这种向量的典型算法是什么？

1个回答

如果我理解正确，只有少量 n 维空间中的点满足您的限制。

您的第一个约束将其限制在超球体的内部，这让我想起了 comp.graphics.algorithms 常见问题解答“球体上的均匀随机点”和如何在 3-d 单位球中生成均匀分布的点？ 第二个约束从超球面切出一点，其他约束进一步缩小到满足您的约束的体积。

我认为最简单的做法是常见问题解答建议的方法之一：

  • 选择一些我们确定包含整个体积的任意轴对齐边界框。在这种情况下，-c < a_1 < c, -c < a_2 < c, ... -c < a_n < c 包含整个约束体积，因为它包含第一个约束描述的超球面，而其他约束不断缩小远在那个音量。
  • 该算法在整个边界框中统一选取点。在这种情况下，算法将候选向量的每个坐标独立地设置为从-c到+c的某个独立的均匀分布的随机数。（我假设您希望点在整个体积中以相等的密度分布。我想您可以使算法选择具有泊松分布或其他非均匀分布的部分或全部坐标，如果您有理由这样做）。
  • 一旦你有了一个候选向量，检查每个约束。如果其中任何一个失败，请返回并选择另一个点。
  • 一旦你有了一个候选向量，就将它存储在某个地方以备后用。
  • 如果您没有足够的存储向量，请返回并尝试生成另一个向量。

使用足够高质量的随机数生成器，这将为您提供一组存储的坐标，这些坐标符合您的标准，具有（预期的）均匀密度。

唉，如果你有一个相对较高的维度 n（即，如果你从一个相对较长的坐标列表中构造每个向量），那么内接球体（更不用说你的缩减体积）在总体积中的比例非常小。总边界框，因此它可能需要执行许多迭代，其中大多数在您的约束区域之外生成被拒绝的点，然后才能在您的约束区域内找到一个点。由于现在的计算机速度非常快，那会足够快吗？

其它你可能感兴趣的问题
上一篇如何找到不同类型事件之间的关系（由它们的 2D 位置定义）？ 下一篇如何量化特征的冗余？