SDSC6015 课程 1-课程介绍与随机优化初步

#sdsc6015

English / 中文

---

课程介绍与随机优化初步

---

主问题 / Main Problem

给定带标签训练数据 $(x_1, y_1), \dots, (x_n, y_n) \in \mathbb{R}^d \times \mathcal{Y}$，
寻找权重 $\theta$ 以最小化：

$$\min_{\theta} f(\theta) = \frac{1}{n} \sum_{i=1}^{n} \ell(\theta, (x_i, y_i)), \quad n \text{ 极大}$$

目标：通过损失函数 $\ell$ 衡量模型预测误差，优化参数 $\theta$。

补充说明 / Supplementary Notes

数学符号解释：

• $\theta \in \mathbb{R}^m$：待优化参数向量（例如线性模型的权重、神经网络的参数）

• $\ell(\theta, (x_i, y_i))$：损失函数，量化模型预测 $\hat{y}_i = g_\theta(x_i)$ 与真实标签 $y_i$ 的差异

• $\frac{1}{n} \sum_{i=1}^n$：经验风险，表示在训练集上的平均损失

实际意义：

该优化问题称为经验风险最小化 (ERM)：

• 核心思想：通过最小化训练集上的平均损失，使模型泛化到新数据
• 挑战：当 $n$ 极大时，直接计算整个数据集的梯度计算成本过高
• 解决方案：随机优化算法（如SGD）每次迭代仅用部分数据近似梯度

---

软间隔支持向量机 / Soft Margin SVM

$$\min_{w,b} \left\{ \frac{1}{n} \sum_{i=1}^{n} \max\left(0, 1 - y_i (w^\top x_i - b)\right) + \lambda \|w\|^2 \right\}$$

• $x_i$：特征向量

• $y_i \in \{-1, 1\}$：类别标签

• $\lambda > 0$：正则化系数

• $w, b$：待学习参数

合页损失 (Hinge Loss)：$\max(0, 1 - y_i (w^\top x_i - b))$ 惩罚分类错误。
正则化 (Regularization)：$\lambda \|w\|^2$ 控制模型复杂度，防止过拟合。

补充说明 / Supplementary Notes

数学原理推导：

1. 合页损失的来源：

   • 理想约束 $y_i(w^\top x_i - b) \geq 1$（所有样本正确分类且间隔至少为1）
   • 引入松弛变量 $\xi_i \geq 0$ 允许违反约束：$y_i(w^\top x_i - b) \geq 1 - \xi_i$
   • 最小化违反程度 $\sum \xi_i$ → $\max(0, 1 - y_i(w^\top x_i - b))$

   几何意义：样本到决策边界的距离 $d = \frac{|w^\top x_i - b|}{\|w\|}$，当 $d < \frac{1}{\|w\|}$ 时被惩罚

2. 正则化项的推导：

   • 间隔大小 $M = \frac{2}{\|w\|}$
   • 最大化间隔等价于最小化 $\|w\|^2$（因 $\arg\max M = \arg\min \|w\|$）

   实际意义：$\lambda$ 平衡分类误差与模型复杂度

   • $\lambda \to 0$：允许更多误分类（大间隔）
   • $\lambda \to \infty$：严格分类（小间隔）

符号扩展解释：

• $w^\top x_i - b = 0$：决策超平面（分离两类样本的边界）

• $\frac{w}{\|w\|}$：法向量方向（决定分类方向）

• $b$：截距项（调整超平面位置）

示例：
二维空间中：

• 决策边界为直线 $w_1x_1 + w_2x_2 - b = 0$

• 正类($y_i=1$)样本在直线一侧，负类($y_i=-1$)在另一侧

• 合页损失仅在样本落入"间隔带"（灰色区域）时激活

---

示例：图像去噪 / Example: Image Denoising

全变分去噪模型 (Total Variation Denoising Model)：

$$\min_{X} \sum_{(i,j) \in P} |X_{ij} - O_{ij}|^2 + \lambda \cdot TV(X)$$

• $X$：待恢复图像矩阵

• $O$：含噪观测图像

• $P$：观测像素索引集

• $TV(X)$：全变分正则项：

  $$TV(X) = \sum_{i,j} |X_{i+1,j} - X_{ij}| + |X_{i,j+1} - X_{ij}|$$

