最优化问题泛指定量决策问题，主要关心如何对有限资源进行有效分配和控制，并达到某种意义上的最优。

它通常需要对需求进行定性和定量分析，建立恰当的数学模型来描述该问题，设计合适的计算方法来寻找问题的最优解，探索研究模型和算法的理论性质，考察算法的计算性能等。

由于很多数学问题难以直接给出显式解，最优化模型就成为人们最常见的选择。

最优化问题概括

最优化问题的一般形式

该问题一般可以描述为：

$$\begin{aligned}\min & f(x), \\\text { s.t. } & x \in \mathcal{X},\end{aligned}\tag{1}$$

其中，$x=\left(x_{1}, x_{2}, \cdots, x_{n}\right)^{\mathrm{T}} \in \mathbb{R}^{n}$ 是决策变量，$f:\mathbb{R}^{n}\to \mathbb{R}$ 是目标函数，$\mathcal{X}\subseteq \mathbb{R}^{n}$ 是约束集合或可行域，可行域包含的点称为可行解或可行点。记号 $\text { s.t. }$ 是 “subject to”的缩写，专指约束条件。

当 $\mathcal{X}=\mathbb{R}^{n}$ 时，该问题则是无约束优化问题。集合 $\mathcal{X}$ 通常可以由约束函数 $c_i(x):\mathbb{R}^{n}\to \mathbb{R},i=1,2,\cdots,m+l$ 表达为如下形式：

$$\begin{array}{c c}{{\chi=\{x\in\mathbb{R}^{n}\mid\ c_{i}(x)\leqslant0,}}&{{i=1,2,\cdots,m,}}\\ {{c_{i}(x)=0,}}&{{i=p+1,m+2\cdot\cdot\cdot,m+l\}.}}\end{array}$$

在所有满足约束条件的决策变量中，使目标函数取最小值的变量 $x^∗$ 称为优化问题 (1) 的最优解。即对任意 $x\in\mathcal{X}$ 都有 $f(x) \geqslant f\left(x^*\right)$。

注意到在集合 $\mathcal{X}$ 上，函数 $f$ 的最小值不一定存在，但是其下确界$" \inf "$总是存在的。因此，当目标函数的最小值不存在时，我们便关心其下确界，即将问题 (1) 中的 “$\min$” 改为 “$\inf$”

实际上，根据具体应用和需求，$x$ 还可以是矩阵、多维数组 或张量等.

** $\mathbb{R}$：实数集合，$\mathbb{R}^{n}$：$n$ 维欧几里得空间

最优化问题的类型与应用背景

最优化问题 (1) 的具体形式非常丰富，可以按照目标函数、约束函数以及解的性质将其分类。

目标函数和约束函数的形式来分：

• 当目标函数和约束函数均为线性函数时，问题 (1) 称为线性规划；
• 当目标函 数和约束函数中至少有一个为非线性函数时，相应的问题称为非线性规划
• 如果目标函数是二次函数而约束函数是线性函数则称为二次规划
• 包含非光滑函数的问题称为非光滑优化
• 不能直接求导数的问题称为无导数优化
• 变量只能取整数的问题称为整数规划
• 在线性约束下极小化关于半正定矩阵的线性函数的问题称为半定规划，其广义形式为锥规划．

按照最优解的性质来分：

• 最优解只有少量非零元素的问题称为稀疏优化
• 最优解是低秩矩阵的问题称为低秩矩阵优化

此外还有几何优化、二次锥规划、张量优化、 鲁棒优化、全局优化、组合优化、网络规划、随机优化、动态规划、带微分方程约束优化、微分流形约束优化、分布式优化等。

数学建模很容易给出应用问题不同的模型，可以对应性质很不相同的问题，其求解难度和需要的算法也将差别很大。

最优化的基本概念

一般来说，最优化算法研究可以分为：构造最优化模型、确定最优化问题类型和设计实现或调用优化算法进行求解。

最优化模型

最优化模型的构造和实际问题紧密相关，比如说，给定二维欧几里得（Euclid）空间 的若干个离散点，假定它们可以通过一条直线分成两部分，也可以通过一条曲线分成两部分．那么分别使用直线与曲线所得到的最优化模型是不同的．
在问题 (1) 中，目标函数 $f$ 和约束函数 $c_i$ 都是由模型来确定的。

最优化问题类型

不存在对于所有优化问题的统一的算法．需要针对具体优化问题所属的类型，来设计或者调用相应的算法求解器。

连续和离散优化问题

最优化问题可以分为连续优化和离散优化问题两大类：

