优化理论简介 · 最优化 01

关键字最优化理论渐进收敛速度停机准则收敛准则复杂度

摘要 —— 这篇文档以简洁的形式介绍了最优化理论的基本信息。

最优化在许多方面都有着极为广泛的运用。本文作为 “最优化” 这个系列的开篇,简单地介绍了其模式、分类与求解思路。

标准形式

\begin{aligned} \mathcal{P}_1: \qquad \min \quad&f(x) \\ s.t. \quad&x \in \mathcal{X} \qquad \quad \end{aligned}

\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}


实例

稀疏优化(信号还原)

\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}

图 1 稀疏性

低秩矩阵恢复

\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}


步骤与分类


最优解

$\mathcal{P}_1$ 的最优解(定义). 对于 $\bar{x} \in \mathcal{X}$:

图 2 解的形式

解的形式


渐进收敛速度

$Q$- 收敛速度

对于充分大的 $k$,若有:

差距越小,速度越快,注意 $\| 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})$。


优化算法设计技巧

最后

本文所使用的图片来自北京大学开设的凸优化课程的官方教材

转载申请

本作品采用 知识共享署名 4.0 国际许可协议 进行许可, 转载时请注明原文链接。您必须给出适当的署名,并标明是否对本文作了修改。

您也可以通过下方按钮直接分享本页面:


发表评论

登录以发表评论

最新评论


Designed & written by Hailiang Zhao.
hliangzhao.cn. Copyright © 2021 - 2022 | 浙ICP备2021026965号-1
Manage