数据保真项 (Data Fidelity)：$\sum |X_{ij} - O_{ij}|^2$ 确保恢复图像接近观测值。
平滑约束 (Smoothness)：$TV(X)$ 通过惩罚相邻像素差异，促进分段平滑。

补充说明 / Supplementary Notes

数学原理推导：

1. 全变分项 $TV(X)$ 的物理意义：

   • $|X_{i+1,j} - X_{ij}|$ 计算垂直方向梯度（像素与下方邻居的强度差）
   • $|X_{i,j+1} - X_{ij}|$ 计算水平方向梯度（像素与右侧邻居的强度差）

   核心思想：自然图像具有"分段平滑"特性（相邻像素相似），而噪声破坏这种连续性

2. 优化目标分解：

   • 数据保真项：最小化 $\|X - O\|_F^2$（Frobenius范数平方）→ 保持与观测图像相似
   • 正则化项：最小化图像梯度 $\|\nabla X\|_1$（梯度向量的L1范数）→ 促进平滑

   $\lambda$ 控制平滑强度：$\lambda \uparrow$ → 更平滑但可能模糊细节

符号扩展解释：

• $X_{ij} \in [0,255]$：图像在位置 $(i,j)$ 的像素强度（灰度值）

• $\nabla X = \begin{bmatrix} X_{i+1,j}-X_{ij} \\ X_{i,j+1}-X_{ij} \end{bmatrix}$：离散梯度算子

• L1范数 $\|\nabla X\|_1$：对噪声更鲁棒（相比L2范数）

实际意义：

• 医学成像：去除CT扫描中的高斯噪声，保留器官边界

• 卫星图像：消除云层干扰，恢复地表纹理

• 与高斯滤波对比：TV去噪保留边缘（如建筑物轮廓），而高斯滤波会使边缘模糊

示例：
假设 2×2 噪声图像 $O = \begin{bmatrix} 50 & 100 \\ 30 & 80 \end{bmatrix}$：

• 计算 $TV(O) = |50-30| + |50-100| + |30-80| + |100-80| = 20+50+50+20=140$

• 去噪后图像 $X$ 的 $TV(X)$ 值显著降低（如降为40），同时 $|X-O|^2$ 保持较小

---

示例：神经网络 / Example: Neural Networks

卷积神经网络 (Convolutional Neural Network)：

$$\min_{w,b} f(w,b) = \frac{1}{n} \sum_{i=1}^{n} \ell(w, b, (x_i, y_i))$$

其中

$$\ell(w, b, (x_i, y_i)) = \left\| w_3^\top \cdot Q(w_2^\top \cdot Q(w_1^\top x_i - b_1) - b_2) - y_i \right\|^2$$

• $Q(w)_i = \max(0, w_i)$：ReLU激活函数

• $w_1, w_2, w_3$：权重矩阵

• $b_1, b_2$：偏置向量

• $x_i$：输入数据，$y_i$：目标输出

ReLU激活：$Q(\cdot)$ 对负输入输出0，引入非线性。
层级结构：嵌套变换 $w_k^\top \cdot Q(\cdot) - b_k$ 建模复杂特征交互。

补充说明 / Supplementary Notes

数学原理推导：

1. 前向传播过程：

   • 输入层：$x_i \in \mathbb{R}^{d_0}$（原始输入，如图像像素）
   • 隐藏层1：$z^{(1)} = w_1^\top x_i - b_1$（线性变换）
     $a^{(1)} = Q(z^{(1)})$（ReLU激活，$\max(0, z^{(1)})$）
   • 隐藏层2：$z^{(2)} = w_2^\top a^{(1)} - b_2$
     $a^{(2)} = Q(z^{(2)})$
   • 输出层：$\hat{y}_i = w_3^\top a^{(2)}$（预测值）

   $\ell = \|\hat{y}_i - y_i\|^2$ 计算预测与真实值的平方误差

2. ReLU的数学特性：

   $$Q(z) = \begin{cases} z & \text{if } z > 0 \\ 0 & \text{otherwise} \end{cases}$$

   优势：

   • 解决梯度消失问题（正区间梯度恒为1）
   • 稀疏激活（约50%神经元激活）

