====== 第一章 最优化问题与基本概念 ======

===== 本章导读 =====

本章从最优化问题的实际背景出发，介绍最优化问题的数学模型、分类方法以及基本概念。重点阐述极值的定义与判定条件，详细讨论凸集与凸函数的性质。这些基础知识是后续学习各类优化算法的理论基石。

===== 1.1 最优化问题概述 =====

==== 1.1.1 什么是最优化问题 ====

最优化问题是指在给定的约束条件下，寻找使某个目标函数达到最优值（最大或最小）的决策变量取值的问题。

**定义 1.1**（最优化问题的一般形式）

设 $f: D \subseteq \mathbb{R}^n \rightarrow \mathbb{R}$，$g_i: D \rightarrow \mathbb{R}$（$i = 1, 2, \ldots, m$），$h_j: D \rightarrow \mathbb{R}$（$j = 1, 2, \ldots, l$）。最优化问题的一般形式为：

$$
\begin{aligned}
\min_{\mathbf{x}} \quad & f(\mathbf{x}) \\
\text{s.t.} \quad & g_i(\mathbf{x}) \leq 0, \quad i = 1, 2, \ldots, m \\
& h_j(\mathbf{x}) = 0, \quad j = 1, 2, \ldots, l
\end{aligned}
$$

其中：
  - $\mathbf{x} = (x_1, x_2, \ldots, x_n)^T \in \mathbb{R}^n$ 称为**决策变量**或**设计变量**
  - $f(\mathbf{x})$ 称为**目标函数**（Objective Function）
  - $g_i(\mathbf{x}) \leq 0$ 称为**不等式约束**（Inequality Constraints）
  - $h_j(\mathbf{x}) = 0$ 称为**等式约束**（Equality Constraints）
  - s.t. 是 "subject to" 的缩写，意为"受约束于"

==== 1.1.2 最优化问题的分类 ====

最优化问题可根据不同特征进行分类：

**按约束条件分类**：
  - **无约束优化**：不含任何约束条件，即 $m = l = 0$
  - **等式约束优化**：只含等式约束，即 $m = 0, l > 0$
  - **不等式约束优化**：只含不等式约束，即 $m > 0, l = 0$
  - **混合约束优化**：同时含等式和不等式约束

**按目标函数和约束函数的性质分类**：
  - **线性规划**（LP）：$f$、$g_i$、$h_j$ 都是线性函数
  - **非线性规划**（NLP）：$f$、$g_i$、$h_j$ 中至少有一个是非线性函数
  - **二次规划**（QP）：$f$ 是二次函数，约束是线性的
  - **凸优化**：目标函数是凸函数，可行域是凸集

**按变量类型分类**：
  - **连续优化**：变量在连续的区间内取值
  - **离散优化/组合优化**：变量只能取离散值
  - **整数规划**：变量只能取整数值

**按目标函数个数分类**：
  - **单目标优化**：只有一个目标函数
  - **多目标优化**：有多个目标函数需要同时优化

==== 1.1.3 实际应用案例 ====

**案例 1：生产计划问题**

某工厂生产 $n$ 种产品，第 $j$ 种产品的单位利润为 $c_j$，生产第 $j$ 种产品需要消耗第 $i$ 种资源的量为 $a_{ij}$，第 $i$ 种资源的可用量为 $b_i$。设 $x_j$ 为第 $j$ 种产品的产量，则利润最大化问题为：

$$
\begin{aligned}
\max \quad & \sum_{j=1}^n c_j x_j \\
\text{s.t.} \quad & \sum_{j=1}^n a_{ij} x_j \leq b_i, \quad i = 1, 2, \ldots, m \\
& x_j \geq 0, \quad j = 1, 2, \ldots, n
\end{aligned}
$$

**案例 2：投资组合优化**