• 连续优化问题是指决策变量所在的可行集合是连续的，比如平面、区间等，其约束集合就是连续的。
• 离散优化问题是指决策变量能在离散集合上取值，比如离散点集、整数集等．常见的离散优化问题有整数规划，其对应的决策变量的取值范围是整数集合。

在连续优化问题中，基于决策变量取值空间以及约束和目标函数的连续性，我们可以从一个点处目标和约束函数的取值来估计该点可行邻域内的取值情况．进一步地，可以根据邻域内的取值信息来判断该点是否最优。

离散优化问题则不具备这个性质，因为决策变量是在离散集合上取值**．因此 在实际中往往比连续优化问题更难求解．实际中的离散优化问题往往可以转化为一系列**连续优化问题来进行求解．

因此连续优化问题的求解在最优化理论与算法中扮演着重要的角色。

无约束和约束优化问题

最优化问题的另外一个重要的分类标准是约束是否存在：

• 无约束优化问题的决策变量没有约束条件限制，即可行集合 $X =R^n$
• 约束优化问题是指带有边界约束条件的问题

可以通过将约束罚到目标函数上转化为无约束问题，所以在某种程度上，约束优化问题就是无约束优化问题。很多约束优化问题的求解也是转化为一系列的无约束优化问题来做，常见方式有增广拉格朗日函数法、罚函数法等．

约束优化问题的理论以及算法研究仍然是非常重要的．主要原因是，借助于约束函数，我们能够更好地
描述可行域的几何性质，进而更有效地找到最优解。

随机和确定性优化问题

• 随机优化问题是指目标或者约束函数中涉及随机变量而带有不确定性的问题。
• 确定性优化问题中目标和约束函数都是确定的，

随机优化问题在机器学习、深度学习以及强化学习中有着重要应用，其优化问题的目标函数是关于一个未知参数的期望的形式．因为参数的未知性，实际中常用的方法是通过足够多的样本来逼近目标函数，得到一个新的有限和形式的目标函数。由于样本数量往往非常大，我们还是将这个问题看作相对于指标随机变量的期望形式，然后通过随机优化方法来进行求解。

相比于确定性优化问题，随机优化问题的求解往往涉及更多的随机性． 很多确定性优化算法都有相应的随机版本．

随机性使得这些算法在特定问题上具有更低的计算复杂度或者更好的收敛性质．以目标函数为多项求和的优化问题为例，如果使用确定性优化算法，每一次计算目标函数的梯度都会引入昂贵的复杂度．但是对于随机优化问题，我们每次可能只计算和式中的一项或者几项，这大大减少了计算时间．同时我们还能保证算法求解的足够精确．

线性和非线性规划问题

线性规划是指问题 (1) 中目标函数和约束函数都是线性的，例如：