符号扩展解释：

• $w_k \in \mathbb{R}^{d_{k} \times d_{k-1}}$：权重矩阵（$d_k$为第$k$层神经元数）

• $b_k \in \mathbb{R}^{d_k}$：偏置向量（平移决策边界）

• $Q(\cdot)$：逐元素操作（对向量/矩阵中每个元素独立应用ReLU）

实际意义：

• 特征提取：

  • 浅层学习边缘/纹理（$w_1$）
  • 中层学习部件/形状（$w_2$）
  • 高层学习语义概念（$w_3$）

• 优化挑战：

  • 非凸目标函数（存在多个局部最优）
  • 梯度计算需反向传播（链式法则）

示例（数字识别）：
输入 $x_i$ 为28×28手写数字图像（$d_0=784$）：

1. $w_1$：卷积核提取边缘（输出 $d_1=32$ 特征图）

2. $Q$：保留正激活（增强特征对比度）

3. $w_2$：组合边缘为数字部件（如"7"的横折）

4. $w_3$：组合部件为数字0-9（输出 $d_3=10$）

---

简单数值示例：最小二乘回归 / Simple Numerical Example: Least Squares Regression

问题描述 / Problem Setup

$$\min_{x} f(x) := \frac{1}{2} \|Ax - y\|^2$$

• $A \in \mathbb{R}^{n \times d}$：数据矩阵

• $y \in \mathbb{R}^{n}$：观测向量

• $x \in \mathbb{R}^{d}$：待优化变量

梯度下降 vs. 随机梯度下降 / Gradient Descent (GD) vs. Stochastic Gradient Descent (SGD)

方法	更新规则	梯度计算	单步计算成本
GD	$x_{t+1} = x_t - \eta \nabla f(x_t)$	$\nabla f(x) = A^\top (Ax - y)$	$O(nd)$
SGD	$x_{t+1} = x_t - \eta \nabla f_t(x_t)$	$\nabla f_t(x) = a_i^\top (a_i x - y_i)$	$O(d)$

核心思想：

• GD 每步使用全部 $n$ 个数据点 → 计算量大但收敛稳定。
• SGD 每步随机使用一个数据点 $(a_i, y_i)$ → 计算高效，适合大规模数据，但收敛带噪声。

模拟参数 / Simulation Parameters

• 数据：$A = \begin{bmatrix} 1 & 2 \\ 2 & 1 \\ 1 & 1 \end{bmatrix}$, $y = \begin{bmatrix} 1.5 \\ 3.5 \\ 2.0 \end{bmatrix}$ ($n=3$, $d=2$)

• 步长：$\eta = 0.1$

• 初始值：$x_0 = (0, 0)$

关键结论 / Key Takeaways

• GD：收敛平稳，但迭代计算成本高。

• SGD：单步计算成本低，在大规模问题中实际收敛更快（尽管路径有噪声）。

随机优化基础 (Preliminaries of Stochastic Optimization)

---

柯西-施瓦茨不等式 / Cauchy-Schwarz Inequality

对任意向量 $u, v \in \mathbb{R}^d$：

$$|u^\top v| \leq \|u\| \|v\|$$

符号说明：

• $u = \begin{pmatrix} u_1 \\ \vdots \\ u_d \end{pmatrix}$, $v = \begin{pmatrix} v_1 \\ \vdots \\ v_d \end{pmatrix}$：$d$维实数列向量

• $u^\top v = \sum_{i=1}^d u_i v_i$：标量积（内积）

• $\|u\| = \sqrt{u^\top u} = \sqrt{\sum_{i=1}^d u_i^2}$：欧几里得范数

几何解释：

• 单位向量情形（$\|u\|=\|v\|=1$）时，等式成立当且仅当 $u=v$ 或 $u=-v$
• 可定义向量夹角 $\alpha$：$\cos \alpha = \frac{u^\top v}{\|u\|\|v\|}$，满足 $-1 \leq \cos \alpha \leq 1$

Examples for unit vectors (‖u‖=‖v‖= 1)

Equality in Cauchy-Schwarz if and only u = v or u = −v.

---

赫尔德不等式 / Hölder’s Inequality