设有 $n$ 种资产，其预期收益率分别为 $\mu_1, \mu_2, \ldots, \mu_n$，协方差矩阵为 $\Sigma$。设 $x_i$ 为投资于第 $i$ 种资产的比例，在预期收益率不低于 $R$ 的条件下，最小化投资风险：

$$
\begin{aligned}
\min_{\mathbf{x}} \quad & \mathbf{x}^T \Sigma \mathbf{x} \\
\text{s.t.} \quad & \sum_{i=1}^n \mu_i x_i \geq R \\
& \sum_{i=1}^n x_i = 1 \\
& x_i \geq 0, \quad i = 1, 2, \ldots, n
\end{aligned}
$$

**案例 3：函数拟合问题**

给定数据点 $(t_i, y_i)$，$i = 1, 2, \ldots, m$，寻找参数 $\mathbf{x}$ 使得模型 $f(t; \mathbf{x})$ 最好地拟合数据。最小二乘拟合问题为：

$$\min_{\mathbf{x}} \sum_{i=1}^m (f(t_i; \mathbf{x}) - y_i)^2$$

===== 1.2 可行域与最优解 =====

==== 1.2.1 可行域 ====

**定义 1.2**（可行域）

满足所有约束条件的点的集合称为**可行域**（Feasible Region），记作 $\mathcal{F}$：

$$\mathcal{F} = \{\mathbf{x} \in \mathbb{R}^n \mid g_i(\mathbf{x}) \leq 0, i = 1, \ldots, m; h_j(\mathbf{x}) = 0, j = 1, \ldots, l\}$$

若 $\mathcal{F} = \emptyset$，称该优化问题是**不可行**的；若 $\mathcal{F} = \mathbb{R}^n$，则为无约束优化。

**定义 1.3**（可行点）

若 $\mathbf{x} \in \mathcal{F}$，则称 $\mathbf{x}$ 为**可行点**或**可行解**（Feasible Solution）。

==== 1.2.2 最优解的定义 ====

**定义 1.4**（全局最优解）

设 $\mathbf{x}^* \in \mathcal{F}$。若对任意 $\mathbf{x} \in \mathcal{F}$，都有 $f(\mathbf{x}^*) \leq f(\mathbf{x})$，则称 $\mathbf{x}^*$ 为**全局最优解**（Global Optimal Solution），$f(\mathbf{x}^*)$ 为**全局最优值**。

**定义 1.5**（严格全局最优解）

设 $\mathbf{x}^* \in \mathcal{F}$。若对任意 $\mathbf{x} \in \mathcal{F}$ 且 $\mathbf{x} \neq \mathbf{x}^*$，都有 $f(\mathbf{x}^*) < f(\mathbf{x})$，则称 $\mathbf{x}^*$ 为**严格全局最优解**。

**定义 1.6**（局部最优解）

设 $\mathbf{x}^* \in \mathcal{F}$。若存在 $\delta > 0$，使得对任意 $\mathbf{x} \in \mathcal{F} \cap B(\mathbf{x}^*, \delta)$，都有 $f(\mathbf{x}^*) \leq f(\mathbf{x})$，则称 $\mathbf{x}^*$ 为**局部最优解**（Local Optimal Solution）。其中 $B(\mathbf{x}^*, \delta) = \{\mathbf{x} \mid \|\mathbf{x} - \mathbf{x}^*\| < \delta\}$ 是以 $\mathbf{x}^*$ 为中心、$\delta$ 为半径的邻域。

**定义 1.7**（严格局部最优解）

设 $\mathbf{x}^* \in \mathcal{F}$。若存在 $\delta > 0$，使得对任意 $\mathbf{x} \in \mathcal{F} \cap B(\mathbf{x}^*, \delta)$ 且 $\mathbf{x} \neq \mathbf{x}^*$，都有 $f(\mathbf{x}^*) < f(\mathbf{x})$，则称 $\mathbf{x}^*$ 为**严格局部最优解**。

===== 1.3 极值条件 =====

