# 数据科学和机器学习中的优化理论与算法（上）

本场 Chat 从基础知识的角度，用大白话对数据科学和机器学习中用到的最重要的优化理论和算法做个小结。

本场 Chat 内容如下：

• 优化中涉及的线性代数数学基础
• 优化理论中最常提到的一些定义、定理
• 求解无约束优化问题的常用算法简介
• 线搜索方法简述（梯度下降法、牛顿法等）
• 信赖域方法的数学原理与算法
• 共轭梯度方法（线性 CG、非线性 CG）
• 拟牛顿方法（DFP、BFGS、SR1、BB）
• 最小二乘问题算法概述
• 约束优化理论（拉格朗日条件、KKT、对偶）
• 非线性约束优化算法（积极集、内点法）
• 二次规划问题的相关算法（SQP 等）
• 罚方法机器改进（ALM、Dual Ascent、ADMM）

编辑器不支持长文，文章分为上下。

数据科学和机器学习当前越来越热，其中涉及的优化知识颇多。很多人在做机器学习或者数据科学时，对其中和优化相关的数学基础，包括随机梯度下降、ADMM、KKT 条件，拉格朗日乘数法、对偶问题等，不太了解，一知半解地用，用着用着就出错了。

本文希望从基础知识的角度，尽可能全地对最简单的优化理论和算法做一个小结。内容涵盖以下几个方面：优化简介、无约束优化、线搜索方法、信赖域方法、共轭梯度方法、拟牛顿方法、最小二乘问题、非线性方程、约束优化理论、非线性约束优化算法、二次规划、罚方法......

通过本文档的学习，相信你会掌握数据科学和机器学习中用到的优化基础知识，以后再遇到优化问题，就不会再困惑了。

建议收藏，方便时时查阅。

简介 数学背景

所谓的优化，在数学上说呢，就是最小化或者最大化一个函数，使得这个函数的变量满足一些约束。我们一般用 $x$ 向量来表示变量，称为未知数或者叫参数。 $f$ 叫做目标函数，它是我们想要最大化或者最小化的一个标量函数。$c_i$ 我们称之为约束函数，用来定义和 $x$ 必须要满足的确定的等式或者不等式约束。优化问题标准的数学方程一般写成下述形式：

$$\begin{array}{ll}{\min {x \in \mathbb{R}^{n}}} & {f(x)} \{\text { subject to }} & {c{i}(x)=0, \quad i \in \mathcal{E}=\left{1, \ldots, m{e}\right}}\& {c{i}(x) \geq 0, \quad i \in \mathcal{I}=\left{m_{e}+1, \ldots, m\right}}\end{array}\tag{1}$$

这里的 $\mathcal{E}$ 表示等式约束的指标集，$\mathcal{I}$ 表示不等式约束的指标集。规划问题又可分为线性规划和非线性规划，一般来说，只要目标函数或者约束函数当中有一个是非线性的，我们就称之为非线性规划。

分类

按照目标函数和约束函数的性质、变量的规模、函数的光滑性，我们可以粗略地将优化问题按如下分类：

• 连续优化和离散优化

• 全局最优化和局部最优化

• 光滑优化和非光滑优化

• 随机优化和确定性优化

• 约束优化和无约束优化：等式约束和不等式约束的指标集都为空集称为约束优化，否则称为无约束优化

• 凸优化和非凸优化

当然，还有一些别的分类方式，比如线性和非线性、可微和不可微、大规模和小规模等等。

凸性

• 一个集合 $S \in \Re^{n}$ 被称为凸集，如果对于任意的两个点，$x \in S,y\in S$，对任意的 $\alpha \in[0,1]$，我们有 $\alpha x+(1-\alpha) y \in S$。

• 我们说 $f$ 是个凸函数，当它的定义域是个凸集，并且下式满足。当下式对于 $x\neq y$，且 $\alpha$ 在开区间 $(0,1)$ 上严格成立（取不到等号）时，我们称 $f$ 是严格凸的。若 $-f$ 是凸函数，那么 $f$ 就是一个凹函数。