对 $p,q > 1$ 满足 $\frac{1}{p} + \frac{1}{q} = 1$，及任意向量 $x,y$：

$$\sum_{i=1}^n |x_i y_i| \leq \left( \sum_{i=1}^n |x_i|^p \right)^{1/p} \left( \sum_{i=1}^n |y_i|^q \right)^{1/q}$$

关联概念：

• $\ell_p$-范数：$\|x\|_p = \left( \sum_{i=1}^n |x_i|^p \right)^{1/p}$

• $p$ 值越大，大分量权重越高

• 柯西-施瓦茨不等式是 $p=q=2$ 时的特例

核心思想：通过 $\ell_p$ 和 $\ell_q$ 范数量化向量间相互作用的上界。

---

凸集 / Convex Sets

集合 $C$ 是凸集当且仅当任意两点连线仍在 $C$ 内：

$$\forall x,y \in C, \ \forall \lambda \in [0,1], \quad \lambda x + (1-\lambda)y \in C$$

左图：凸集
中图：非凸集（线段不全在集合内）
右图：非凸集（部分边界点缺失）

凸集性质 / Properties

1. 交运算封闭：凸集的交集仍是凸集

   $$\bigcap_{i \in I} C_i \text{ 凸}, \quad \forall \text{凸集 } C_i$$

2. 投影唯一性：对非空闭凸集 $C$，投影算子 $P_C(x) = \arg\min\limits_{y \in C} \|y - x\|$的解唯一

3. 非扩张性：

   $$\|P_C(x) - P_C(y)\| \leq \|x - y\|, \quad \forall x,y$$

---

利普希茨连续性 / Lipschitz Continuity

函数 $f: \mathbb{R}^d \to \mathbb{R}$ 是 $L$-利普希茨连续的若：

$$\|f(x) - f(y)\| \leq L\|x - y\|, \quad \forall x,y \in \mathbb{R}^d$$

$L$ 的意义：函数变化速率的上界
示例：$f(x) = \sqrt{x^2 + 5}$, $f(x) = \|x\|$

---

可微函数 / Differentiable Functions

函数 $f: \mathbb{R}^d \to \mathbb{R}$ 在 $x_0$ 可微若存在梯度 $\nabla f(x_0)$ 使得：

$$f(x_0 + h) \approx f(x_0) + \nabla f(x_0)^\top h$$

其中 $h$ 为微小扰动。全域可微时，其图像每点均有切超平面。

不可微函数示例

$$f(x) = \|x\| \quad \text{(欧几里得范数)}$$

特性：在原点不可微（"冰激凌锥"状图像）

---

L-光滑性 / L-Smoothness

函数 $f: \mathbb{R}^d \to \mathbb{R}$ 是 $L$-光滑的若：

1. $f$ 连续可微（梯度 $\nabla f$ 存在且连续）

2. 梯度满足 $L$-利普希茨条件：

   $$\|\nabla f(x) - \nabla f(y)\| \leq L\|x - y\|, \quad \forall x,y$$

梯度定义：

$$\nabla f(x) = \left( \frac{\partial f}{\partial x_1}(x), \dots, \frac{\partial f}{\partial x_d}(x) \right)$$

示例：$f(x) = \frac{1}{2}\|x\|^2$ 是 $1$-光滑函数

补充说明 / Supplementary Notes

数学原理推导：

1. Lipschitz常数的计算：

   $$L = \sup_{x \neq y} \frac{|f(x) - f(y)|}{\|x - y\|}$$

   即函数在任意两点间割线斜率的最大值

2. 可微函数的Lipschitz条件：
   若 $f$ 可微，则 $L = \sup_{x} \|\nabla f(x)\|$

   证明：由中值定理 $|f(x)-f(y)| = |\nabla f(\xi)^\top (x-y)| \leq \|\nabla f(\xi)\|\|x-y\|$

符号扩展解释：

• $\|x - y\|$：$\mathbb{R}^d$ 中两点间的欧氏距离

• $L$：Lipschitz常数（函数变化率的上界）

• $|f(x)-f(y)|$：函数值变化的绝对值

实际意义：

• 优化算法稳定性：

  • 梯度下降法中，$L$ 决定最大允许步长（$\eta < 2/L$）
  • 保证算法收敛性（防止振荡或发散）

