人工智能数学课高等数学线性微积分数学教程笔记（7. 最优化）

前言

对人工智能数学课高等数学线性微积分数学教程的学习笔记。主要用于快速回忆已学的数学知识点，不适合基础学习。博客园中同步更新。

---

---

7. 最优化

- 基本概念

• 求 $f(x)$ 的极大值或极小值，$x$ 是优化变量，就是自变量，$f(x)$ 是目标函数，可能带有约束条件，满足约束并在定义域内的集合叫可行域；
  $$\begin{gathered} \max f(x)\iff \min f(x) \\ {g}_i(x)=0,i=1,\cdots ,m \\ {h}_j(x)\le 0j=1,\cdots ,n \end{gathered}$$

• 局部极小值：任意在 $x_0$ 的领域存在，$f(x)\ge f(x_0),\forall x\in \delta (x_0)$

• 通过大量实践发现在高维度的优化问题中，局部极小值 (local minimum)和全局极小值没有太大的区别，甚至有时候有更好的泛化能力。

• 为什么要迭代求解？(求导困难，求根困难)，(初始值，逼近)

- 梯度下降法

$${\mathbf{x}}_{k+1}={\mathbf{x}}_k-\gamma \nabla f({\mathbf{x}}_k)$$

推导：

1. 利用多元函数的泰勒展开公式：$f(\mathbf{x})-f({\mathbf{x}}_0)\approx [\nabla f({\mathbf{x}}_0){]}^T(\mathbf{x}-{\mathbf{x}}_0)$
2. $X^{T}Y=|X|\cdot |Y|\cdot \cos \theta$，$\cos \theta =-1$ 下降幅度最大
3. 为了使得下降幅度最大，向量 $\mathbf{x}-{\mathbf{x}}_0$ (不一定是单位向量) 的方向和梯度方向相反：$\mathbf{v}=-\frac{\nabla f({\mathbf{x}}_0)}{\Vert \nabla f({\mathbf{x}}_0)\Vert }$
4. $\mathbf{x}={\mathbf{x}}_0-\eta \frac{\nabla f({\mathbf{x}}_0)}{\Vert \nabla f({\mathbf{x}}_0)\Vert }$，分母是标量可并入 $\eta$，即 $\mathbf{x}={\mathbf{x}}_0-\eta \nabla f({\mathbf{x}}_0)$

$\eta$ 是步长，不能太大，否则不满足约等于条件。

- 牛顿法

$${\mathbf{x}}_{k+1}=\mathbf{x}-{\mathbf{H}}_k^{-1}{\mathbf{g}}_k$$

思想：找梯度为0的点。

推导：

1. 多元函数的泰勒展开公式展开二次以上的项
   $$f(\mathbf{x})=f({\mathbf{x}}_0)+[\nabla f({\mathbf{x}}_0){]}^T(\mathbf{x}-{\mathbf{x}}_0)+\frac{1}{2}(\mathbf{x}-{\mathbf{x}}_0{)}^{T}H({\mathbf{x}}_0)(\mathbf{x}-{\mathbf{x}}_0)+\mathbf{o}(\mathbf{x}-{\mathbf{x}}_0)$$
   取近似
   $$f(\mathbf{x})\approx f({\mathbf{x}}_0)+[\nabla f({\mathbf{x}}_0){]}^T(\mathbf{x}-{\mathbf{x}}_0)+\frac{1}{2}(\mathbf{x}-{\mathbf{x}}_0{)}^{T}H({\mathbf{x}}_0)(\mathbf{x}-{\mathbf{x}}_0)$$

2. 由于 $({\mathbf{w}}^T\mathbf{x}{)}^{\prime }=\mathbf{w}$，$({\mathbf{x}}^T\mathbf{A}\mathbf{x}{)}^{\prime }=(\mathbf{A}+{\mathbf{A}}^T)\mathbf{x}$，故有：
   $$\nabla f(\mathbf{x})\approx \nabla f({\mathbf{x}}_0)+H({\mathbf{x}}_0)(\mathbf{x}-{\mathbf{x}}_0)=\mathbf{g}+\mathbf{H}(\mathbf{x}-{\mathbf{x}}_0)$$

