前言

动机：近期在整理 MoE 系列笔记的时候，察觉到自己对最优化 (Optimization) 的记忆有点模糊了。因此笔者重新阅读最优化相关的内容并进行较为系统地整理。笔者之前系统学习中科大凌青老师的《凸优化》课程，这次在整理过程中发现了新的学习资料，讲的清晰易懂，非常适合入门或者复习。

Sion Minimax Theorem

补充概念

Saddle Point 形式

对于最优化问题：$\min_x \max_y f(x,y)$，若存在 $(x^\star,y^\star)$ 满足:

\[f(x^\star,y)\le f(x^\star,y^\star)\le f(x,y^\star), \quad \forall x,\forall y,\]

那么 $(x^\star,y^\star)$ 就是一个 saddle point。直观理解：

  • 固定 $y=y^\star$，$x^\star$ 让 $f(x,y^\star)$ 最小
  • 固定 $x=x^\star$，$y^\star$ 让 $f(x^\star,y)$ 最大

Compact

在有限维欧氏空间 $\mathbb{R}^d$ 中，可以把 compact 理解为

\[\boxed{ \text{closed and bounded} }\]

举个例子：$[0,1]$ 是紧集；$(0,1)$ 不是（因为非 bounded）；$\mathbb{R}$ 不是（因为非 closed）。

Quasi-Convex/Concave

一个函数 $g(z)$ 是 quasi-convex 定义为：

\[g(\theta u+(1-\theta)v) \le \max\{g(u),g(v)\}, \quad \theta\in[0,1].\]

意思是：在两个点之间连线，中间点的函数值不会超过两端中较大的那个。这比普通 convex 的条件弱，因为 convex 要求：

\[g(\theta u+(1-\theta)v) \le \theta g(u)+(1-\theta)g(v).\]

因此有：$\text{convex} \Rightarrow \text{quasi-convex}$

同理，对于一个 quasi-concave 函数 $g(z)$，意味着：

\[g(\theta u+(1-\theta)v) \ge \min\{g(u),g(v)\}.\]

同理也有：$\text{concave} \Rightarrow \text{quasi-concave}$

Convex-Concave Function

对于二元函数 $f(x,y)$，若满足下述 “希望” 则是 convex-concave function。

  • 如果优化问题是：$\min_x \max_y f(x,y)$
    • 对 $x$ 做 minimization，希望 $f$ 关于 $x$ 是 convex
    • 对 $y$ 做 maximization，希望 $f$ 关于 $y$ 是 concave
  • 如果优化问题是：$\max_x \min_y f(x,y)$ 则 “希望” 翻转。

Continuity-Semicontinuity

“连续性 / 半连续性”可以理解为：当变量发生极小扰动时，函数值不能以破坏极值存在性的方式突然跳变。

Continuity
\[x_k\to x_0 \quad\Longrightarrow\quad f(x_k)\to f(x_0).\]

由于很多优化问题里的函数不是完全连续的。例如 indicator function、约束惩罚函数、$⁡\max$、$⁡\inf$、$⁡\sup$、分段函数，都可能存在跳变。因此需要比“连续”更弱但仍然足够好用的条件，即：半连续性 (Semicontinuity)。

\[\text{continuous} \Rightarrow \text{upper semicontinuous and lower semicontinuous}.\]
Semicontinuity

半连续性有两类：Lower semicontinuity and upper semicontinuity，分别定义如下：

\[\begin{cases} \textbf{Lower: }\quad f(x_0)\le \liminf_{k\to\infty} f(x_k) \quad \text{for every }x_k\to x_0. \\ \textbf{Upper: }\quad f(x_0)\ge \limsup_{k\to\infty}f(x_k) \quad \text{for every }x_k\to x_0. \end{cases}\]
  • Lower semicontinuity：不允许突然向上跳；适合 minimization；
  • Upper semicontinuity：不允许突然向下跳；适合 maximization。

定理运用

不要先背完整定理。先记住它的“工程化检查表”。

对于：

\[\max_x \min_y f(x,y),\]

要交换成：

\[\min_y \max_x f(x,y),\]

此时需要检查：

第一、优化变量可行域

\[X \text{ compact convex and }Y \text{ convex}\]

第二、max 操作相关

因为你在对 $x$ 最大化，所以希望：

\[f(\cdot,y)\]

$f(\cdot, y)$ 关于 $x$ 至少是 quasi-concave 且 upper semicontinuity。

第三、min 操作相关

因为你在对 $y$ 最小化，所以希望：

\(f(x,\cdot)\) $f(x, \cdot)$ 关于 $y$ 至少是 quasi-convex 且 lower semicontinuity。

Reference

[1] “拉格朗日对偶问题”如何直观理解？“KKT条件” “Slater条件” “凸优化”打包理解

[2] 凸优化 中科大