优化理论简介 · 最优化 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 (作者)
有时可能遇到部分公式没有正确显示的情况。刷新一下通常可以解决问题