==== 1.3.1 一元函数的极值条件 ====

**定理 1.1**（Fermat定理）

设函数 $f(x)$ 在点 $x_0$ 处可导，且 $x_0$ 是 $f$ 的极值点，则 $f'(x_0) = 0$。

满足 $f'(x_0) = 0$ 的点称为**驻点**或**平稳点**（Stationary Point）。注意：驻点不一定是极值点（如 $f(x) = x^3$ 在 $x = 0$ 处）。

**定理 1.2**（一阶必要条件）

设 $f(x)$ 在 $x_0$ 处可导。若 $x_0$ 是局部极小点，则 $f'(x_0) = 0$。

**定理 1.3**（二阶充分条件）

设 $f(x)$ 在 $x_0$ 处二阶可导，且 $f'(x_0) = 0$。
  - 若 $f''(x_0) > 0$，则 $x_0$ 是严格局部极小点
  - 若 $f''(x_0) < 0$，则 $x_0$ 是严格局部极大点
  - 若 $f''(x_0) = 0$，则无法判定（需更高阶条件）

**定理 1.4**（高阶充分条件）

设 $f(x)$ 在 $x_0$ 处 $n$ 阶可导，且 $f'(x_0) = f''(x_0) = \cdots = f^{(n-1)}(x_0) = 0$，$f^{(n)}(x_0) \neq 0$。
  - 若 $n$ 为偶数且 $f^{(n)}(x_0) > 0$，则 $x_0$ 是严格局部极小点
  - 若 $n$ 为偶数且 $f^{(n)}(x_0) < 0$，则 $x_0$ 是严格局部极大点
  - 若 $n$ 为奇数，则 $x_0$ 不是极值点

==== 1.3.2 多元函数的极值条件 ====

对于多元函数 $f: \mathbb{R}^n \rightarrow \mathbb{R}$，记：
  - **梯度**（Gradient）：$\nabla f(\mathbf{x}) = \left(\frac{\partial f}{\partial x_1}, \frac{\partial f}{\partial x_2}, \ldots, \frac{\partial f}{\partial x_n}\right)^T$
  - **Hesse矩阵**：$\nabla^2 f(\mathbf{x}) = \left(\frac{\partial^2 f}{\partial x_i \partial x_j}\right)_{n \times n}$

**定理 1.5**（一阶必要条件）

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

**证明**：假设 $\nabla f(\mathbf{x}^*) \neq \mathbf{0}$，取方向 $\mathbf{d} = -\nabla f(\mathbf{x}^*)$。由 Taylor 展开：
$$f(\mathbf{x}^* + \alpha \mathbf{d}) = f(\mathbf{x}^*) + \alpha \nabla f(\mathbf{x}^*)^T \mathbf{d} + o(\alpha) = f(\mathbf{x}^*) - \alpha \|\nabla f(\mathbf{x}^*)\|^2 + o(\alpha)$$

当 $\alpha > 0$ 充分小时，$f(\mathbf{x}^* + \alpha \mathbf{d}) < f(\mathbf{x}^*)$，与 $\mathbf{x}^*$ 是局部极小点矛盾。$\square$

**定理 1.6**（二阶必要条件）

设 $f(\mathbf{x})$ 在 $\mathbf{x}^*$ 处二阶连续可微。若 $\mathbf{x}^*$ 是局部极小点，则：
1. $\nabla f(\mathbf{x}^*) = \mathbf{0}$
2. $\nabla^2 f(\mathbf{x}^*)$ 是半正定矩阵，即 $\mathbf{d}^T \nabla^2 f(\mathbf{x}^*) \mathbf{d} \geq 0$，$\forall \mathbf{d} \in \mathbb{R}^n$

**定理 1.7**（二阶充分条件）