• 神经网络训练：

  • 权重矩阵的Lipschitz约束控制模型敏感性
  • 提高对抗鲁棒性（抵抗输入扰动）

示例验证：

1. $f(x) = \|x\|$：

   $$| \|x\| - \|y\| | \leq \|x - y\| \quad (\text{三角不等式})$$

   → $L=1$

2. $f(x) = \sqrt{x^2 + 5}$：

   $$\left| \frac{d}{dx}\sqrt{x^2+5} \right| = \frac{|x|}{\sqrt{x^2+5}} \leq 1$$

   → $L=1$

3. 非Lipschitz函数：$f(x) = x^2$

   $$\frac{|x^2 - y^2|}{|x-y|} = |x+y| \xrightarrow{|x|,|y|\to\infty} \infty$$

   → 无全局Lipschitz常数

几何解释：

• Lipschitz连续函数的图像被限制在"斜率锥"内

• 任意两点间的垂直距离 $\leq L \times$ 水平距离

---

凸函数

---

定义与几何意义 / Definition and Geometric Interpretation

函数 $f: \mathbb{R}^d \to \mathbb{R}$ 是凸函数若：

1. 定义域 $\text{dom}(f)$ 是凸集

2. 满足凸不等式：

   $$\forall x,y \in \text{dom}(f), \ \forall \lambda \in [0,1], \quad f(\lambda x + (1-\lambda)y) \leq \lambda f(x) + (1-\lambda)f(y)$$

几何解释：函数图像上任意两点的连线（弦）位于图像上方。

补充说明 / Supplementary Notes

数学符号解释：

• $\lambda \in [0,1]$：插值参数，控制两点间的线性组合比例

• $\lambda x + (1-\lambda)y$：凸组合，表示连接 $x$ 和 $y$ 的线段上的点

• $f(\lambda x + (1-\lambda)y)$：函数在凸组合点处的值

• $\lambda f(x) + (1-\lambda)f(y)$：函数值在 $f(x)$ 和 $f(y)$ 间的线性插值

关键性质推导：

凸不等式可等价表述为：

$$\frac{f(y) - f(x)}{\|y - x\|} \geq \frac{f(z) - f(x)}{\|z - x\|}, \quad \forall z \in [x,y]$$

即函数在任意区间 $[x,y]$ 上的平均增长率单调不减

实际意义：

• 优化优势：凸函数的局部最小值即全局最小值

• 经济决策：描述边际收益递减（如生产成本函数）

• 物理系统：弹簧势能 $f(x) = \frac{1}{2}kx^2$ 是凸函数（$k>0$）

几何特性详解：

1. 弦在图像上方：

   • 对任意 $x,y$，连接 $(x,f(x))$ 和 $(y,f(y))$ 的线段
   • 始终位于函数图像 $z = f(\lambda x + (1-\lambda)y)$ 的上方

2. 无局部凹陷：

   • 函数曲线不会出现"碗状"凹陷（如 $f(x) = -x^2$）
   • 二阶可微时等价于 $\nabla^2 f(x) \succeq 0$（Hessian矩阵半正定）

示例验证：

1. 凸函数：$f(x) = x^2$

   $$f(\lambda x + (1-\lambda)y) = [\lambda x + (1-\lambda)y]^2$$

   $$\lambda f(x) + (1-\lambda)f(y) = \lambda x^2 + (1-\lambda)y^2$$

   差值：$\lambda(1-\lambda)(x-y)^2 \geq 0$ → 满足凸不等式

2. 非凸函数：$f(x) = \sin(x)$（在 $[0,2\pi]$）

   取 $x=0, y=2\pi, \lambda=0.5$：
   $f(0.5×0 + 0.5×2\pi) = \sin(\pi) = 0$
   $0.5\sin(0) + 0.5\sin(2\pi) = 0$
   但 $x=\pi/2$ 时 $f(\pi/2)=1 > 0$ → 违反凸不等式

比喻理解：

将凸函数想象成"山谷"：

• 从任意两点出发的缆车线（弦）始终高于山谷底部（函数图像）
• 水滴沿山谷下滑时，最终必汇聚到最低点（全局最优）

---

常见凸函数示例 / Examples

