定义一个local minimax

作者: 顾劝劝 | 来源:发表于2020-09-29 20:35 被阅读0次

定义一个local minimax
Android.mk
Minimax算法和α-β剪枝
lua可视化规则
ThreadLocal 总结
lua模块使用
Android.mk语法详解
Android.mk文件学习笔记
第四章：Android.mk语法
csci561 期末复习

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)就行了。相当于两个选手都在一个邻域内做序贯决策。