设 $f(\mathbf{x})$ 在 $\mathbf{x}^*$ 处二阶连续可微。若：
1. $\nabla f(\mathbf{x}^*) = \mathbf{0}$
2. $\nabla^2 f(\mathbf{x}^*)$ 是正定矩阵，即 $\mathbf{d}^T \nabla^2 f(\mathbf{x}^*) \mathbf{d} > 0$，$\forall \mathbf{d} \neq \mathbf{0}$

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

**证明**：由 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)$$

由于 $\nabla f(\mathbf{x}^*) = \mathbf{0}$ 且 $\nabla^2 f(\mathbf{x}^*)$ 正定，存在 $\lambda_{\min} > 0$ 使得 $\mathbf{d}^T \nabla^2 f(\mathbf{x}^*) \mathbf{d} \geq \lambda_{\min} \|\mathbf{d}\|^2$。因此：
$$f(\mathbf{x}^* + \mathbf{d}) - f(\mathbf{x}^*) \geq \frac{\lambda_{\min}}{2} \|\mathbf{d}\|^2 + o(\|\mathbf{d}\|^2) > 0$$

当 $\|\mathbf{d}\|$ 充分小时，故 $\mathbf{x}^*$ 是严格局部极小点。$\square$

===== 1.4 凸集与凸函数 =====

凸性是优化理论中最重要的概念之一。凸优化问题具有良好的性质：局部最优即全局最优。

==== 1.4.1 凸集 ====

**定义 1.8**（凸集）

设集合 $C \subseteq \mathbb{R}^n$。若对任意 $\mathbf{x}, \mathbf{y} \in C$ 和任意 $\lambda \in [0, 1]$，都有：
$$\lambda \mathbf{x} + (1-\lambda) \mathbf{y} \in C$$

则称 $C$ 为**凸集**（Convex Set）。

几何意义：连接集合中任意两点的线段仍完全包含在该集合中。

**凸集的性质**：

**定理 1.8**
  - 任意多个凸集的交集仍是凸集
  - 凸集的内核是凸集
  - 凸集的闭包是凸集

**常见的凸集**：

**例 1.1**（超平面与半空间）
  - 超平面：$H = \{\mathbf{x} \mid \mathbf{a}^T \mathbf{x} = b\}$ 是凸集
  - 半空间：$H^+ = \{\mathbf{x} \mid \mathbf{a}^T \mathbf{x} \geq b\}$ 和 $H^- = \{\mathbf{x} \mid \mathbf{a}^T \mathbf{x} \leq b\}$ 都是凸集

**例 1.2**（球与椭球）
  - 欧几里得球：$B(\mathbf{x}_c, r) = \{\mathbf{x} \mid \|\mathbf{x} - \mathbf{x}_c\|_2 \leq r\}$ 是凸集
  - 椭球：$\mathcal{E} = \{\mathbf{x} \mid (\mathbf{x}-\mathbf{x}_c)^T P^{-1} (\mathbf{x}-\mathbf{x}_c) \leq 1\}$（$P$ 正定）是凸集

**例 1.3**（多面体）
多面体 $P = \{\mathbf{x} \mid A\mathbf{x} \leq \mathbf{b}\}$ 是凸集，因为它是有限个半空间的交集。

**定义 1.9**（凸组合与凸包）

给定点 $\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_k \in \mathbb{R}^n$，形如 $\sum_{i=1}^k \lambda_i \mathbf{x}_i$（其中 $\lambda_i \geq 0$，$\sum_{i=1}^k \lambda_i = 1$）的点称为这些点的**凸组合**。

集合 $S \subseteq \mathbb{R}^n$ 的**凸包**（Convex Hull）是 $S$ 中所有点的凸组合构成的集合，记作 $\text{conv}(S)$。

**定理 1.9**
$\text{conv}(S)$ 是包含 $S$ 的最小凸集。

==== 1.4.2 凸函数 ====

**定义 1.10**（凸函数）