1. 线性函数：$f(x) = a^\top x$

2. 仿射函数：$f(x) = a^\top x + b$

3. 指数函数：$f(x) = e^{\alpha x}$

4. 范数：任意 $\mathbb{R}^d$ 上的范数（如欧几里得范数 $\|x\|$）

   范数凸性证明：
   由三角不等式 $\|x+y\| \leq \|x\| + \|y\|$ 和齐次性 $\|\alpha x\| = |\alpha|\|x\|$：

   $$\| \lambda x + (1-\lambda)y \| \leq \lambda \|x\| + (1-\lambda)\|y\|$$

---

凸函数与集合的关系 / Epigraph and Convexity

函数的图

函数的图定义为：

$$\{(x, f(x)) \mid x \in \text{dom}(f)\}$$

其中，$\text{dom}(f)$ 表示函数 $f$ 的定义域。

Epigraph（上镜图）

函数 $f: \mathbb{R}^d \to \mathbb{R}$ 的 epigraph 定义为：

$$\text{epi}(f) := \{(x, \alpha) \in \mathbb{R}^{d+1} \mid x \in \text{dom}(f), \alpha > f(x)\}$$

补充说明：epigraph 是函数图像上方的所有点集，直观理解为函数“上方”的区域。例如，如果 $f(x)$ 是凸函数，epigraph 会形成一个“碗状”凸集。

• 关键性质：

  $f$ 是凸函数 $\iff$ $\text{epi}(f)$ 是凸集

  补充说明：这个观察将函数的凸性与集合的凸性联系起来，简化了凸函数的分析，因为我们可以利用凸集的性质（如线段在集合内）来证明函数性质。

证明: $f$ 是凸函数 $\iff$ $\text{epi}(f)$ 是凸集

⇒（充分性）：假设 $f$ 是凸函数。取任意点 $(x,t), (y,s) \in \text{epi}(f)$，需证明线段 $\lambda(x,t) + (1-\lambda)(y,s)$ 在 $\text{epi}(f)$ 中，即：

$$f(\lambda x + (1-\lambda)y) \leq \lambda t + (1-\lambda)s$$

由 $f$ 的凸性（定义：$f(\lambda x + (1-\lambda)y) \leq \lambda f(x) + (1-\lambda)f(y)$），且因为 $(x,t), (y,s) \in \text{epi}(f)$ 有 $t > f(x)$ 和 $s > f(y)$，所以不等式成立。故 $\text{epi}(f)$ 是凸集。

⇐（必要性）：假设 $\text{epi}(f)$ 是凸集。取点 $(x,f(x)), (y,f(y)) \in \text{epi}(f)$。由于 $\text{epi}(f)$ 凸，线段 $\lambda(x,f(x)) + (1-\lambda)(y,f(y))$ 在 $\text{epi}(f)$ 中，即：

$$(\lambda x + (1-\lambda)y, \lambda f(x) + (1-\lambda)f(y)) \in \text{epi}(f)$$

由 epigraph 定义，$\lambda f(x) + (1-\lambda)f(y) > f(\lambda x + (1-\lambda)y)$，这等价于 $f(\lambda x + (1-\lambda)y) \leq \lambda f(x) + (1-\lambda)f(y)$。故 $f$ 是凸函数。

补充说明：证明的核心是利用 epigraph 定义中的不等式 $\alpha > f(x)$，将集合凸性转化为函数凸性。第一部分从函数凸性推导集合凸性，第二部分反之。

Jensen不等式

引理1（Jensen不等式）
设 $f$ 为凸函数，$x_1, \dots, x_m \in \text{dom}(f)$，$\lambda_1, \dots, \lambda_m \in \mathbb{R}_+$ 且满足 $\sum_{i=1}^m \lambda_i = 1$，则：

$$f\left( \sum_{i=1}^m \lambda_i x_i \right) \leq \sum_{i=1}^m \lambda_i f(x_i)$$

说明：

• 当 $m=2$ 时，即为凸函数的定义：$f(\lambda x_1 + (1-\lambda)x_2) \leq \lambda f(x_1) + (1-\lambda)f(x_2)$。
• 一般情况的证明可通过数学归纳法完成（留作练习）。核心思路是将 $m$ 个点的凸组合拆分为两两组合的递归形式。

