第二章 无约束优化理论基础

本章深入探讨无约束优化问题的理论基础，包括多元函数的梯度、Hesse矩阵及其计算，方向导数的概念，以及无约束优化问题的一阶和二阶最优性条件。这些理论是设计和分析各类无约束优化算法的基石。

设函数 $f: \mathbb{R}^n \rightarrow \mathbb{R}$ 在点 $\mathbf{x}$ 处可微。

定义 2.1（梯度）

函数 $f$ 在点 $\mathbf{x}$ 处的梯度定义为： $$\nabla f(\mathbf{x}) = \left(\frac{\partial f(\mathbf{x})}{\partial x_1}, \frac{\partial f(\mathbf{x})}{\partial x_2}, \ldots, \frac{\partial f(\mathbf{x})}{\partial x_n}\right)^T$$

梯度是一个 $n$ 维列向量，指向函数值增长最快的方向。

定义 2.2（方向导数）

设 $\mathbf{d} \in \mathbb{R}^n$ 是单位向量（$\|\mathbf{d}\| = 1$）。函数 $f$ 在点 $\mathbf{x}$ 处沿方向 $\mathbf{d}$ 的方向导数定义为： $$\frac{\partial f(\mathbf{x})}{\partial \mathbf{d}} = \lim_{t \rightarrow 0^+} \frac{f(\mathbf{x} + t\mathbf{d}) - f(\mathbf{x})}{t}$$

定理 2.1

若 $f$ 在 $\mathbf{x}$ 处可微，则方向导数存在且： $$\frac{\partial f(\mathbf{x})}{\partial \mathbf{d}} = \nabla f(\mathbf{x})^T \mathbf{d}$$

定理 2.2（梯度方向的最速性）

设 $\nabla f(\mathbf{x}) \neq \mathbf{0}$，则：

1. 沿 $-\nabla f(\mathbf{x})$ 方向，函数值下降最快
2. 下降速率为 $-\|\nabla f(\mathbf{x})\|$

即： $$-\|\nabla f(\mathbf{x})\| = \min_{\|\mathbf{d}\|=1} \nabla f(\mathbf{x})^T \mathbf{d}$$

证明：由 Cauchy-Schwarz 不等式： $$|\nabla f(\mathbf{x})^T \mathbf{d}| \leq \|\nabla f(\mathbf{x})\| \cdot \|\mathbf{d}\| = \|\nabla f(\mathbf{x})\|$$

等号成立当且仅当 $\mathbf{d}$ 与 $\nabla f(\mathbf{x})$ 平行。因此，当 $\mathbf{d} = -\frac{\nabla f(\mathbf{x})}{\|\nabla f(\mathbf{x})\|}$ 时，方向导数取最小值 $-\|\nabla f(\mathbf{x})\|$。$\square$

定义 2.3（Hesse矩阵）

设函数 $f$ 在点 $\mathbf{x}$ 处二阶可微。$f$ 在 $\mathbf{x}$ 处的Hesse矩阵定义为： $$\nabla^2 f(\mathbf{x}) = \begin{bmatrix} \frac{\partial^2 f}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1 \partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_1 \partial x_n}
\frac{\partial^2 f}{\partial x_2 \partial x_1} & \frac{\partial^2 f}{\partial x_2^2} & \cdots & \frac{\partial^2 f}{\partial x_2 \partial x_n}
\vdots & \vdots & \ddots & \vdots
\frac{\partial^2 f}{\partial x_n \partial x_1} & \frac{\partial^2 f}{\partial x_n \partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_n^2} \end{bmatrix}$$

Hesse矩阵是一个 $n \times n$ 对称矩阵（若二阶偏导数连续）。

例 2.1

设 $f(x, y) = x^2 + 2xy + 3y^2$，则： $$\nabla f(x, y) = \begin{bmatrix} 2x + 2y
2x + 6y \end{bmatrix}, \quad \nabla^2 f(x, y) = \begin{bmatrix} 2 & 2
2 & 6 \end{bmatrix}$$

定理 2.3（Taylor展开）

设 $f$ 在 $\mathbf{x}$ 的某邻域内二阶连续可微。对充分小的 $\mathbf{d}$：

1. 一阶 Taylor 展开：

$$f(\mathbf{x} + \mathbf{d}) = f(\mathbf{x}) + \nabla f(\mathbf{x})^T \mathbf{d} + o(\|\mathbf{d}\|)$$

- 二阶 Taylor 展开：
$$f(\mathbf{x} + \mathbf{d}) = f(\mathbf{x}) + \nabla f(\mathbf{x})^T \mathbf{d} + \frac{1}{2} \mathbf{d}^T \nabla^2 f(\mathbf{x}) \mathbf{d} + o(\|\mathbf{d}\|^2)$$

定理 2.4（带 Lagrange 余项的 Taylor 展开）