3. 令 $\nabla f(\mathbf{x})=0$，如果 Hessian 矩阵可逆，则有
   $$\begin{gathered} \mathbf{g}+\mathbf{H}(\mathbf{x}-{\mathbf{x}}_0)=0 \\ \Rightarrow \mathbf{x}-{\mathbf{x}}_0=-{\mathbf{H}}^{-1}\mathbf{g} \end{gathered}$$

对比：
$$\begin{gathered} {\mathbf{x}}_{k+1}={\mathbf{x}}_k-\eta \cdot {\mathbf{g}}_k \\ {\mathbf{x}}_{k+1}={\mathbf{x}}_k-\eta \cdot {\mathbf{H}}_k^{-1}\cdot {\mathbf{g}}_k \end{gathered}$$

• 牛顿法步长设定不好就有可能不收敛，不是迭代就一定使得函数值下降，一般用 line search 的技术，选择一些值如 $10^{-4},10^{-6}$，看哪个步长使得 $f({\mathbf{x}}_{k+1})$ 更小。

• 牛顿法收敛更快。

- 坐标下降法

• 分治 (分而治之) 法的思想：保持其他不动，只优化其中一个，优化完了之后再回来重新优化。
• 计算量小

- 数值优化算法面临的问题

• 驻点不一定是极值点
• 局部极值问题；
• 鞍点问题，如 $x^3$，在这一点 Hessian 矩阵不定，

- 凸优化问题

前面数值优化面临两个问题，对这类问题进行限定：

1. 优化变量的可行域必须是凸集；
2. 优化函数必须是个凸函数。

同时满足这两个条件的叫凸优化问题，才能说局部极小值就是全局极小值。

- 凸集

• 定义：对于一个点的集合 $C$，有属于它的两个点 $x,y$，它们两点连线中任意一点也属于该集合：$\theta x+(1-\theta )y\in C,0\le \theta \le 1$
• 典型的凸集：
  • 欧式空间 ${\mathbb{R}}^n$：$\mathbf{x},\mathbf{y}\in {\mathbb{R}}^n\Rightarrow \theta \mathbf{x}+(1-\theta )\mathbf{y}\in {\mathbb{R}}^n$；很多可行域就是欧式空间，即凸集；
  • 仿射子空间： { x ∈ R n : A x = b } \left \{ \boldsymbol{x}\in\mathbb{R}^n:\boldsymbol{A}\boldsymbol{x}=\boldsymbol{b} \right \} {x∈Rn:Ax=b}，$\mathbf{x}$ 是 $n$ 维欧式空间的向量，满足线性方程的解；所有等式约束构成的集合是凸集，不会构建非线性等式约束；
  • 多面体： { x ∈ R n : A x ≤ b } \left \{ \boldsymbol{x}\in\mathbb{R}^n:\boldsymbol{A}\boldsymbol{x}\le\boldsymbol{b} \right \} {x∈Rn:Ax≤b}，线性不等式的解；一组线性不等式约束，也是凸集。
• 凸集的交集也是凸集 $\bigcap _{i=1}^k{C}_i$，并集不一定是凸集。

- 凸函数

• 定义：函数上任意两点它们的连线 (即割线) 上的值比对应的函数上的值要大，$f(\theta x+(1-\theta )y)<\theta f(x)+(1-\theta )f(y)$
• 凸函数的证明：
  1. 利用定义
  2. 利用一阶导数：
     • 一元函数：$f(y)\ge f(x)+f^{\prime }(x)(y-x)$
     • 多元函数：$f(\mathbf{y})\ge f(\mathbf{x})+\nabla f(\mathbf{x}{)}^T(\mathbf{y}-\mathbf{x})$
  3. 二阶判别法：
     • 一元函数：$f^{\prime \prime }(x)\ge 0$
     • 多元函数：Hessian 矩阵半正定，$>0$ 是严格凸函数
• 如果每个函数 $f_i(x)$ 都是凸函数，那么它们的非负线性组合 $f(x)=\sum _{i=1}^k{w}_i{f}_i(x),w_i\ge 0$ 也是凸函数。