---

可微函数的几何性质

对于可微函数 $f$，其仿射函数：

$$f(x) + \nabla f(x)^\top (y - x)$$

的图形是函数 $f$ 在点 $(x, f(x))$ 处的切线超平面。

几何解释：

• $\nabla f(x)$ 是 $f$ 在 $x$ 处的梯度（多维导数）。
• 该切线超平面在 $x$ 处与 $f$ 的曲面相切，且是 $f$ 在 $x$ 附近的局部线性逼近。
• 若 $f$ 是凸函数，该切线超平面位于整个函数的 epigraph 内（即切线在函数图像下方）。

---

凸性判据 / Convexity Criteria

一阶凸性判定

引理 2
设 $\text{dom}(f)$ 为开集且 $f$ 可微（梯度 $\nabla f(x) := \left( \frac{\partial f}{\partial x_1}(x), \dots, \frac{\partial f}{\partial x_d}(x) \right)$ 处处存在），则 $f$ 是凸函数当且仅当：

1. $\text{dom}(f)$ 是凸集；

2. 对所有 $x, y \in \text{dom}(f)$，满足：

$$f(y) \geq f(x) + \nabla f(x)^\top (y - x)$$

几何解释：

• 该不等式表明凸函数的图像始终位于其任意一点的切线超平面之上（如图形为“碗状”）。
• 梯度 $\nabla f(x)$ 是函数在 $x$ 处的最速上升方向，而 $-\nabla f(x)$ 是最速下降方向。

---

二阶凸性判定

设 $\text{dom}(f)$ 为开集且 $f$ 二阶可微（Hessian 矩阵 $\nabla^2 f(x)$ 对称且处处存在），则 $f$ 是凸函数当且仅当：

1. $\text{dom}(f)$ 是凸集；

2. 对所有 $x \in \text{dom}(f)$，Hessian 矩阵半正定（$\nabla^2 f(x) \succeq 0$），即：

$$\forall z \in \mathbb{R}^d, \quad z^\top \nabla^2 f(x) z \geq 0$$

关键概念：

• Hessian 矩阵：二阶偏导数构成的对称矩阵，描述函数的局部曲率：

$$\nabla^2 f(x) = \begin{pmatrix} \frac{\partial^2 f}{\partial x_1^2} & \cdots & \frac{\partial^2 f}{\partial x_1 \partial x_d} \\ \vdots & \ddots & \vdots \\ \frac{\partial^2 f}{\partial x_d \partial x_1} & \cdots & \frac{\partial^2 f}{\partial x_d^2} \end{pmatrix}$$

• 半正定性（$\succeq 0$）：矩阵特征值非负，表明函数在所有方向均“向上弯曲”（例如 $x^2$ 的 Hessian 为 2）。

示例

函数 $f(x_1, x_2) = x_1^2 + x_2^2$ 的 Hessian 为：

$$\nabla^2 f(x) = \begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix} \succeq 0$$

说明：该矩阵是正定矩阵（特征值均为 2 > 0），故 $f$ 是严格凸函数（旋转抛物面）。

---

凸函数性质 / Properties

保凸运算

引理 4
(i) 设 $f_1, \dots, f_m$ 为凸函数，$\lambda_1, \dots, \lambda_m \in \mathbb{R}_+$，则函数 $f := \sum_{i=1}^m \lambda_i f_i$ 在定义域 $\text{dom}(f) := \bigcap_{i=1}^m \text{dom}(f_i)$ 上是凸函数。

说明：凸函数的非负线性组合仍是凸函数（定义域取交集）。

(ii) 设 $f$ 为凸函数（$\text{dom}(f) \subseteq \mathbb{R}^d$），$g(x) = Ax + b$ 是仿射映射（$A \in \mathbb{R}^{d \times m}, b \in \mathbb{R}^d$），则复合函数 $f \circ g$（即 $x \mapsto f(Ax + b)$）在 $\text{dom}(f \circ g) := \{x \in \mathbb{R}^m : Ax + b \in \text{dom}(f)\}$ 上是凸函数。

说明：凸函数与仿射映射的复合仍保持凸性（例如 $f(2x+1)$ 是凸的）。