设函数 $f: C \rightarrow \mathbb{R}$，其中 $C \subseteq \mathbb{R}^n$ 是凸集。若对任意 $\mathbf{x}, \mathbf{y} \in C$ 和任意 $\lambda \in [0, 1]$，都有：
$$f(\lambda \mathbf{x} + (1-\lambda) \mathbf{y}) \leq \lambda f(\mathbf{x}) + (1-\lambda) f(\mathbf{y})$$

则称 $f$ 为**凸函数**（Convex Function）。

若上述不等式严格成立（$\mathbf{x} \neq \mathbf{y}$，$\lambda \in (0, 1)$），则称 $f$ 为**严格凸函数**。

**定义 1.11**（凹函数）

若 $-f$ 是凸函数，则称 $f$ 为**凹函数**（Concave Function）。

**凸函数的几何意义**：函数图像上任意两点间的弦位于函数图像的上方。

**定理 1.10**（一阶判定条件）

设 $f$ 在凸集 $C$ 上可微。则 $f$ 是凸函数当且仅当：
$$f(\mathbf{y}) \geq f(\mathbf{x}) + \nabla f(\mathbf{x})^T (\mathbf{y} - \mathbf{x}), \quad \forall \mathbf{x}, \mathbf{y} \in C$$

几何意义：凸函数图像总是位于其切平面的上方。

**定理 1.11**（二阶判定条件）

设 $f$ 在开凸集 $C$ 上二阶连续可微。则：
  - $f$ 是凸函数当且仅当 $\nabla^2 f(\mathbf{x})$ 在 $C$ 上处处半正定
  - 若 $\nabla^2 f(\mathbf{x})$ 在 $C$ 上处处正定，则 $f$ 是严格凸函数

**常见的凸函数**：

**例 1.4**（范数）
任何范数 $f(\mathbf{x}) = \|\mathbf{x}\|$ 都是凸函数。

**例 1.5**（二次函数）
$f(\mathbf{x}) = \frac{1}{2} \mathbf{x}^T A \mathbf{x} + \mathbf{b}^T \mathbf{x} + c$，其中 $A$ 对称。当 $A$ 半正定时，$f$ 是凸函数。

**例 1.6**（指数函数与对数函数）
  - $e^{ax}$ 在 $\mathbb{R}$ 上是凸函数
  - $\log x$ 在 $(0, +\infty)$ 上是凹函数

**例 1.7**（最大值函数）
$f(\mathbf{x}) = \max\{f_1(\mathbf{x}), f_2(\mathbf{x}), \ldots, f_m(\mathbf{x})\}$，若每个 $f_i$ 都是凸函数，则 $f$ 也是凸函数。

**凸函数的性质**：

**定理 1.12**
  - 非负加权和：若 $f_1, f_2, \ldots, f_m$ 是凸函数，$\lambda_i \geq 0$，则 $\sum_{i=1}^m \lambda_i f_i$ 是凸函数
  - 复合函数：若 $g$ 是凸函数且非减，$h$ 是凸函数，则 $g(h(\mathbf{x}))$ 是凸函数
  - 下水平集：凸函数的下水平集 $C_\alpha = \{\mathbf{x} \mid f(\mathbf{x}) \leq \alpha\}$ 是凸集

==== 1.4.3 凸优化问题 ====

**定义 1.12**（凸优化问题）

一个优化问题是**凸优化问题**，如果：
1. 目标函数 $f$ 是凸函数
2. 不等式约束函数 $g_i$ 都是凸函数
3. 等式约束函数 $h_j$ 都是仿射函数（即 $h_j(\mathbf{x}) = \mathbf{a}_j^T \mathbf{x} - b_j$）

**定理 1.13**（凸优化的优良性质）

对于凸优化问题：
  - 可行域是凸集
  - 任何局部最优解都是全局最优解
  - 若目标函数严格凸，则最优解唯一（如果存在）

