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

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

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

定义 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} $$

其中：

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

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

按约束条件分类：

1. 无约束优化：不含任何约束条件，即 $m = l = 0$
2. 等式约束优化：只含等式约束，即 $m = 0, l > 0$
3. 不等式约束优化：只含不等式约束，即 $m > 0, l = 0$
4. 混合约束优化：同时含等式和不等式约束

按目标函数和约束函数的性质分类：

1. 线性规划（LP）：$f$、$g_i$、$h_j$ 都是线性函数
2. 非线性规划（NLP）：$f$、$g_i$、$h_j$ 中至少有一个是非线性函数
3. 二次规划（QP）：$f$ 是二次函数，约束是线性的
4. 凸优化：目标函数是凸函数，可行域是凸集

按变量类型分类：

1. 连续优化：变量在连续的区间内取值
2. 离散优化/组合优化：变量只能取离散值
3. 整数规划：变量只能取整数值

按目标函数个数分类：

1. 单目标优化：只有一个目标函数
2. 多目标优化：有多个目标函数需要同时优化

案例 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（可行域）

满足所有约束条件的点的集合称为可行域（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.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.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$。

1. 若 $f(x_0) > 0$，则 $x_0$ 是严格局部极小点 - 若 $f(x_0) < 0$，则 $x_0$ 是严格局部极大点
2. 若 $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$。
3. 若 $n$ 为偶数且 $f^{(n)}(x_0) > 0$，则 $x_0$ 是严格局部极小点
4. 若 $n$ 为偶数且 $f^{(n)}(x_0) < 0$，则 $x_0$ 是严格局部极大点
5. 若 $n$ 为奇数，则 $x_0$ 不是极值点

对于多元函数 $f: \mathbb{R}^n \rightarrow \mathbb{R}$，记：

1. 梯度（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$
2. 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.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. 任意多个凸集的交集仍是凸集
2. 凸集的内核是凸集
3. 凸集的闭包是凸集

常见的凸集：

例 1.1（超平面与半空间）

1. 超平面：$H = \{\mathbf{x} \mid \mathbf{a}^T \mathbf{x} = b\}$ 是凸集
2. 半空间：$H^+ = \{\mathbf{x} \mid \mathbf{a}^T \mathbf{x} \geq b\}$ 和 $H^- = \{\mathbf{x} \mid \mathbf{a}^T \mathbf{x} \leq b\}$ 都是凸集

例 1.2（球与椭球）

1. 欧几里得球：$B(\mathbf{x}_c, r) = \{\mathbf{x} \mid \|\mathbf{x} - \mathbf{x}_c\|_2 \leq r\}$ 是凸集
2. 椭球：$\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.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$ 上二阶连续可微。则：

1. $f$ 是凸函数当且仅当 $\nabla^2 f(\mathbf{x})$ 在 $C$ 上处处半正定
2. 若 $\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（指数函数与对数函数）

1. $e^{ax}$ 在 $\mathbb{R}$ 上是凸函数
2. $\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

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

定义 1.12（凸优化问题）

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

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

对于凸优化问题：

1. 可行域是凸集
2. 任何局部最优解都是全局最优解
3. 若目标函数严格凸，则最优解唯一（如果存在）

证明：设 $\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. 最优化问题的一般形式：最小化目标函数，满足约束条件
2. 可行域与最优解：区分全局最优与局部最优
3. 极值条件：一阶必要条件（梯度为零）、二阶充分条件（Hesse矩阵正定）
4. 凸集与凸函数：凸性保证局部最优即全局最优

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

理论题

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. 判断下列集合是否为凸集：

1. $S_1 = \{(x, y) \mid x^2 + y^2 \leq 1\}$
2. $S_2 = \{(x, y) \mid x^2 + y^2 = 1\}$
3. $S_3 = \{(x, y) \mid x \geq 0, y \geq 0, x + y \leq 1\}$

7. 判断下列函数是否为凸函数：

1. $f(x) = x^4$
2. $f(x) = e^x$
3. $f(x) = \ln(1 + e^x)$
4. $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$ 是正定矩阵，则该问题是凸优化问题。

—

*本章完*