---

局部极小即全局极小

定义：$f$ 的局部极小点 $x$ 满足：存在 $\varepsilon > 0$，使得对所有 $\|y - x\| \leq \varepsilon$ 的 $y \in \text{dom}(f)$，有 $f(x) \leq f(y)$。

引理 5：凸函数 $f$ 的局部极小点 $x^*$ 必为全局极小点（即 $f(x^*) \leq f(y), \forall y \in \text{dom}(f)$）。
证明：
假设存在 $y$ 使 $f(y) < f(x^*)$。构造点 $y' = \lambda x^* + (1-\lambda)y$（$\lambda \in (0,1)$）。由凸性：

$$f(y') \leq \lambda f(x^*) + (1-\lambda)f(y) < f(x^*).$$

当 $\lambda \to 1$ 时，$\|y' - x^*\| \to 0$，与 $x^*$ 是局部极小矛盾。

---

临界点即全局极小

引理 6：若 $f$ 在开凸集 $\text{dom}(f)$ 上可微且凸，且 $\nabla f(x) = 0$（临界点），则 $x$ 是全局极小点。
证明：
由一阶凸性条件（引理 2），对任意 $y$：

$$f(y) \geq f(x) + \underbrace{\nabla f(x)^\top (y - x)}_{=0} = f(x).$$

几何解释：梯度为零时，切线超平面水平，函数值全局最小。

---

严格凸函数

定义：$f$ 是严格凸函数若：

1. $\text{dom}(f)$ 凸；

2. 对所有 $x \neq y$ 和 $\lambda \in (0,1)$：

$$f(\lambda x + (1-\lambda)y) < \lambda f(x) + (1-\lambda)f(y).$$

示例：

• $x^2$ 严格凸（左图）；
• 线性函数凸但不严格凸（右图）。

引理 7：严格凸函数至多有一个全局极小点。

---

约束最小化

定义：设 $f$ 凸，$X \subseteq \text{dom}(f)$ 凸集。$x \in X$ 是 $f$ 在 $X$ 上的极小点若 $f(x) \leq f(y), \forall y \in X$。

引理 8：若 $f$ 在开凸集 $\text{dom}(f)$ 上可微，$X \subseteq \text{dom}(f)$ 凸，则 $x^* \in X$ 是最小点当且仅当：

$$\nabla f(x^*)^\top (x - x^*) \geq 0, \quad \forall x \in X.$$

几何解释：在 $x^*$ 处，梯度方向与可行方向夹角 $\leq 90^\circ$（即无下降方向）。

---

全局最小值的存在性

• 问题：如何确保函数存在全局最小值？

• 反例：即使函数有下界（bounded below），全局最小值也可能不存在。
  例如：$f(x) = e^x$ 在 $\mathbb{R}$ 上有下界（$f(x) > 0$），但无全局最小值（$\lim_{x \to -\infty} e^x = 0$ 却不可达）。

关键点：函数有下界仅说明值域存在下确界（infimum），但未必能在某点取到该值（即最小值）。

定义：$\alpha$-下水平集

设函数 $f: \mathbb{R}^d \to \mathbb{R}$ 和实数 $\alpha \in \mathbb{R}$，定义其 $\alpha$-下水平集为：

$$f_{\leq \alpha} := \{ \mathbf{x} \in \mathbb{R}^d \mid f(\mathbf{x}) \leq \alpha \}$$

)

• 含义：该集合包含所有使函数值不超过 $\alpha$ 的点 $\mathbf{x}$。

• 作用：下水平集的性质（如闭合性、有界性）与极小值的存在性密切相关。

---

凸优化问题

形式：

$$\min_{x \in D} f(x),$$

其中 $f$ 凸，$D \subseteq \text{dom}(f)$ 凸集（如 $D = \mathbb{R}^d$）。
关键性质：

• 局部极小即全局极小。

• 可证算法（坐标下降、梯度下降、随机梯度下降等）收敛到全局最优解。

收敛速率示例：梯度下降的收敛速率为 $O(1/t)$，即：

$$f(x_t) - f(x^*) \leq \frac{c}{t},$$

其中 $x^*$ 为最优解，$c$ 为常数（依赖初始条件和函数性质）。