定义一个local minimax

2020-09-29 本文已影响0人顾劝劝

What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?
by Chi Jin, Praneeth Netrapalli, Michael I. Jordan
minimax和纳什均衡有什么关系？局部minimax怎么定义？有什么性质？如何找到？和全局miniax有什么关系？请君听我道来。

minimax问题，就是选手1先最大化目标，选手2再最小化刚才被最大化过的目标，找到他俩的最优解。用数学符号表达就是：
$\min_x \max_y l(x,y)\tag{1}。$

global minimax point

式子（1）的解，一定是存在的。
y的最优解给定所有的x都是最优的，当然给定最优x也是最优的。
x的最优解要从所有最大化l的y里去找，不仅仅是对于给定的最优y。
$l(x^*,y) \leq l(x^*,y^*)\leq \max_{y'\in\mathcal{Y}} l(x,y')$
全局minimax一定存在

global nash equilibrium

只要求x最优解在给定最优y时是最优的
$l(x^*,y) \leq l(x^*,y^*)\leq l(x,y^*)$
以前只要内层凹、外层凸，这个全局纳什均衡就很好找。但是非凹非凸的函数找这个点无疑是NP-hard。

local nash equilibria

全局的难找，局部的总可以找到。我现在缩小搜索范围，把跑遍全部定义域的性质变成局部有这个性质，也就是对于所有 $||x-x^*||\leq \delta$ 和 $||y-y^*||\leq \delta$ 的 $(x,y)$ 来说满足
$l(x^*,y) \leq l(x^*,y^*)\leq l(x,y^*)$ ，
那 $(x^*,y^*)$ 就是局部最优。
局部最优满足一阶必要条件：
$\nabla_x l(x,y)=0,\ \nabla_y l(x,y)=0$
和二阶导数必要条件：
$\nabla^2_x l(x,y)\preceq 0, \nabla^2_y l(x,y)\preceq 0$
当然，如果有这样的二阶充分条件，那肯定是严格的局部最优啦：
$\nabla^2_x l(x,y)\prec 0, \nabla^2_y l(x,y)\prec 0$

不是所有二阶可微的函数都存在（局部或者全局的）纳什均衡哦！

local minimax point

仿照local nash equilibria，给定一个 $\delta_0$ 和一个 $h$ ，我的 $\delta\in(0,\delta_0]$ ，我的 $\delta\rightarrow 0$ 时 $h(\delta)\rightarrow 0$ ，这样的话满足以下条件的 $(x^*,y^*)$ 就是局部minimax点：
$l(x^*,y) \leq l(x^*,y^*)\leq \max_{y':||y'-y^*||\leq h(\delta)} l(x,y')$
这样找到的y只要是邻域内最大的y(x)就行了。相当于两个选手都在一个邻域内做序贯决策。

局部纳什均衡一定是局部minimax哦！
局部minimax也有一阶必要条件
不过二阶必要条件不再是海森矩阵半正定，而是舒尔补半正定；充分条件对应的就是舒尔补正定。体现了x和y是有顺序差异的。这个二阶条件就是local minimax和local nash equilibria的区别。

全局minimax可能既不是局部minimax，也可能不满足舒尔补正定的条件。
不是所有的二阶可微的函数、定义域是紧集的都存在局部minimax哦！

什么时候global minimax一定是local minimax呢？以下几种情况都符合：

内层concave，是个凸优化问题。
内层在邻域内concave，而且所有的local maxima都是global maximal。

定义一个local minimax

global minimax point

global nash equilibrium

local nash equilibria

local minimax point

猜你喜欢

热点阅读