带约束的Min-Max优化问题求解咨询及理论疑问

数据老陈

2026-6-26

你的优化问题解答

约束的应用顺序

你的第一个思路完全正确：必须先在约束x + y = 1下求解max{x + 2y − 1, 2x + 0.5y + 0.75}，再对这个结果取最小值。原因如下：

若先不考虑约束求max{...}，这个最大值是无界的（比如x、y趋向正无穷时，两个线性函数都会趋向正无穷），后续再套约束完全没有意义，无界的最大值无法进行最小化操作。
正确步骤是先利用约束消元：由x + y = 1得y = 1 - x，代入两个函数：
- 第一个函数：x + 2(1 - x) - 1 = -x + 1
- 第二个函数：2x + 0.5(1 - x) + 0.75 = 1.5x + 1.25
  问题转化为：求min max{ -x + 1, 1.5x + 1.25 }（x为任意实数）
找两个函数的交点：令-x + 1 = 1.5x + 1.25，解得x = -0.1，此时y = 1.1，对应max值为1.1。
分析单调性：-x+1随x增大递减，1.5x+1.25随x增大递增，因此它们的交点就是max函数的最小值点，也就是整个问题的最优解，目标值为1.1。

max min(f₁,f₂,...,fₙ)是典型的极小极大对偶函数，它有以下等价表述：

集合角度：它是所有函数f₁,...,fₙ的下包络（每个点取所有函数的最小值形成的曲线/曲面）的上确界（最大值）。
优化问题转化：可写成等价的优化形式：
```
max t
s.t. t ≤ f₁(x),
     t ≤ f₂(x),
     ...
     t ≤ fₙ(x)
```
即找到最大的t，使得t同时小于等于所有fᵢ(x)在点x处的值（若x为变量，则是找满足约束的x和t，使得t最大）。
性质：若所有fᵢ都是线性函数，那么max min(f₁,...,fₙ)是凹函数，对应的优化问题可转化为线性规划。另外，它和min max(f₁,...,fₙ)满足弱对偶性，即max min(...) ≤ min max(...)，当满足特定条件（如冯·诺依曼极小极大定理的条件：函数线性、变量在紧凸集上）时，两者相等。