存在 $\theta \in (0, 1)$ 使得： $$f(\mathbf{x} + \mathbf{d}) = f(\mathbf{x}) + \nabla f(\mathbf{x})^T \mathbf{d} + \frac{1}{2} \mathbf{d}^T \nabla^2 f(\mathbf{x} + \theta \mathbf{d}) \mathbf{d}$$

定义 2.4

设 $A$ 是 $n \times n$ 对称矩阵。

1. $A$ 正定（Positive Definite）：$\mathbf{x}^T A \mathbf{x} > 0$，$\forall \mathbf{x} \neq \mathbf{0}$
2. $A$ 半正定（Positive Semi-definite）：$\mathbf{x}^T A \mathbf{x} \geq 0$，$\forall \mathbf{x}$
3. $A$ 负定（Negative Definite）：$\mathbf{x}^T A \mathbf{x} < 0$，$\forall \mathbf{x} \neq \mathbf{0}$
4. $A$ 不定（Indefinite）：存在 $\mathbf{x}, \mathbf{y}$ 使 $\mathbf{x}^T A \mathbf{x} > 0$ 且 $\mathbf{y}^T A \mathbf{y} < 0$

定理 2.5（Sylvester准则）

对称矩阵 $A$ 正定的充分必要条件是其所有顺序主子式大于零： $$\Delta_1 = a_{11} > 0, \quad \Delta_2 = \begin{vmatrix} a_{11} & a_{12}
a_{21} & a_{22} \end{vmatrix} > 0, \quad \ldots, \quad \Delta_n = \det(A) > 0$$

定理 2.6（特征值判定）

对称矩阵 $A$：

1. 正定 $\Leftrightarrow$ 所有特征值 $> 0$
2. 半正定 $\Leftrightarrow$ 所有特征值 $\geq 0$
3. 负定 $\Leftrightarrow$ 所有特征值 $< 0$

定理 2.7（Cholesky分解）

对称矩阵 $A$ 正定的充分必要条件是存在唯一的下三角矩阵 $L$（对角元为正）使得 $A = LL^T$。

例 2.2

判断矩阵 $A = \begin{bmatrix} 4 & 2
2 & 3 \end{bmatrix}$ 的正定性。

解：顺序主子式：

1. $\Delta_1 = 4 > 0$
2. $\Delta_2 = 4 \times 3 - 2 \times 2 = 8 > 0$

因此 $A$ 正定。验证：特征值为 $\lambda = \frac{7 \pm \sqrt{17}}{2} > 0$。

定义 2.5（下降方向）

设 $f$ 在 $\mathbf{x}$ 处可微，$\mathbf{d} \neq \mathbf{0}$。若存在 $\bar{\delta} > 0$ 使得： $$f(\mathbf{x} + \delta \mathbf{d}) < f(\mathbf{x}), \quad \forall \delta \in (0, \bar{\delta})$$

则称 $\mathbf{d}$ 是 $f$ 在 $\mathbf{x}$ 处的下降方向。

定理 2.8

若 $\nabla f(\mathbf{x})^T \mathbf{d} < 0$，则 $\mathbf{d}$ 是下降方向。

证明：由 Taylor 展开： $$f(\mathbf{x} + \delta \mathbf{d}) = f(\mathbf{x}) + \delta \nabla f(\mathbf{x})^T \mathbf{d} + o(\delta)$$

当 $\delta$ 充分小时，$f(\mathbf{x} + \delta \mathbf{d}) - f(\mathbf{x}) \approx \delta \nabla f(\mathbf{x})^T \mathbf{d} < 0$。$\square$

推论 2.1

$-\nabla f(\mathbf{x})$ 是下降方向（若 $\nabla f(\mathbf{x}) \neq \mathbf{0}$）。

定理 2.9（一阶必要条件）

设 $f$ 在 $\mathbf{x}^*$ 处可微。若 $\mathbf{x}^*$ 是局部极小点，则： $$\nabla f(\mathbf{x}^*) = \mathbf{0}$$

满足 $\nabla f(\mathbf{x}) = \mathbf{0}$ 的点称为驻点或平稳点（Stationary Point）。

说明：驻点包括局部极小点、局部极大点和鞍点。

定理 2.10（二阶必要条件）

设 $f$ 在 $\mathbf{x}^*$ 处二阶连续可微。若 $\mathbf{x}^*$ 是局部极小点，则： 1. $\nabla f(\mathbf{x}^*) = \mathbf{0}$ 2. $\nabla^2 f(\mathbf{x}^*)$ 半正定

定理 2.11（二阶充分条件）

设 $f$ 在 $\mathbf{x}^*$ 处二阶连续可微。若： 1. $\nabla f(\mathbf{x}^*) = \mathbf{0}$ 2. $\nabla^2 f(\mathbf{x}^*)$ 正定

