优化理论简介 · 最优化 01
关键字： 最优化理论 渐进收敛速度 停机准则 收敛准则 复杂度
最优化在许多方面都有着极为广泛的运用。本文作为 “最优化” 这个系列的开篇，简单地介绍了其模式、分类与求解思路。
标准形式
\begin{aligned} \mathcal{P}_1: \qquad \min \quad&f(x) \\ s.t. \quad&x \in \mathcal{X} \qquad \quad \end{aligned}
- $x \in \mathbb{R}^n$： 决策变量
- $f:\mathbb{R}^n \to \mathbb{R}$： 目标函数
- $\mathcal{X} \subseteq \mathbb{R}^n$： 可行域
\begin{aligned} \mathcal{X} \triangleq \{ x \in \mathbb{R}^n | &c_i(x) \leq 0, i = 1, ..., m, c_i(x) = 0, i = m + 1, ..., m + l. \} \end{aligned}
- $\min f(x)$ 不存在 $\Rightarrow \inf f(x)$ （最大下界）
- $\max f(x)$ 不存在 $\Rightarrow \sup f(x)$ （最小上界）
实例
稀疏优化（信号还原）
\begin{aligned} \textrm{(NP-hard)} \qquad \min_{x \in \mathbb{R}^n} &| x |_0, \\ s.t. \quad &Ax = b \qquad \qquad \qquad \quad \end{aligned} 变换为 $l_1$-norm 优化问题求解（$l_0$-norm 和 $l_1$-norm 优化一样，均具备稀疏性）： \begin{aligned} \textrm{(solvable)} \qquad \min_{x \in \mathbb{R}^n} &| x |_1, \\ s.t. \quad &Ax = b \qquad \qquad \qquad \quad \end{aligned}
低秩矩阵恢复
\begin{aligned} \min_{X \in \mathbb{R}^{m \times n}} &\textrm{rank}(X), \\ s.t. \quad &X_{ij} = M_{ij}, (i,j) \in \Omega \end{aligned} 根据稀疏优化思想，非零奇异值的个数 $\Rightarrow$ 非零奇异值的和： \begin{aligned} \min_{X \in \mathbb{R}^{m \times n}} &\| X \|_*, \\ s.t. \quad &X_{ij} = M_{ij}, (i,j) \in \Omega \end{aligned} 二次罚函数形式（去掉约束项）： \begin{aligned} \min_{X \in \mathbb{R}^{m \times n}} \mu \| X \|_* + \frac{1}{2} \sum_{(i,j) \in \Omega} \Big( X_{ij} - M_{ij} \Big)^2 \end{aligned}
步骤与分类
- 步骤 ：构造模型 $\Rightarrow$ 确定问题类型 $\Rightarrow$ 设计算法 $\Rightarrow$ 实现
- 分类 1：
- 连续：可以根据邻域信息来估计某点是否最优
- 离散：通常松弛成连续问题来求解
- 分类 2：
- 无约束：欧几里得空间中寻找函数的最小点
- 有约束：将约束罚到目标函数上转换为无约束问题
- 分类 3：
- 确定：不含未知参数
- 随机：目标函数是关于未知参数的期望
- 分类 4：
- 线性：单纯形法、内点法
- 非线性：目标或约束至少有一个非线性
- 分类 5：
- 凸：任何局部最优解都是全局最优解
- 非凸：转化为一系列凸子问题并逼近
最优解
$\mathcal{P}_1$ 的最优解（定义）. 对于 $\bar{x} \in \mathcal{X}$：
- $\forall x \in \mathcal{X},f(\bar{x}) \leq f(x) \Rightarrow \bar{x}$ 为 “全局极小解 / 最优解 / 最小值点”；
- 存在 $\bar{x}$ 的 $\varepsilon$- 邻域 $\mathcal{N}_\varepsilon(\bar{x})$ 使得 $\forall x \in \mathcal{N}_\varepsilon(\bar{x}) \cap \mathcal{X}, f(\bar{x}) \leq f(x) \Rightarrow \bar{x}$ 为 “局部极小解 / 局部最优解”；
- $\forall x \in \mathcal{N}_\varepsilon(\bar{x}) \cap \mathcal{X} \textrm{且} x \neq \bar{x}, f(\bar{x}) < f(x) \Rightarrow \bar{x}$ 为 “严格局部极小解”。
解的形式
- 解析解：分析函数性质得到
- 数值解：迭代算法
- （无约束优化）收敛准则（需要某种方法对 $x^*$ 进行估计）： \begin{aligned} \frac{f(x^k) - f^*}{\max \{ |f^*|, 1 \}} \leq \varepsilon_1, \quad \| \nabla f(x^k) \| \leq \varepsilon_2 \end{aligned} 判定约束优化问题是否收敛还需考虑 “约束条件的违反度”。
- 停机准则： \begin{aligned} \frac{\| x^{k+1} - x^k \|}{\max \{| x^k |, 1\}} \leq \varepsilon_3, \quad \frac{| f(x^{k+1}) - f(x^k) |}{\max \{| f(x^k) |, 1\}} \leq \varepsilon_4 \end{aligned} 依点列收敛到局部（全局）最优解： \begin{aligned} \lim_{k \to \infty} \| x^k - x^* \| = 0 \end{aligned}
渐进收敛速度
$Q$- 收敛速度 ：
对于充分大的 $k$，若有：
- $\frac{\| x^{k+1} - x^* \|}{\| x^k - x^* \|} \leq a, a \in (0,1) \Longrightarrow$ $Q$- 线性收敛
- $\frac{\| x^{k+1} - x^* \|}{\| x^k - x^* \|} = 0 \Longrightarrow$ $Q$- 超线性收敛（快）
- $\frac{\| x^{k+1} - x^* \|}{\| x^k - x^* \|} \leq 1 \Longrightarrow$ $Q$- 次线性收敛
- $\frac{\| x^{k+1} - x^* \|}{\| x^k - x^* \|^2} \leq a, a \in (0,1) \Longrightarrow$ $Q$- 二次收敛（快）
差距越小，速度越快，注意 $\| x^{k+1} - x^* \| \ll 1$ 和 $a \ll 1$。
$R$- 线性收敛 （同理可定义 R - 超线性 / 次线性 / 二次收敛）： \begin{aligned} \| x^k - x^* \| \leq t_k \longmapsto \textrm{记为}\mathcal{O}(t_k) \end{aligned} 其中 ${t_k}$ 是非负的 $Q$- 线性收敛序列。
复杂度
复杂度通常用迭代次数来描述，可结合渐进收敛速度得到。
示例 ：
若已知 \begin{aligned} f(x^k) - f(x^*) \leq \frac{c}{\sqrt{k}}, \forall k > 0, \end{aligned} 则满足精度 $f(x^k) - f(x^*) \leq \varepsilon$ 的迭代次数 $k$ 满足 \begin{aligned} k \geq \frac{c^2}{\varepsilon^2}. \end{aligned} 因此，算法对应的复杂度为 $\mathcal{O}(\frac{1}{\varepsilon^2})$。
优化算法设计技巧
- 泰勒展开 ：在曲线的局部用多项式拟合（多项式可拟合任意光滑曲线）；
- 对偶 ：对偶问题通常比原始问题容易求解，Primal-Dual Update，ADMM，etc；
- 拆分 ： \begin{aligned} \min_x f(x) + g(x) \qquad \Longrightarrow \qquad \min_{x,y} f(x) + g(y), \quad s.t. \quad x = y \end{aligned}
- 块坐标下降 ：通过逐步求解分量转化为多个低维空间的优化问题。
最后
本文所使用的图片来自北京大学开设的凸优化课程的官方教材。
转载申请
本作品采用 知识共享署名 4.0 国际许可协议 进行许可， 转载时请注明原文链接。您必须给出适当的署名，并标明是否对本文作了修改。
您也可以通过下方按钮直接分享本页面：
Hailiang Zhao （作者）
有时可能遇到部分公式没有正确显示的情况。刷新一下通常可以解决问题