====== 第二章 无约束优化理论基础 ====== ===== 本章导读 ===== 本章深入探讨无约束优化问题的理论基础，包括多元函数的梯度、Hesse矩阵及其计算，方向导数的概念，以及无约束优化问题的一阶和二阶最优性条件。这些理论是设计和分析各类无约束优化算法的基石。 ===== 2.1 多元函数的微分 ===== ==== 2.1.1 梯度与方向导数 ==== 设函数 $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}$，则： - 沿 $-\nabla f(\mathbf{x})$ 方向，函数值下降最快 - 下降速率为 $-\|\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.1.2 Hesse矩阵 ==== **定义 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}$： - 一阶 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.2 矩阵的正定性 ===== ==== 2.2.1 正定矩阵的定义 ==== **定义 2.4** 设 $A$ 是 $n \times n$ 对称矩阵。 - $A$ **正定**（Positive Definite）：$\mathbf{x}^T A \mathbf{x} > 0$，$\forall \mathbf{x} \neq \mathbf{0}$ - $A$ **半正定**（Positive Semi-definite）：$\mathbf{x}^T A \mathbf{x} \geq 0$，$\forall \mathbf{x}$ - $A$ **负定**（Negative Definite）：$\mathbf{x}^T A \mathbf{x} < 0$，$\forall \mathbf{x} \neq \mathbf{0}$ - $A$ **不定**（Indefinite）：存在 $\mathbf{x}, \mathbf{y}$ 使 $\mathbf{x}^T A \mathbf{x} > 0$ 且 $\mathbf{y}^T A \mathbf{y} < 0$ ==== 2.2.2 正定性的判定 ==== **定理 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$： - 正定 $\Leftrightarrow$ 所有特征值 $> 0$ - 半正定 $\Leftrightarrow$ 所有特征值 $\geq 0$ - 负定 $\Leftrightarrow$ 所有特征值 $< 0$ **定理 2.7**（Cholesky分解） 对称矩阵 $A$ 正定的充分必要条件是存在唯一的下三角矩阵 $L$（对角元为正）使得 $A = LL^T$。 **例 2.2** 判断矩阵 $A = \begin{bmatrix} 4 & 2 \\ 2 & 3 \end{bmatrix}$ 的正定性。 **解**：顺序主子式： - $\Delta_1 = 4 > 0$ - $\Delta_2 = 4 \times 3 - 2 \times 2 = 8 > 0$ 因此 $A$ 正定。验证：特征值为 $\lambda = \frac{7 \pm \sqrt{17}}{2} > 0$。 ===== 2.3 无约束优化的最优性条件 ===== ==== 2.3.1 下降方向 ==== **定义 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.3.2 一阶最优性条件 ==== **定理 2.9**（一阶必要条件） 设 $f$ 在 $\mathbf{x}^*$ 处可微。若 $\mathbf{x}^*$ 是局部极小点，则： $$\nabla f(\mathbf{x}^*) = \mathbf{0}$$ 满足 $\nabla f(\mathbf{x}) = \mathbf{0}$ 的点称为**驻点**或**平稳点**（Stationary Point）。 **说明**：驻点包括局部极小点、局部极大点和鞍点。 ==== 2.3.3 二阶最优性条件 ==== **定理 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.3.4 高阶条件 ==== **定理 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.4 算法的收敛性 ===== ==== 2.4.1 收敛性与收敛速度 ==== **定义 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$。 - **线性收敛**（Q-linear）：$\limsup_{k \rightarrow \infty} \frac{\|\mathbf{x}_{k+1} - \mathbf{x}^*\|}{\|\mathbf{x}_k - \mathbf{x}^*\|} = r < 1$ - **超线性收敛**（Q-superlinear）：$\lim_{k \rightarrow \infty} \frac{\|\mathbf{x}_{k+1} - \mathbf{x}^*\|}{\|\mathbf{x}_k - \mathbf{x}^*\|} = 0$ - **$p$ 阶收敛**：$\limsup_{k \rightarrow \infty} \frac{\|\mathbf{x}_{k+1} - \mathbf{x}^*\|}{\|\mathbf{x}_k - \mathbf{x}^*\|^p} = r < \infty$ - $p = 2$ 时称为**二次收敛** 收敛速度关系：二次收敛 $\Rightarrow$ 超线性收敛 $\Rightarrow$ 线性收敛。 ==== 2.4.2 停机准则 ==== 实际计算中，常用以下停机准则： 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$ ===== 2.5 算法的基本结构 ===== 一般的无约束优化算法采用**迭代格式**： $$ \mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{d}_k $$ 其中： - $\mathbf{x}_k$：第 $k$ 次迭代的当前点 - $\mathbf{d}_k$：**搜索方向**（Search Direction） - $\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$ 的选取方式，可将算法分为： - **梯度方法**：$\mathbf{d}_k$ 基于 $-\nabla f(\mathbf{x}_k)$ - **Newton方法**：$\mathbf{d}_k$ 基于 Hesse矩阵 - **拟Newton方法**：用近似矩阵代替 Hesse矩阵 - **共轭梯度法**：利用共轭方向 ===== 2.6 例题详解 ===== **例 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. 判定正定性： - $\Delta_1 = 2 > 0$ - $\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}^*$ 是严格局部（也是全局）极小点。 ===== 2.7 小结 ===== 本章核心内容： - **梯度**：函数增长最快的方向，$-\nabla f$ 是最速下降方向 - **Hesse矩阵**：刻画函数的局部曲率，用于判定极值性质 - **最优性条件**： - 一阶必要条件：$\nabla f(\mathbf{x}^*) = \mathbf{0}$ - 二阶必要条件：$\nabla^2 f(\mathbf{x}^*)$ 半正定 - 二阶充分条件：$\nabla f(\mathbf{x}^*) = \mathbf{0}$ 且 $\nabla^2 f(\mathbf{x}^*)$ 正定 - **收敛性**：线性、超线性、二次收敛的定义 - **迭代算法**：$\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{d}_k$ 的基本框架 ===== 2.8 习题 ===== **理论题** 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矩阵： - $f(x, y) = x^3 + y^3 - 3xy$ - $f(x, y, z) = x^2 + 2y^2 + 3z^2 + 2xy + 2xz$ - $f(\mathbf{x}) = \ln(1 + e^{\mathbf{a}^T \mathbf{x}})$ 7. 求下列函数的极值点并判断其性质： - $f(x, y) = x^2 + 4xy + 5y^2 - 2x - 4y$ - $f(x, y) = x^3 - 3x + y^3 - 3y$ 8. 判断下列矩阵的正定性： - $A = \begin{bmatrix} 3 & 1 \\ 1 & 2 \end{bmatrix}$ - $B = \begin{bmatrix} 2 & 4 \\ 4 & 3 \end{bmatrix}$ - $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$ 的唯一全局极小点。 --- *本章完*