则 $\mathbf{x}^*$ 是严格局部极小点。

证明：由 Taylor 展开，存在 $\theta \in (0, 1)$： $$f(\mathbf{x}^* + \mathbf{d}) - f(\mathbf{x}^*) = \frac{1}{2} \mathbf{d}^T \nabla^2 f(\mathbf{x}^* + \theta \mathbf{d}) \mathbf{d}$$

由于 $\nabla^2 f(\mathbf{x}^*)$ 正定，存在邻域使 $\nabla^2 f(\mathbf{x})$ 正定，故上式 $> 0$。$\square$

注意：二阶条件是充分的但不是必要的。例如 $f(x) = x^4$ 在 $x = 0$ 处有严格局部极小，但 $f''(0) = 0$。

定理 2.12

设 $f$ 在 $\mathbf{x}^*$ 处足够光滑，且： $$\nabla f(\mathbf{x}^*) = \nabla^2 f(\mathbf{x}^*) = \cdots = \nabla^{2m-1} f(\mathbf{x}^*) = \mathbf{0}$$

若 $2m$ 阶导数张量 $\nabla^{2m} f(\mathbf{x}^*)$ 正定，则 $\mathbf{x}^*$ 是严格局部极小点。

定义 2.6（收敛性）

设算法产生序列 $\{\mathbf{x}_k\}$。若 $\mathbf{x}_k \rightarrow \mathbf{x}^*$，$\mathbf{x}^*$ 是最优解，则称算法收敛。

定义 2.7（收敛速度）

设 $\mathbf{x}_k \rightarrow \mathbf{x}^*$，$\mathbf{x}^* \neq \mathbf{x}_k$。

1. 线性收敛（Q-linear）：$\limsup_{k \rightarrow \infty} \frac{\|\mathbf{x}_{k+1} - \mathbf{x}^*\|}{\|\mathbf{x}_k - \mathbf{x}^*\|} = r < 1$
2. 超线性收敛（Q-superlinear）：$\lim_{k \rightarrow \infty} \frac{\|\mathbf{x}_{k+1} - \mathbf{x}^*\|}{\|\mathbf{x}_k - \mathbf{x}^*\|} = 0$
3. $p$ 阶收敛：$\limsup_{k \rightarrow \infty} \frac{\|\mathbf{x}_{k+1} - \mathbf{x}^*\|}{\|\mathbf{x}_k - \mathbf{x}^*\|^p} = r < \infty$
4. $p = 2$ 时称为二次收敛

收敛速度关系：二次收敛 $\Rightarrow$ 超线性收敛 $\Rightarrow$ 线性收敛。

实际计算中，常用以下停机准则：

1. 梯度准则：$\|\nabla f(\mathbf{x}_k)\| \leq \varepsilon_1$ 2. 函数值准则：$|f(\mathbf{x}_{k+1}) - f(\mathbf{x}_k)| \leq \varepsilon_2$ 3. 步长准则：$\|\mathbf{x}_{k+1} - \mathbf{x}_k\| \leq \varepsilon_3$ 4. 相对准则：$\frac{|f(\mathbf{x}_{k+1}) - f(\mathbf{x}_k)|}{|f(\mathbf{x}_k)|} \leq \varepsilon_4$

一般的无约束优化算法采用迭代格式：

$$ \mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{d}_k $$

其中：

1. $\mathbf{x}_k$：第 $k$ 次迭代的当前点
2. $\mathbf{d}_k$：搜索方向（Search Direction）
3. $\alpha_k$：步长（Step Size）

算法流程：

1. 选择初始点 $\mathbf{x}_0$，设 $k = 0$
2. 若满足停机条件，停止并输出 $\mathbf{x}_k$
3. 确定搜索方向 $\mathbf{d}_k$
4. 确定步长 $\alpha_k > 0$
5. 更新 $\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{d}_k$
6. $k \leftarrow k + 1$，转步骤 2

根据搜索方向 $\mathbf{d}_k$ 的选取方式，可将算法分为：

1. 梯度方法：$\mathbf{d}_k$ 基于 $-\nabla f(\mathbf{x}_k)$
2. Newton方法：$\mathbf{d}_k$ 基于 Hesse矩阵
3. 拟Newton方法：用近似矩阵代替 Hesse矩阵
4. 共轭梯度法：利用共轭方向

例 2.3

求函数 $f(x, y) = x^2 + xy + y^2 - 3x - 3y$ 的极值点。

解：

1. 求梯度并令其为零：

 $$\nabla f = \begin{bmatrix} 2x + y - 3 \\ x + 2y - 3 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}$$

2. 解方程组：

 $$\begin{cases} 2x + y = 3 \\ x + 2y = 3 \end{cases} \Rightarrow x = 1, y = 1$$

3. 求 Hesse矩阵：

 $$\nabla^2 f = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}$$

