具有随机性的线性规划?

计算科学 优化 凸优化 约束优化 线性规划 随机
2021-12-12 05:42:04

假设我已经实现了一个 LP,其中一些约束系数被实现为一些概率分布的平均值。

现在,我想解决同样的问题,但要根据概率分布重新引入随机性。

这仍然可以使用 LP 技术解决吗?

如果不是,那么自然的替代品是什么?

1个回答

有大量关于“随机规划”的文献,但您可能对所谓的“机会约束规划”感兴趣,其中约束系数是随机变量,并且您想找到解决方案x使得每个约束都单独满足概率η(η可能是 0.95、0.99 等)

这些问题通常不能重新表述为 LP,但它们有时可以表述为其他类型的优化问题并解决。例如,如果您的 LP 的约束系数具有多元正态分布,则可以将 LP 的机会约束版本制定和求解为二阶锥程序。您可以在Boyd 和 Vandenberghe的凸优化的第 4.4 节中找到对此的讨论。

您还应该查找更广泛的“稳健优化”主题,以了解适用于各种不确定系数的方法。