$$f(\alpha x+(1-\alpha) y) \leq \alpha f(x)+(1-\alpha) f(y) \quad \forall \alpha \in[0,1]$$

• 所谓的凸优化，一般说的是在约束优化问题中，目标函数是凸的，等式约束是线性的，且不等式约束函数是凹函数。为什么不等式约束是凹函数呢？因为我们这里定义的不等式是 $c_{i}(x) \geq 0$，若改成 $\leq$，则是凸函数。

优化算法

优化算法一般都是一些迭代型的算法。所谓的迭代，就是先给定一个初值，然后通过一定的算法按照 $x_{k} \rightarrow x_{k+1}, \quad k=1,2, \ldots$ 的方式进行迭代更新。优化算法往往有一些评价指标。

• 鲁棒性（Robustness）：对于不同问题和初值都要是表现良好。

• 有效性（Efficiency）：不需要额外的时间和内存。

• 准确性（Accuracy）：能够准确地求解，不能对数据误差或者算法在数值计算时产生的舍入误差过度敏感。

除了以上几点，个人认为应该还添加上以下几点：收敛性、最优性、可扩展性、可靠性、可用性。

背景材料 向量和矩阵

• 向量的表示用 $x \in \mathbb{R}^{n}: x=\left(x_{1}, \ldots, x_{n}\right)^{T}$。

• 向量內积：给定 $x, y \in \mathbb{R}^{n}, x^{T} y=\sum_{i=1}^{n} x_{i} y_{i}$。

• 矩阵的表示用 $A \in \mathbb{R}^{m \times n}$。

• 半正定矩阵：$x^{T} A x \geq 0$ 对于任意的 $x \in \mathbb{R}^{n}$。

• 正交矩阵：$Q^{T} Q=Q Q^{T}=I$

• 特征值和特征向量：$A x=\lambda x$。

向量范数

• ${x \in \mathbb{R}^{n} \text { . }}$

$$\begin{array}{l} {\qquad \begin{aligned} l{1} \text { -norm: } &\|x\|{1}=\sum{i=1}^{n}\left|x{i}\right| \ l{2} \text { -norm: } &\|x\|{2}=\left(\sum{i=1}^{n} x{i}^{2}\right)^{1 / 2}=\left(x^{T} x\right)^{1 / 2} \ l{\infty} \text { -norm: } &\|x\|{\infty}=\max {i=1, \ldots, n}\left|x{i}\right| \end{aligned}} \end{array}$$

• $\|x\|_{\infty} \leq\|x\|_{2} \leq \sqrt{n}\|x\|_{\infty}$ 且 $\|x\|_{\infty} \leq n\|x\|_{\infty}$。

• 柯西-斯瓦茨不等式：$\left|x^{T} y\right| \leq\|x\|_{2}\|y\|_{2}$。

对偶范数

$\|\cdot\|$ 的对偶范数：

$$\|x\|_{D}=\max _{\|y\|=1} x^{T} y=\max _{y \neq 0} \frac{x^{T} y}{\|y\|}$$

根据对偶范数的定义，容易知道 $\left|x^{T} y\right| \leq\|y\|\|x\|_{D}$。

矩阵范数

• 给定 $A \in \mathbb{R}^{m \times n},$ 定义 $\|A\|=\sup _{x \neq 0} \frac{\|A x\|}{\|x\|}$，有

$$\begin{array}{l} {\|A\|_{1}=\max _{j=1, \ldots, n} \sum{i=1}^{m}\left|A{i j}\right|} \ {\|A\|{2}=\operatorname{largest} \text { eigenvalue of }\left(A^{T} A\right)^{1 / 2}} \ {\|A\|{\infty}=\max {i=1, \ldots, m} \sum{j=1}^{n}\left|A_{i j}\right|} \end{array}$$