4. 判定正定性：

1. $\Delta_1 = 2 > 0$
2. $\Delta_2 = 4 - 1 = 3 > 0$

故 $\nabla^2 f$ 正定。

5. 结论：$(1, 1)$ 是严格局部极小点（也是全局极小点）。

例 2.4

设 $f(\mathbf{x}) = \frac{1}{2} \mathbf{x}^T A \mathbf{x} - \mathbf{b}^T \mathbf{x}$，其中 $A$ 对称正定。证明该函数有唯一全局极小点，并求出该点。

解：

1. 由 $A$ 正定，$f$ 是严格凸函数，故局部极小即全局极小。

2. 求梯度：$\nabla f(\mathbf{x}) = A\mathbf{x} - \mathbf{b}$

3. 令梯度为零：$A\mathbf{x} = \mathbf{b}$

4. 由于 $A$ 正定可逆，唯一解为 $\mathbf{x}^* = A^{-1}\mathbf{b}$

5. Hesse矩阵 $\nabla^2 f = A$ 正定，故 $\mathbf{x}^*$ 是严格局部（也是全局）极小点。

本章核心内容：

1. 梯度：函数增长最快的方向，$-\nabla f$ 是最速下降方向
2. Hesse矩阵：刻画函数的局部曲率，用于判定极值性质
3. 最优性条件：
4. 一阶必要条件：$\nabla f(\mathbf{x}^*) = \mathbf{0}$
5. 二阶必要条件：$\nabla^2 f(\mathbf{x}^*)$ 半正定
6. 二阶充分条件：$\nabla f(\mathbf{x}^*) = \mathbf{0}$ 且 $\nabla^2 f(\mathbf{x}^*)$ 正定
7. 收敛性：线性、超线性、二次收敛的定义
8. 迭代算法：$\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{d}_k$ 的基本框架

理论题

1. 设 $f(\mathbf{x}) = \mathbf{x}^T A \mathbf{x}$，其中 $A$ 是 $n \times n$ 矩阵（不一定对称）。证明：$\nabla f(\mathbf{x}) = (A + A^T)\mathbf{x}$，$\nabla^2 f(\mathbf{x}) = A + A^T$。

2. 证明：若 $f$ 是凸函数，则任何局部极小点都是全局极小点。

3. 设 $f(\mathbf{x}) = \frac{1}{2}\|\mathbf{x}\|^2$，$\mathbf{x} \in \mathbb{R}^n$。证明对任意 $\mathbf{x} \neq \mathbf{0}$，方向 $\mathbf{d} = -\mathbf{x}$ 是下降方向，并计算下降速率。

4. 证明：若对称矩阵 $A$ 正定，则 $A^{-1}$ 也正定。

5. 设 $f(x, y) = (x^2 - y)^2 + x^2$。证明 $(0, 0)$ 是驻点但不是极值点（鞍点）。

计算题

6. 求下列函数的梯度和Hesse矩阵：

1. $f(x, y) = x^3 + y^3 - 3xy$
2. $f(x, y, z) = x^2 + 2y^2 + 3z^2 + 2xy + 2xz$
3. $f(\mathbf{x}) = \ln(1 + e^{\mathbf{a}^T \mathbf{x}})$

7. 求下列函数的极值点并判断其性质：

1. $f(x, y) = x^2 + 4xy + 5y^2 - 2x - 4y$
2. $f(x, y) = x^3 - 3x + y^3 - 3y$

8. 判断下列矩阵的正定性：

1. $A = \begin{bmatrix} 3 & 1
   1 & 2 \end{bmatrix}$
2. $B = \begin{bmatrix} 2 & 4
   4 & 3 \end{bmatrix}$
3. $C = \begin{bmatrix} 5 & 2 & -1
   2 & 3 & 1
   -1 & 1 & 2 \end{bmatrix}$

证明题

9. 设 $\{\mathbf{x}_k\}$ 超线性收敛到 $\mathbf{x}^*$，且 $\mathbf{x}_k \neq \mathbf{x}^*$ 对所有 $k$ 成立。证明： $$\lim_{k \rightarrow \infty} \frac{\|\mathbf{x}_{k+1} - \mathbf{x}_k\|}{\|\mathbf{x}_k - \mathbf{x}^*\|} = 1$$

10. 设 $f$ 在 $\mathbf{x}^*$ 的邻域内满足：$\nabla f(\mathbf{x}^*) = \mathbf{0}$，且存在 $m, M > 0$ 使得：

  $$m\|\mathbf{d}\|^2 \leq \mathbf{d}^T \nabla^2 f(\mathbf{x}) \mathbf{d} \leq M\|\mathbf{d}\|^2, \quad \forall \mathbf{x}, \mathbf{d}$$
  证明 $\mathbf{x}^*$ 是 $f$ 的唯一全局极小点。

—

*本章完*