**证明**：设 $\mathbf{x}^*$ 是局部最优解，假设存在 $\mathbf{y} \in \mathcal{F}$ 使得 $f(\mathbf{y}) < f(\mathbf{x}^*)$。考虑点 $\mathbf{z}_\lambda = \lambda \mathbf{x}^* + (1-\lambda) \mathbf{y}$，$\lambda \in [0, 1]$。

由可行域的凸性，$\mathbf{z}_\lambda \in \mathcal{F}$。由 $f$ 的凸性：
$$f(\mathbf{z}_\lambda) \leq \lambda f(\mathbf{x}^*) + (1-\lambda) f(\mathbf{y}) < \lambda f(\mathbf{x}^*) + (1-\lambda) f(\mathbf{x}^*) = f(\mathbf{x}^*)$$

当 $\lambda \rightarrow 1$ 时，$\mathbf{z}_\lambda \rightarrow \mathbf{x}^*$，这与 $\mathbf{x}^*$ 是局部最优解矛盾。$\square$

===== 1.5 小结 =====

本章介绍了最优化问题的基本概念：

  - **最优化问题的一般形式**：最小化目标函数，满足约束条件
  - **可行域与最优解**：区分全局最优与局部最优
  - **极值条件**：一阶必要条件（梯度为零）、二阶充分条件（Hesse矩阵正定）
  - **凸集与凸函数**：凸性保证局部最优即全局最优

这些基础概念是后续学习各种优化算法的理论前提。

===== 1.6 习题 =====

**理论题**

1. 证明：若 $f: \mathbb{R}^n \rightarrow \mathbb{R}$ 是凸函数，则对任意 $\alpha \in \mathbb{R}$，水平集 $\{\mathbf{x} \mid f(\mathbf{x}) \leq \alpha\}$ 是凸集。

2. 设 $f(\mathbf{x}) = \mathbf{x}^T A \mathbf{x} + \mathbf{b}^T \mathbf{x} + c$，其中 $A$ 是 $n \times n$ 对称矩阵，$\mathbf{b} \in \mathbb{R}^n$，$c \in \mathbb{R}$。证明：$f$ 是凸函数当且仅当 $A$ 半正定。

3. 求函数 $f(x, y) = x^3 + y^3 - 3xy$ 的所有驻点，并判断它们是否为极值点。

4. 设 $f_1, f_2, \ldots, f_m$ 是凸函数，证明 $f(\mathbf{x}) = \max_{i} f_i(\mathbf{x})$ 也是凸函数。

5. 证明：严格凸函数最多有一个全局最小值点。

**计算题**

6. 判断下列集合是否为凸集：
   - $S_1 = \{(x, y) \mid x^2 + y^2 \leq 1\}$
   - $S_2 = \{(x, y) \mid x^2 + y^2 = 1\}$
   - $S_3 = \{(x, y) \mid x \geq 0, y \geq 0, x + y \leq 1\}$

7. 判断下列函数是否为凸函数：
   - $f(x) = x^4$
   - $f(x) = e^x$
   - $f(x) = \ln(1 + e^x)$
   - $f(x, y) = x^2 + 2xy + 3y^2$

8. 求函数 $f(x, y) = 2x^2 + xy + y^2 + x - y + 3$ 的极值点，并判断其性质。

**应用题**

9. 将下列问题建模为最优化问题：
   某公司有 $m$ 个工厂和 $n$ 个仓库。工厂 $i$ 的产量为 $a_i$，仓库 $j$ 的需求量为 $b_j$，从工厂 $i$ 到仓库 $j$ 的单位运输成本为 $c_{ij}$。建立使总运输成本最小的优化模型。

10. 证明：对于二次规划问题
    $$\min \frac{1}{2} \mathbf{x}^T Q \mathbf{x} + \mathbf{c}^T \mathbf{x} \quad \text{s.t.} \quad A\mathbf{x} = \mathbf{b}, \mathbf{x} \geq \mathbf{0}$$
    若 $Q$ 是正定矩阵，则该问题是凸优化问题。

---

*本章完*