计算科学 - 使用预言机进行极小极大优化 - 吾爱随笔录

我有以下形式的优化问题：

min_{y} [max_{x} f (x, y)] .

$\min_y\left[\max_x f(x,y)\right].$ 固定的情况下在上是相当简单的，类似地固定的情况下在上。如果有帮助，我的问题是凹的——但是虽然我可以以封闭形式解决问题，但它不是凸的。

f (x, y)

$f(x,y)$

y

$y$

x

$x$

f (x, y)

$f(x,y)$

x

$x$

y

$y$

x

$x$

y

$y$

极小极大问题的优化算法的一个明显候选可能如下所示：但是，这个算法不必收敛。

\begin{aligned} x_{k + 1} & \leftarrow \arg max_{x} f (x, y_{k}) \\ y_{k + 1} & \leftarrow \arg min_{y} f (x_{k + 1}, y) \end{aligned}

$\begin{array}{rl} x_{k+1}&\gets\arg\max_x f(x,y_k)\\ y_{k+1}&\gets\arg\min_y f(x_{k+1},y) \end{array}$

给定一次优化一个变量的预言，我们可以为极小极大问题构建一种优化算法吗？

梯度下降-上升 (GDA) 算法具有类似的风格，但是对于我们的问题，可以独立地找到的全局最优值，因此似乎没有必要只采取小的梯度步骤。如果有帮助，我很乐意为添加一个二次项并假设我可以优化目标。 $x,y$ $f$ $f(x,y)+\alpha\|y-y_0\|_2^2-\beta\|x-x_0\|_2^2$