1. 凸集
1.1 基本定义
定义 1.1.1 (凸集)
集合 $C \subseteq \mathbb{R}^n$ 称为凸集，如果对于任意 $x, y \in C$ 和任意 $\theta \in [0,1]$，都有：
$$ \theta x + (1-\theta)y \in C $$
定义 1.1.2 (凸组合)
点 $x_1, x_2, \dots, x_k$ 的凸组合是指形如：
$$ \theta_1 x_1 + \theta_2 x_2 + \cdots + \theta_k x_k $$
的点，其中 $\theta_i \geq 0$ 且 $\sum_{i=1}^k \theta_i = 1$。
1.2 重要的凸集例子
例 1.2.1 (超平面)
$$ \{x \mid a^T x = b\} $$
其中 $a \in \mathbb{R}^n$, $a \neq 0$, $b \in \mathbb{R}$。
例 1.2.2 (半空间)
$$ \{x \mid a^T x \leq b\} $$
例 1.2.3 (欧几里得球)
$$ B(x_c, r) = \{x \mid \|x - x_c\|_2 \leq r\} $$
例 1.2.4 (椭球)
$$ \mathcal{E} = \{x \mid (x - x_c)^T P^{-1} (x - x_c) \leq 1\} $$
其中 $P \in \mathbb{S}_{++}^n$（对称正定矩阵）。
1.3 保凸运算
定理 1.3.1 凸集经过以下运算后仍为凸集：
- 交集：如果 $C_1, C_2$ 凸，则 $C_1 \cap C_2$ 凸
- 仿射函数：如果 $C$ 凸，则 $f(C) = \{Ax + b \mid x \in C\}$ 凸
- 透视函数：如果 $C$ 凸，则 $P(C) = \{(x,t) \mid x/t \in C, t > 0\}$ 凸
- 线性分式函数：如果 $C$ 凸，则 $f(C) = \{\frac{Ax+b}{c^Tx+d} \mid c^Tx+d > 0, x \in C\}$ 凸
2. 凸函数
2.1 基本定义
定义 2.1.1 (凸函数)
函数 $f: \mathbb{R}^n \to \mathbb{R}$ 称为凸函数，如果：
- $\text{dom } f$ 是凸集
对于任意 $x, y \in \text{dom } f$ 和 $\theta \in [0,1]$，有：
$$ f(\theta x + (1-\theta)y) \leq \theta f(x) + (1-\theta) f(y) $$
定义 2.1.2 (严格凸函数)
如果上述不等式在 $x \neq y$ 且 $\theta \in (0,1)$ 时严格成立，则称 $f$ 为严格凸函数。
2.2 凸性判定条件
定理 2.2.1 (一阶条件)
如果 $f$ 可微，则 $f$ 凸当且仅当对于任意 $x, y \in \text{dom } f$：
$$ f(y) \geq f(x) + \nabla f(x)^T (y - x) $$
定理 2.2.2 (二阶条件)
如果 $f$ 二阶可微，则 $f$ 凸当且仅当对于任意 $x \in \text{dom } f$：
$$ \nabla^2 f(x) \succeq 0 $$
2.3 常见的凸函数
例 2.3.1 (仿射函数)
$$ f(x) = a^T x + b $$
例 2.3.2 (指数函数)
$$ f(x) = e^{ax} $$
例 2.3.3 (负熵)
$$ f(x) = x \log x \quad (x > 0) $$
例 2.3.4 (范数)
任意范数 $\|x\|$ 都是凸函数。
2.4 共轭函数
定义 2.4.1 (共轭函数)
函数 $f: \mathbb{R}^n \to \mathbb{R}$ 的共轭函数 $f^*: \mathbb{R}^n \to \mathbb{R}$ 定义为：
$$ f^*(y) = \sup_{x \in \text{dom } f} (y^T x - f(x)) $$
性质 2.4.2
- $f^*$ 总是凸函数（即使 $f$ 不凸）
- Fenchel 不等式：$f(x) + f^*(y) \geq x^T y$
- 如果 $f$ 闭凸，则 $f^{**} = f$
3. 凸优化问题
3.1 标准形式
定义 3.1.1 (凸优化问题)
凸优化问题具有形式：
$$ \begin{aligned} \min_{x} \quad & f_0(x) \\ \text{s.t.} \quad & f_i(x) \leq 0, \quad i = 1, \dots, m \\ & a_j^T x = b_j, \quad j = 1, \dots, p \end{aligned} $$
其中 $f_0, f_1, \dots, f_m$ 是凸函数，等式约束是仿射的。
3.2 最优性条件
定理 3.2.1 (全局最优性)
凸优化问题的任何局部最优解都是全局最优解。
定理 3.2.2 (无约束问题的最优性)
对于无约束凸优化问题，$x^*$ 是最优解当且仅当：
$$ \nabla f(x^*) = 0 $$
定理 3.2.3 (有约束问题的最优性)
对于凸优化问题，$x^*$ 是最优解当且仅当对于所有可行点 $y$：
$$ \nabla f(x^*)^T (y - x^*) \geq 0 $$
4. 对偶理论
4.1 Lagrange 对偶
定义 4.1.1 (Lagrange 函数)
对于优化问题：
$$ \begin{aligned} \min_{x} \quad & f_0(x) \\ \text{s.t.} \quad & f_i(x) \leq 0, \quad i = 1, \dots, m \\ & h_i(x) = 0, \quad i = 1, \dots, p \end{aligned} $$
其 Lagrange 函数 为：
$$ L(x, \lambda, \nu) = f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{i=1}^p \nu_i h_i(x) $$
其中 $\lambda_i \geq 0$ 称为 Lagrange 乘子。
定义 4.1.2 (对偶函数)
对偶函数 $g: \mathbb{R}^m \times \mathbb{R}^p \to \mathbb{R}$ 定义为：
$$ g(\lambda, \nu) = \inf_{x} L(x, \lambda, \nu) $$
性质 4.1.3
- 对偶函数 $g$ 是凹函数
- 对于任意 $\lambda \succeq 0$，有 $g(\lambda, \nu) \leq p^*$（弱对偶性）
4.2 强对偶与 KKT 条件
定义 4.2.1 (强对偶性)
如果对偶间隙 $p^* - d^* = 0$，则称问题满足强对偶性。
定理 4.2.2 (Slater 条件)
如果问题是凸的，且存在严格可行点（即 $f_i(x) < 0$ 对于所有不等式约束），则强对偶性成立。
定理 4.2.3 (KKT 条件)
对于凸优化问题，如果强对偶性成立，则 $x^*$ 和 $(\lambda^*, \nu^*)$ 分别是原问题和对偶问题的最优解当且仅当满足以下 KKT 条件：
原始可行性：
- $f_i(x^*) \leq 0$, 对于 $i = 1, \dots, m$
- $h_i(x^*) = 0$, 对于 $i = 1, \dots, p$
对偶可行性：
- $\lambda_i^* \geq 0$, 对于 $i = 1, \dots, m$
互补松弛条件：
- $\lambda_i^* f_i(x^*) = 0$, 对于 $i = 1, \dots, m$
梯度条件：
$$ \nabla f_0(x^*) + \sum_{i=1}^m \lambda_i^* \nabla f_i(x^*) + \sum_{i=1}^p \nu_i^* \nabla h_i(x^*) = 0 $$
其中 $L(x, \lambda, \nu)$ 是 Lagrange 函数。
5. 算法基础
5.1 梯度下降法
算法 5.1.1 (梯度下降)
$$ x_{k+1} = x_k - \alpha_k \nabla f(x_k) $$
定理 5.1.2 (收敛性)
如果 $f$ 是 $L$-光滑凸函数，采用固定步长 $\alpha = 1/L$，则：
$$ f(x_k) - f(x^*) \leq \frac{2L\|x_0 - x^*\|^2}{k} $$
5.2 次梯度法
定义 5.2.1 (次梯度)
向量 $g \in \mathbb{R}^n$ 称为 $f$ 在点 $x$ 的次梯度，如果对于所有 $y$：
$$ f(y) \geq f(x) + g^T (y - x) $$
算法 5.2.2 (次梯度法)
$$ x_{k+1} = x_k - \alpha_k g_k, \quad g_k \in \partial f(x_k) $$
5.3 近端梯度法
算法 5.3.1 (近端梯度法)
对于问题 $\min f(x) + g(x)$，其中 $f$ 光滑、$g$ 非光滑但近端算子易计算：
$$ x_{k+1} = \text{prox}_{\alpha g}(x_k - \alpha \nabla f(x_k)) $$
其中近端算子定义为：
$$ \text{prox}_g(v) = \arg\min_x \left(g(x) + \frac{1}{2}\|x - v\|^2\right) $$
总结
凸分析与优化提供了处理凸问题的系统理论框架，具有以下重要特性：
- 理论完备：局部最优即全局最优
- 对偶理论：强对偶性在 mild 条件下成立
- 算法有效：存在高效的数值算法
- 应用广泛：在机器学习、信号处理、控制等领域有广泛应用