• Frobenius范数：

$$\|A\|_{F}=\left(\sum_{i=1}^{m} \sum_{j=1}^{n} A_{i j}^{2}\right)^{1 / 2}$$

• 条件数：$\kappa(A)=\|A\|\left\|A^{-1}\right\|$。

子空间

所谓子空间，给定 $\mathcal{S} \subset \mathbb{R}^{n}$，若 $x, y \in \mathcal{S}$ ，那么 $\alpha x+\beta y \in \mathcal{S},$ 对于所有的 $\alpha, \beta \in \mathbb{R}$。零空间：$\operatorname{Null}(A)=\{w | A w=0\}$，值空间：$\operatorname{Range}(A)=\{w | w=A v \text { for some vector } v\}$，零空间和转置的值空间的直和为全空间：Null$(A) \oplus$ Range $\left(A^{T}\right)=\mathbb{R}^{n}$。

导数

• Frechet 可微性:$f: \mathbb{R}^{n} \rightarrow \mathbb{R},$ 在 $x$ 处是可微的，若 $\exists g \in \mathbb{R}^{n}$ 使得：

$$\lim _{y \rightarrow 0} \frac{f(x+y)-f(x)-g^{T} y}{\|y\|}=0$$

• $f$ 的梯度：

$$g(x)=\nabla f(x)=\left(\frac{\partial f}{\partial x_{1}}, \ldots, \frac{\partial f}{\partial x_{n}}\right)^{T} \in \mathbb{R}^{n}$$

• $f$ 的 Hessian 矩阵：

$$H(x)=\nabla^{2} f(x)=\left[\frac{\partial^{2} f}{\partial x_{i} \partial x_{j}}\right] \in \mathbb{R}^{n \times n}$$

• 链式法则 1：

$$\frac{d \phi(\alpha(\beta))}{d \beta}=\phi^{\prime}(\alpha) \alpha^{\prime}(\beta)$$

• 链式法则 2：$x, t \in \mathbb{R}^{n}$ 且 $x=x(t)$，定义 $h(t)=f(x(t))$，那么

  $$\nabla h(t)=\sum_{i=1}^{n} \frac{\partial f}{\partial x_{i}} \nabla x_{i}(t)=\nabla x(t)^T \nabla f(x(t))$$

• 方向导数：$D(f(x): p)=\lim _{\epsilon \rightarrow 0} \frac{f(x+\epsilon p)-f(x)}{\epsilon}=\nabla f(x)^{T} p$。

收敛率

令 $\left\{x_{k}\right\}$ 是 $\mathbb{R}^{n}$ 的一个序列，收敛到 $x^{*}$。

• Q-线性收敛说的是存在一个常数 $r\in(0,1)$，使得当 $k$ 充分大时，有：

  $$\frac{\left\|x_{k+1}-x_{*}\right\|}{\left\|x_{k}-x^{*}\right\|} \leq r$$

• Q-超线性收敛指的是：

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

• Q-二次收敛指的是，存在一个常数 $M$，使得当 $k$ 充分大时，

  $$\frac{\left\|x_{k+1}-x_{*}\right\|}{\left\|x_{k}-x^{*}\right\|^{2}} \leq M$$

无约束优化

$f: \Re^{n} \rightarrow \Re$ 是一个光滑函数，无约束优化指的就是没有约束的优化。

$$\min _{x \in \mathbb{R}^{n}} f(x)$$

不同说法的解

全局极小值指的是

$$f\left(x^{*}\right) \leq f(x) \quad \text { for all } x \in \mathbb{R}^{n}$$

局部极小值指的是存在 $x^{*}$ 的一个领域 $\mathcal{N}$，

$$f\left(x^{*}\right) \leq f(x) \quad \text { for all } x \in \mathcal{N}$$

严格的局部极小值，

$$f\left(x^{*}\right)