$$\begin{aligned}& \min F=6x_1+5x_2 \\& \text { s.t. }\left\{\begin{array}{l}2 x_1+3 x_2 \leq 10 \\4 x_1+2 x_2 \leq 12\\x_1, x_2 \geq 0\end{array}\right.\end{aligned}$$

当目标函数和约束函数至少有一个是非线性的，那么对应的优化问题的称为非线性规划问题，例如：

$$\begin{aligned}& \min F=x_1^2+x_2^2+8 \\& \text { s.t. }\left\{\begin{array}{l}x_1^2-x_2 \geq 0 \\-x_1-x_2^2+2=0 \\x_1, x_2 \geq 0\end{array}\right.\end{aligned}$$

凸和非凸优化问题

• 凸优化问题是指最小化问题 (1) 中的目标函数和可行域分别是凸函数和凸集．
• 如果其中有一个或者两者都不是凸的，那么相应的最小化问题是非凸优化问题．

若问题 (1) 中的 $min$ 改为 $max$，且目标函数和可行域分别为凹函数和凸集，我们也称这样的问题为凸优化问题．这是因为对凹函数求极大等价于对其相反数（凸函数）求极小．

在实际问题的建模中，我们经常更倾向于得到一个凸优化模型．另外， 判断一个问题是否是凸问题也很重要．比如，给定一个非凸优化问题，一种方法是将其转化为一系列凸优化子问题来求解逼近原问题．

优化算法

同一类优化问题往往存在着不同的求解算法．对于具体的优化问题，我们需要充分利用问题的结构，并根据问题的需求（求解精度和速度等）来设计相应的算法．另外，根据算法得到的结果，我们可以来判别模型构造是否合理或者进一步地改进模型．

全局和局部最优解

对于可行点 $\bar{x}$ (即 $\bar{x} \in \mathcal{X}$ ), 定义如下概念：

• 如果 $f(\bar{x}) \leqslant f(x), \forall x \in \mathcal{X}$, 那么称 $\bar{x}$ 为问题 (1) 的全局极小解 (点) ，有时也称为 (全局) 最优解或最小值点;
• 如果存在 $\bar{x}$ 的一个 $\varepsilon$ 邻域 $N_{\varepsilon}(\bar{x})$ 使得 $f(\bar{x}) \leqslant f(x), \forall x \in N_{\varepsilon}(\bar{x}) \cap \mathcal{X}$, 那 么称 $\bar{x}$ 为问题 (1.1.1) 的局部极小解（点），有时也称为局部最优解;
• 进一步地, 如果有 $f(\bar{x})<f(x), \forall x \in N_{\varepsilon}(\bar{x}) \cap \mathcal{X}, x \neq \bar{x}$ 成立, 则称 $\bar{x}$ 为问题 (1) 的严格局部极小解 (点).

如果一个点是局部极小解, 但不是严格局部极小解, 我们称之为非严格局部极小解.

在问题 (1) 的求解中, 我们想要得到的是其全局最优解, 但是由于 实际问题的复杂性, 往往只能够得到其局部最优解.

显式解

对于一个优化问题，如果我们能用代数表达式给出其最优解，那么这个解称为显式解，对应的问题往往比较简单．例如二次函数在有界区间上的极小化问题，通过比较其在对称轴点上和区间两个端点处的值得到最优解，这个解可以显式地写出．但实际问题往往是没有办法显式求解的，因此常采用迭代算法．

迭代法

从一个初始点 $x^0$ 出发，按照某种给定的规则进行迭代，得到一个序列 ${x^k}$．如果迭代在有限步内终止，那么希望最后一个点就是优化问题的解．如果迭代点列是无穷集合，那么希望该序列的极限点（或者聚点）则为优化问题的解。

为了使算法能在有限步内终止，我们一般会通过一些收敛准则来保证迭代停在问题的一定精度逼近解上．对于无约束优化问题，常用的收敛准则有：

$$\frac{f\left(x^k\right)-f^*}{\max \left\{\left|f^*\right|, 1\right\}} \leqslant \varepsilon_1, \quad\left\|\nabla f\left(x^k\right)\right\| \leqslant \varepsilon_2$$

其中 $\varepsilon_1, \varepsilon_2$ 为给定的很小的正数, $\|\cdot\|$ 表示某种范数（这里可以简单理解为 $\ell_2$ 范数: $\|x\|_2=\left(\sum_{i=1}^n x_i^2\right)^{1 / 2}$), $f^*$ 为函数 $f$ 的最小值（假设已知或者以某种方式估计得到）以及 $\nabla f\left(x^k\right)$ 表示函数 $f$ 在点 $x$ 处的梯度 (光滑函数在局部最优点处梯度为零向量)，描述了函数值与最优值的相对误差.

对于约束优化问题, 还需要考虑约束违反度. 具体地, 要求最后得到的点满足

$$\begin{aligned} c_i\left(x^k\right) \leqslant \varepsilon_3, i & =1,2, \cdots, m \\ \left|c_i\left(x^k\right)\right| \leqslant \varepsilon_4, i & =m+1, m+2, \cdots, m+l, \end{aligned}$$

其中 $\varepsilon_3, \varepsilon_4$ 为很小的正数, 用来刻画 $x^k$ 的可行性.

由于一般情况下事先并不知道最优解, 在最优解唯一的情形下一般使用某种基准算法来得到 $x^*$ 的一个估计, 之后计算其与 $x^k$ 的距离以评价算法的性能. 因为约束的存在, 我们不能简单地用目标函数的梯度来判断最优性, 实际中采用的判别准则是点的最优性条件的违反度.

对于一个具体的算法, 根据其设计的出发点, 我们不一定能得到一个高精度的逼近解. 此时, 为了避免无用的计算开销, 我们还需要一些停机准则来及时停止算法的进行. 常用的停机准则有

$$\frac{\left\|x^{k+1}-x^k\right\|}{\max \left\{\left\|x^k\right\|, 1\right\}} \leqslant \varepsilon_5, \quad \frac{\left|f\left(x^{k+1}\right)-f\left(x^k\right)\right|}{\max \left\{\left|f\left(x^k\right)\right|, 1\right\}} \leqslant \varepsilon_6,$$

这里的各个 $\varepsilon$ 一般互不相等. 上面的准则分别表示相邻迭代点和其对应目标函数值的相对误差很小. 在算法设计中，这两个条件往往只能反映迭代点列接近收敛，但不能代表收敛到优化问题的最优解.

在算法设计中，一个重要的标准是算法产生的点列是否收敛到优化问题的解. 对于问题 (1), 其可能有很多局部极小解和全局极小解, 但所有全局极小解对应的目标函数值, 即优化问题的最小值 $f^*$ 是一样的. 考虑无约束的情形, 对于一个算法, 给定初始点 $x^0$, 记其迭代产生的点列为 $\left\{x^k\right\}$. 如果 $\left\{x^k\right\}$ 在某种范数 $\|\cdot\|$ 的意义下满足

$$\lim _{k \rightarrow \infty}\left\|x^k-x^*\right\|=0$$

且收玫的点 $x^*$ 为一个局部（全局）极小解, 那么我们称该点列收敛到局部 （全局）极小解，相应的算法称为是依点列收敛到局部（全局）极小解的.

在算法的收敛分析中, 初始迭代点 $x^0$ 的选取也尤为重要. 比如一般的牛顿法, 只有在初始点足够接近局部 (全局) 最优解时, 才能收敛. 但是这样的初始点的选取往往比较困难, 此时我们更想要的是一个从任何初始点出发都能收玫的算法. 因此优化算法的研究包括如何设计全局化策略, 将已有的可能发散的优化算法修改得到一个新的全局收敛到局部（全局）最优解的算法. 比如通过采用合适的全局化策略, 我们可以修正一般的牛顿法使得修改后的算法是全局收敛到局部（全局）最优解的.

进一步地, 如果从任意初始点 $x^0$ 出发, 算法都是依点列收玫到局部 (全局）极小解的, 我们称该算法是全局依点列收敛到局部（全局）极小解的.

相应地, 如果记对应的函数值序列为 $\left\{f\left(x^k\right)\right\}$, 我们还可以定义算法的（全局）依函数值收敛到局部 (全局) 极小值的概念. 对于凸优化问题, 因为其任何局部最优解都为全局最优解, 算法的收敛性都是相对于其全局极小而 言的.

除了点列和函数值的收敛外, 实际中常用的还有每个迭代点的最优性条件 (如无约束优化问题中的梯度范数, 约束优化问题中的最优性条件违反度等等）的收敛.

对于带约束的情形, 给定初始点 $x^0$, 算法产生的点列 $\left\{x^k\right\}$ 不一定是可行的 (即 $x^k \in \mathcal{X}$ 末必对任意 $k$ 成立). 考虑到约束违反的情形, 我们需要保证 $\left\{x^k\right\}$ 在收敛到 $x^*$ 的时候, 其违反度是可接受的. 除此要求之外, 算法的收敛性的定义和无约束情形相同.

简化优化问题

在设计优化算法时, 我们有一些基本的准则或技巧. 对于复杂的优化问题, 基本的想法是将其转化为一系列简单的优化问题 (其最优解容易计算或者有显式表达式）来逐步求解. 常用的技巧有：

• 泰勒 (Taylor) 展开. 对于一个非线性的目标或者约束函数, 通过其泰勒展开用简单的线性函数或者二次函数来逼近, 从而得到一个简化的问题. 因为该简化问题只在小邻域内逼近原始问题，所以需要根据迭代点的更新来重新构造相应的简化问题.
• 对偶. 每个优化问题都有对应的对偶问题. 特别是凸的情形, 当原始问题比较难解的时候, 其对偶问题可能很容易求解.通过求解对偶问题或者同时求解原始问题和对偶问题, 我们可以简化原始问题的求解，从而设计更有效的算法.
• 拆分. 对于一个复杂的优化问题, 我们可以将变量进行拆分, 比 如 $\min _x h(x)+r(x)$, 可以拆分，通过引人更多的变量, 我们可以得到每个变量的简单问题（较易求解或者解有显式表达式), 从而通过交替求解等方式来得到原问题的解.

$$\min _{x, y} h(x)+r(y), \text { s.t. } x=y .$$

• 块坐标下降. 对于一个 $n$ 维空间 ( $n$ 很大) 的优化问题, 我们可以通过逐步求解分量的方式将其转化为多个低维空间中的优化问题．比如，对于 $n$ =100，我们可以先固定第 2—100 个分量， 来求解 $x_1$ ;固定下标为 1,3—100的分量来求解 $x_2$；依次类推．

Q-收敛速度

算法重要的指标是渐进收敛速度．以点列的 Q-收敛速度（Q的含义为“quotient”）为例

设 $\left\{x^k\right\}$ 为算法产生的迭代点列且收玫于 $x^*$,

若算法（点列）是 $\mathrm{Q}$-线性收敛的，则对充分大的 $k$ 有

$$\frac{\left\|x^{k+1}-x^*\right\|}{\left\|x^k-x^*\right\|} \leqslant a, \quad a \in(0,1),$$

若满足算法（点列）是 $\mathrm{Q}$-超线性收敛的，则有

$$\lim _{k \rightarrow \infty} \frac{\left\|x^{k+1}-x^*\right\|}{\left\|x^k-x^*\right\|}=0,$$

若算法（点列）是 $\mathbf{Q}$-次线性收敛的，则有

$$\lim _{k \rightarrow \infty} \frac{\left\|x^{k+1}-x^*\right\|}{\left\|x^k-x^*\right\|}=1 \text {, }$$

若算法 (点列) 是 $\mathbf{Q}$ 二次收玫，则对充分大的 $k$ 满足

$$\frac{\left\|x^{k+1}-x^*\right\|}{\left\|x^k-x^*\right\|^2} \leqslant a, \quad a>0,$$

类似地, 也可定义更一般的 $Q-r$ 次收玫 $(r>1)$.

以上更直观地展示不同的 Q-收玫速度,. 点列 $\left\{2^{-k}\right\}$ 是 $\mathrm{Q}$-线性收敛的，点列 $\left\{2^{-2^k}\right\}$ 是 $\mathrm{Q}$ 二次收玫的 (也是 $\mathrm{Q}$-超线性收玫的), 点列 $\left\{\frac{1}{k}\right\}$ 是 $\mathrm{Q}$ 次线性收玫的 一般来说, 具有 $\mathrm{Q}$-超线性收玫速度和 Q-二次收玫速度的算法是收玫较快的.

R-收敛速度

另一常用概念是 R-收敛速度（R 的含义为 “root"） 以点列为例, 设 $\left\{x^k\right\}$ 为算法产生的迭代点且收玫于 $x^*$, 若存在 $\mathrm{Q}$-线性收敛于 0 的非负序列 $t_k$ 并且

$$\left\|x^k-x^*\right\| \leqslant t_k$$

对任意的 $k$ 成立，则称算法 (点列) 是 $\mathrm{R}$-线性收敛的. 类似地，可定义 $\mathrm{R}$-超线性收敛和 $\mathrm{R}$-二次收敛等收玫速度. 从 $\mathrm{R}$-收玫速度的定义可以看出序列$\left\{\left\|x^k-x^*\right\|\right\}$ 被另一趋于 0 的序列 $\left\{t_k\right\}$ 控制. 当知道 $t_k$ 的形式时, 我们也称 算法 (点列) 的收敛速度为 $\mathcal{O}\left(t_k\right)$.

复杂度与收敛速度

与收敛速度密切相关的概念是优化算法的复杂度 $N(\varepsilon)$, 即计算出给定精度 $\varepsilon$ 的解所需的迭代次数或浮点运算次数. 在实际应用中, 这两种定义复杂度的方式均很常见. 如果能较准确地估计每次迭代的运算量, 则可以由算法所需迭代次数推出所需浮点运算次数. 我们用具体的例子来进一步解释算法复杂度. 设某一算法产生的迭代序列 $\left\{x^k\right\}$ 满足

$$f\left(x^k\right)-f\left(x^*\right) \leqslant \frac{c}{\sqrt{k}}, \quad \forall k>0,$$

其中 $c>0$ 为常数, $x^*$ 为全局极小点. 如果需要计算算法满足精度 $f\left(x^k\right)-$ $f\left(x^*\right) \leqslant \varepsilon$ 所需的迭代次数, 只需令 $\frac{c}{\sqrt{k}} \leqslant \varepsilon$ 则得到 $k \geqslant \frac{c^2}{\varepsilon^2}$, 因此该优化算法 对应的 (迭代次数) 复杂度为 $N(\varepsilon)=\mathcal{O}\left(\frac{1}{\varepsilon^2}\right)$.

注意, 渐进收玫速度更多的是考虑迭代次数充分大的情形, 而复杂度给出了算法迭代有限步之后产生的解与最优解之间的定量关系.

实例：稀疏优化

考虑线性方程组求解问题：

$$Ax=b\tag{2}$$

其中向量$x \in \mathbb{R}^n, b \in \mathbb{R}^m$，矩阵 $A \in \mathbb{R}^{m \times n}$，且向量 $b$ 的维数远小于向量 $x$ 的维数，即 $m≪n$。

在自然科学和工程中常常遇到已知向量 $b$ 和矩阵 $A$，想要重构向量 $x$ 的问题．例如在信号传输过程中，希望通过接收到长度为 $m$ 的数字信号精确地重构原始信号。

注意到由于 $m≪n$，方程组 (2) 是欠定的，因此存在无穷多个解，重构出原始信号看似很难．

但这些解当中大部分是我们不感兴趣的，真正有用的解是所谓的“稀疏解”，即原始信号中有较多的零元素．如果加上稀疏性这一先验信息，且矩阵 $A$ 以及原 问题的解 $x$ 满足某些条件，那么我们可以通过求解稀疏优化问题把 $x$ 与方程组 (2) 的其他解区别开．这类技术广泛应用于压缩感知（compressive sensing），即通过部分信息恢复全部信息的解决方案。

实例建模

假设构造一个矩阵 $A$ 为 $128\times256$ 大小，且元素服从高斯分布。使得：

$$Au=b$$

其中 $u$ 只有 10% 的元素为非零元素，元素服从高斯分布。这些特征可以在理论上保证 $u$ 是方程组 (2) 唯一的非零元素最少的解，

即 $u$ 是如下 $ℓ_0$ 范数问题的最优解：

$$\begin{aligned}\min _{x \in \mathbb{R}^n} & \|x\|_0, \\\text { s.t. } & A x=b .\end{aligned}\tag{2.1}$$

其中 $\|x\|_0$ 是指 $x$ 中非零元素的个数. 由于 $\|x\|_0$ 取值只可能是整数, 该问题实际上是 NP (non-deterministic polynomial) 难题,。

所以需要将问题转化为连续性问题. 若定义 $\ell_1$ 范数: $\|x\|_1=\sum_{i=1}^n\left|x_i\right|$ , 并将其替换到问题 (2.1) 当中, 我们得到了另一个形式上非常相似的问题（又称 $\ell_1$ 范数优化问题，基追踪问题）：

$$\begin{aligned}\min _{x \in \mathbb{R}^n} & \|x\|_1, \\\text { s.t. } & A x=b .\end{aligned}\tag{2.2}$$

令人惊讶地是, 可以从理论上证明：若 $A, b$ 满足一定的条件（例如使用前 面随机产生的 $A$ 和 $b$ ) ，向量 $u$ 也是 $\ell_1$ 范数优化问题 (2.2) 的唯一最优解.

虽然问题 $(2.2)$ 仍没有显式解, 但与问题 (2.1) 相比难度已经大大降低. 前面我们提到 $\ell_0$ 范数优化问题是 NP 难问 题, 但 $\ell_1$ 范数优化问题的解可以非常容易地通过现有优化算法得到.

是否能使用其他更容易求解的范数替代 $\ell_0$ 范数呢? 事实并非如此. 如果简单地把 $\ell_1$ 范数修改为 $\ell_2$ 范数: $\|x\|_2=\left(\sum_{i=1}^n x_i^2\right)^{1 / 2}$, 即求解如下优化问题:

$$\begin{aligned}\min _{x \in \mathbb{R}^n} & \|x\|_2, \\\text { s.t. } & A x=b .\end{aligned}\tag{2.3}$$

几何学的知识表明, 问题 (2.3) 实际上就是原点到仿射集 $A x=b$ 的投影, 我们可以直接写出它的显式表达式. 但 $u$ 并不是问题 (2.3) 的解.

事实上, 下图分别给出了一组随机数据下的精确解 $u$, 以及问题 (2.2) 和 问题 (2.3) 的数值解. 可以看出 精确解 $u$和 问题 (2.2)的解 是完全一样的, 而 问题 (2.3)的解 则与 $u$ 相去甚远, 虽然隐约能看出数据点的大致趋势, 但已经不可分辨非零元素的具体位置. 这是由于 $ℓ_0, ℓ_1, ℓ_2$ 范数的性质造成的

ℓ0, ℓ1, ℓ2 范数的性质

定义在二维空间上欠定方程组 $A x=b$, 此时 $A x=b$ 是一条直线. 在几何上, 三种优化问题实际上要找到最小的 $C$, 使得 “范数球” $\{x \mid\|x\| \leqslant C\}$ ( $\|\cdot\|$ 表示任何一种范数) 恰好与 $A x=b$ 相交.

而下图里分别展示了三种范数球的几何直观：

对 $\ell_0$ 范数, 当 $C=2$ 时 $\left\{x \mid\|x\|_0 \leqslant C\right\}$ 是全平面, 它自然与 $A x=b$ 相交, 而当 $C=1$ 时退化成两条直线 (坐标轴), 此时问题的解是 $A x=b$ 和这两条直线的交点;

对$\ell_1$ 范数, 根据 $C$ 不同 $\left\{x \mid\|x\|_1 \leqslant C\right\}$ 为一系列正方形, 这些正方形的顶点恰好都在坐标轴上, 而最小的 $C$ 对应的正方形和直线 $A x=b$ 的交点一般都是顶点, 因此 $\ell_1$ 范数的解有稀疏性;

对 $\ell_2$ 范数, 当 $C$ 取值不同时 $\left\{x \mid\|x\|_2 \leqslant C\right\}$ 为一系列圆, 而圆有光滑的边界, 它和直线 $A x=b$ 的切点可以是圆周上的任何一点, 所以 $\ell_2$ 范数优化问题一般不能保证解的稀疏性.

实例：深度学习

深度学习（deep learning）的起源可以追溯至 20 世纪 40 年代，其雏形出现在控制论中．近十年来深度学习又重新走入了人们的视野，深度学习问题和算法的研究也经历了一次新的浪潮．虽然卷积网络的设计受到了生物学和神经科学的启发，但深度学习目前的发展早已超越了机器学习模型中的 神经科学观点．它用相对简单的函数来表达复杂的表示，从低层特征概括到更加抽象的高层特征，让计算机从经验中挖掘隐含的信息和价值．

多层感知机

多层感知机（multi-layer perceptron, MLP）也叫作深度前馈网络（deep feedforward network）或前馈神经网络（feedforward neural network），它通过已有的信息或者知识来对未知事物进行预测．在神经网络中，已知的信息通常用数据集来表示．

数据集一般分为训练集和测试集：训练集是用来训练神经网络，从而使得神经网络能够掌握训练集上的信息；测试集是用来测试训练完的神经网络的预测准确性．

常见的任务如分类问题．假设我们有一个猫和狗的图片集，将其划分成训练集和测试集（保证集合中猫和狗图片要有一定的比例）．神经网络是想逼近一个从图片到 {0,1} 的函数，这 里 0 表示猫，1 表示狗．因为神经网络本身的结构和大量的训练集信息，训练得到的函数与真实结果具有非常高的吻合性．

具体地, 给定训练集 $D=\left\{\left\{a_1, b_1\right\},\left\{a_2, b_2\right\}, \cdots,\left\{a_m, b_m\right\}\right\}$, 假设数据 $a_i \in \mathbb{R}^p, b_i \in \mathbb{R}^q$. 为了方便处理模型里的偏差项, 还假设 $a_i$ 的第一个元素等 于 1 , 即 $a_{i 1}=1$.

上图给出了一种由 $p$ 个输人单元和 $q$ 个输出单元构成的 $(L+2)$ 层感知机, 其含有一个输人层, 一个输出层, 和 $L$ 个隐藏层. 每一个层之间都是全连接的。

该感知机的第 $l$ 个隐藏层共有 $m^{(l)}$ 个神经元, 为了方便我们用 $l=0$ 表示输人层, $l=L+1$ 表示输出层, 并定义 $m^{(0)}=p$ 和 $m^{(L+1)}=q$. 设 $y^{(l)} \in \mathbb{R}^{m^{(l)}}$ 为第 $l$ 层的所有神经元,

同样地, 为了能够处理每一个隐藏层的信号偏差, 除输出层外, 我们令 $y^{(l)}$ 的第一个元素等于 1 , 即 $y_1^{(l)}=1,0 \leqslant l \leqslant L$, 而其余的元素则是通 过上一层的神经元的值进行加权求和得到.

令参数 $x=\left(x^{(1)}, x^{(2)}, \cdots, x^{(L+1)}\right)$ 表示网络中所有层之间的权重, 其中 $x_{i, k}^{(l)}$ 是第 $(l-1)$ 隐藏层的第 $k$ 个单元 连接到第 $l$ 隐藏层的第 $i$ 个单元对应的权重, 则在第 $l$ 隐藏层中, 第 $i$ 个单 元 $(i>1$, 当 $l=L+1$ 时可取为 $i \geqslant 1)$ 计算输出信息 $y_i^{(l)}$ 为

$$y_i^{(l)}=t\left(z_i^{(l)}\right), \quad z_i^{(l)}=\sum_{k=1}^{m^{(l-1)}} x_{i, k}^{(l)} y_k^{(l-1)} .$$

这里函数 $t(\cdot)$ 称为激活函数, 常见的类型有 Sigmoid 函数

$$t(z)=\frac{1}{1+\exp (-z)}$$

Heaviside 函数

$$t(z)= \begin{cases}1, & z \geqslant 0 \\ 0, & z<0\end{cases}$$

以及 ReLU 函数

$$t(z)=\max \{0, z\}$$

整个过程可以描述为，对上一层计算权重与偏置后通过激活函数得到下一层。

$$y^{(0)} \stackrel{x^{(1)}}{\rightarrow} z^{(1)} \stackrel{t}{\rightarrow} y^{(1)} \stackrel{x^{(2)}}{\rightarrow} \cdots \stackrel{t}{\rightarrow} y^{(L+1)}$$

容易看出, 多层感知机的每一层输出实际就是由其上一层的数值作线性组合再逐分量作非线性变换得到的. 若将 $y^{(0)}$ 视为自变量, $y^{(L+1)}$ 视为因变量, 则多层感知机实际上定义了一个以 $x$ 为参数的函数 $h(a ; x): \mathbb{R}^p \rightarrow \mathbb{R}^q$, 这里 $a$ 为输人层 $y^{(0)}$ 的取值. 当输人数据为 $a_i$ 时, 其输出 $h\left(a_i ; x\right)$ 将作为真实标签 $b_i$ 的估计. 若选择平方误差为损失函数, 则我们得到多层感知机的优化模型:

$$\min _x \sum_{i=1}^m\left\|h\left(a_i ; x\right)-b_i\right\|_2^2+\lambda r(x)$$

其中 $r(x)$ 是正则项, 用来刻画解的某些性质, 如光滑性或稀疏性等; $\lambda$ 称为正则化参数, 用来平衡模型的拟合程度和解的性质. 如果 $\lambda$ 太小, 那么对解的性质没有起到改善作用; 如果 $\lambda$ 太大, 则模型与原问题相差很大, 可能是一个糟糕的逼近.

卷积神经网络

卷积神经网络（convolutional neural network，CNN）是一种深度前馈人工神经网络，专门用来处理如时间序列数据或是图像等网格数据．CNN 在计算机视觉、视频分析、自然语言处理等诸多领域有大量成功的应用．

与 MLP 全连接网络（相邻两层之间的节点都是相连或相关的）不同， 卷积神经网络的思想是通过局部连接以及共享参数的方式来大大减少参数量，从而减少对数据量的依赖以及提高训练的速度．

典型的CNN网络结构通常由一个或多个卷积层、池化层（下采样）（pooling）和顶层的全连接层组成．全连接层的结构与多层感知机的结构相同．卷积层如下图，是一种特殊的网络层，它首先对输入数据进行卷积操作产生多个特征映射，之后使用非线性激活函数（比如ReLU）对每个特征进行变换．下采样层一般位于卷积层之后， 它的作用是减小数据维数并提取数据的多尺度信息，其结果最终会输出到下一组变换．

给定一个二维图像 $I \in \mathbb{R}^{n \times n}$ 和卷积核 $K \in \mathbb{R}^{k \times k}$, 我们定义一种简单的卷积操作 $S=I * K$, 它的元素是

$$\boldsymbol{S}_{i, j}=\langle\mathbf{I}(i: i+k-1, j: j+k-1), \boldsymbol{K}\rangle,$$

其中两个矩阵 $X, Y$ 的内积是它们相应元素乘积之和, 即 $\langle X, Y\rangle=\sum_{i, j} X_{i j} Y_{i j}$, $\boldsymbol{I}(i: i+k-1, j: j+k-1)$ 是矩阵 $\boldsymbol{I}$ 从位置 $(i, j)$ 开始的一个 $k \times k$ 子矩阵. 结果 $S$ 可以根据卷积核的维数、 $I$ 的边界是否填充、卷积操作时滑动的大小等相应变化.

第 $l$ 特征层是第 $(l-1)$ 特征层的下采样层. 具体地, 先将第 $(l-1)$ 层的每个矩阵划分成若干子矩阵, 之后 将每个子矩阵里所有元素按照某种规则（例如取平均值或最大值）变换成一个元素. 因此, 第 $(l-1)$ 特征层每个小框里所有元素的平均值或最大值就对应于第 $l$ 特征层的一个元素. 容易看出, 下采样层实际上是用一个数代表一个子矩阵, 经过下采样层变换后, 前一特征层矩阵的维数会进一步降低.

图上给出了一个简单的卷积神经网络示意图. 输人图片通过不同的卷积核生成的不同矩阵, 再经过非线性激活函数作用后生成第 1 层的特征; 第 2 层是第 1 层的下采样层；第 3 层和第 4 层又是卷积层和下采样层；第 5 层是全 连接层；第 6 层为输出层．实际的卷积神经网络可达几十层甚至更多，卷积核的大小，网络节点之间的连接方式也可以有很多变化，从而生成不一样的模型．