Math-04.优化-02.凸优化基础

本页建立凸优化（convex optimization）基础——理解「何时梯度下降一定能找到全局最优」。

段末注释：凸集（convex set）中任意两点连线仍在集合内；凸函数（convex function）图像在任意弦上方，局部极小即全局极小。

系列入口：00.系列规划 | 前置：01 总论

---

1. 凸集（D2）

集合 $C \subseteq \mathbb{R}^d$ 凸，若 $\forall \mathbf{x},\mathbf{y} \in C$，$\lambda \in [0,1]$：

$$
\lambda \mathbf{x} + (1-\lambda)\mathbf{y} \in C
$$

凸	非凸
超平面 ${\mathbf{x}: \mathbf{a}^\top\mathbf{x}=b}$	两个分离圆的并
半空间 $\mathbf{a}^\top\mathbf{x} \le b$	环面
$|\mathbf{x}|_2 \le r$（球）	ReLU 网络的参数空间约束一般非凸

可行域为凸集 + 目标凸 → 凸优化问题。

---

2. 凸函数（D3）

$f: C \to \mathbb{R}$ 凸，若

$$
f(\lambda \mathbf{x} + (1-\lambda)\mathbf{y}) \le \lambda f(\mathbf{x}) + (1-\lambda) f(\mathbf{y})
$$

一阶条件（可微）：$f(\mathbf{y}) \ge f(\mathbf{x}) + \nabla f(\mathbf{x})^\top(\mathbf{y}-\mathbf{x})$。

二阶条件（二阶可微）：Hessian $H \succeq 0$（半正定，Math-03/07）。

强凸：$H \succ \mu I$，$\mu>0$ → 唯一全局极小，GD 线性收敛。

---

3. 凸优化问题（D3–D6）

$$
\min_{\mathbf{x} \in C} f(\mathbf{x}) \quad \text{s.t.} \quad f \text{ 凸},, C \text{ 凸}
$$

关键定理：任一局部极小 = 全局极小；一阶条件 $\nabla f(\mathbf{x}^*)=\mathbf{0}$ 即最优（无约束）。

ML 问题	凸性
线性回归 MSE	凸（对 $\boldsymbol{\beta}$）
Ridge 回归	强凸
Lasso	凸非光滑（$L_1$）
Logistic 回归 + CE	凸
SVM（hinge + 约束）	凸二次规划
2+ 层 ReLU 网络	非凸

---

4. Jensen 不等式（D3）

若 $\varphi$ 凸，$X$ 随机变量：

$$
\varphi(\mathbb{E}[X]) \le \mathbb{E}[\varphi(X)]
$$

应用：证明 KL 非负、EM 算法单调性、某些损失下界。

---

5. ML 意义（D7）

场景	启示
线性/广义线性模型	凸 → SGD 稳、解唯一（强凸时）
深网	非凸 → 多极小、鞍点；靠过参数化与 SGD 噪声
凸松弛	某些组合问题用凸 surrogate
正则化	$L_2$ 使问题强凸化

---

6. 局限（D8）

问题	说明
深网非凸	凸理论不直接套用
Lasso 非光滑	需近端梯度、坐标下降
约束 SVM	见 06 Lagrange
数值 Hessian	大规模 $d$ 不可显式求

---

7. sklearn 示例（D12）

import numpy as np
from sklearn.linear_model import LogisticRegression

X = np.random.randn(200, 5)
y = (X[:, 0] + X[:, 1] > 0).astype(int)

# 凸优化：L2 正则 logistic，liblinear/lbfgs 求全局最优
clf = LogisticRegression(penalty="l2", C=1.0, solver="lbfgs", max_iter=500)
clf.fit(X, y)
print("coef shape:", clf.coef_.shape)

---

8. 小结

凸 = 可证明全局最优；ML 经典线性模型多凸，深网非凸但实践可训。下一篇：06 约束与 Lagrange | 07 二阶法。

系列导航：01 总论 | 03 SGD