- 凸优化的性质

目标函数是凸函数，可行域是凸集，则局部最优解一定是全局最优解。

证明：(反证法)

假设有一点 $x$ 是局部最小值，但不是全局最小值，则存在另一个点 $y$ 是全局最小值，这时 $f(y)<f(x)$。

证明 $x$ 的领域有一个点 $z$ 比 $x$ 小即可，取 $z=\theta y+(1-\theta )x,\theta =\frac{\delta }{2\Vert x-y{\Vert }_2}$ 即可。

- 凸优化一般的表述形式

$$\min f(x),x\in C$$

或者
$$\begin{gathered} \min f(x) \\ {c}_i(x)\le 0,i=1,\cdots ,m \\ {h}_j(x)=0,j=1,\cdots ,k \end{gathered}$$

- 拉格朗日乘数法

将一个有n 个变量与k 个约束条件的最优化问题转换为一个有n + k个变量的方程组的极值问题，其变量不受任何约束；

(1) 等式约束条件
$$\begin{gathered} \min f(\mathbf{x}) \\ s.t.h_k(\mathbf{x})=0k=1,2,\cdots ,l \end{gathered}$$
求解步骤：

1. 定义拉格朗日函数：
   $$F(\mathbf{x},\mathbf{\lambda })=f(\mathbf{x})+\sum _{k=1}^l{\lambda }_k{h}_k(\mathbf{x})$$

2. 解变量的偏导方程：
   $$\frac{\partial F}{\partial x_i}=0,\cdots ,\frac{\partial F}{\partial {\lambda }_k}=0,\cdots$$

3. 或者说是分别对 $\mathbf{x}$ 和 $\mathbf{\lambda }$ 求梯度，然后解方程组
   $$\begin{gathered} {\nabla }_{x}f+\sum _{k=1}^l{\lambda }_k{\nabla }_x{h}_k=0 \\ {h}_k(\mathbf{x})=0 \end{gathered}$$

(2) 带不等式约束条件

可参考KKT条件。

- 拉格朗日对偶

$$\begin{gathered} \min f(x) \\ {g}_i(x)\le 0,i=1,\cdots ,m \\ {h}_j(x)=0,j=1,\cdots ,k \end{gathered}$$

构建一个广义 (包括不等式约束) 的拉格朗日函数：
$$L(x,\alpha ,\beta )=f(x)+\sum _{i=1}^m{\alpha }_i{g}_i(x)+\sum _{j=1}^k{\beta }_i{h}_j(x),{\alpha }_i\ge 0$$
问题转化为：
$$p^{\ast }=\underset{x}{\min }\underset{\alpha ,\beta ,{\alpha }_i\ge 0}{\max }L(x,\alpha ,\beta )=\underset{x}{\min }{\theta }_p(x)$$
理解可参考：【数学】拉格朗日对偶，从0到完全理解

无论如何，$p^{\ast }$ 都不会小于 $\underset{\alpha ,\beta ,{\alpha }_i\ge 0}{\max }L(x,\alpha ,\beta )$。

- KKT 条件

$$\begin{gathered} \min f(x) \\ {g}_i(x)\le 0,i=1,\cdots ,q \\ {h}_j(x)=0,j=1,\cdots ,p \end{gathered}$$

$$L(x,\lambda ,\mu )=f(x)+\sum _{j=1}^p{\lambda }_j{h}_j(x)+\sum _{i=1}^q{\mu }_i{g}_i(x)$$

KKT 条件：
$$\begin{gathered} {\nabla }_{x}L(x^{\ast })=\nabla f(x^{\ast })+\sum _{j=1}^p{\lambda }_i^{\ast }\nabla h_j(x^{\ast })+\sum _{i=1}^q{\mu }_i^{\ast }\nabla g_i(x^{\ast })=0 \\ {\mu }_i^{\ast }\ge 0 \\ {\mu }_i^{\ast }{g}_i(x^{\ast })=0 \\ {h}_j(x^{\ast })=0 \\ {g}_i(x^{\ast })\le 0 \end{gathered}$$