algorithm - 如何线性化最小最大约束

Question

目前我有这个线性规划模型：

最大 X

这样：

Max_a(Min_b(F(a,b,X))) <= 某个常数

* Max_a意思是通过改变a来最大化下面的方程，同样适用于Min_b

现在，问题变成了如何线性化约束部分。当前的大多数 Minmax 线性化论文都将 Minmax 作为目标。但是，如果它是一个约束，如何线性化它？

谢谢

Answer 1

初步说明：你描述的问题不是“线性规划模型”，也没有办法直接转化为线性模型（不代表不能解决）。

首先，请注意Maxin 约束不是必需的，即您的问题可以重新表述为：

 Max X
 subject to: Min_b F(a, b, X) <= K  forall a

现在，既然您说的是“线性模型”，我假设至少F是线性的，即：

 F(a, b, X) = Fa.a + Fb.b + FX.X

并且约束显然可以写成：

 Fa.a + Min_b Fb.b + FX.X <= k forall a

有趣的一点是，on 的最小值b不依赖于aand的值X。因此，它可以预先解决：先找到u = Min_b Fb.b，然后解决

 Max X
 subject to Fa.a + FX.X <= k - u   forall a

当然，这假设 和 的域a是b独立的（形式为AxB）：如果有其他约束耦合a和b，这是一个不同的问题（在这种情况下，请在问题中写下完整的问题）。