🌳 Ch24 数值分析与凸优化
├─ §01 浮点与数值稳定性
│ └─ IEEE 754 标准
│ │ └─ FP32 (1+8+23)
│ │ └─ FP16 (1+5+10)
│ │ └─ BF16 (1+8+7)
│ │ └─ FP8 / FP4
│ │ └─ 1.58-bit (BitNet)
│ └─ Machine Epsilon
│ │ └─ FP32 = 1.19e-7
│ │ └─ FP16 = 9.77e-4
│ │ └─ bf16 = 7.81e-3
│ └─ 误差类型
│ │ └─ 舍入误差
│ │ └─ 截断误差
│ │ └─ Catastrophic Cancellation
│ └─ 关键算法
│ │ └─ Kahan 求和
│ │ └─ Softmax 减 max
│ │ └─ BatchNorm
│ │ └─ Loss Scaling
├─ §02 迭代法与稀疏线代
│ └─ 矩阵分解
│ │ └─ LU / QR / SVD / Cholesky
│ └─ 迭代法
│ │ └─ CG (Conjugate Gradient)
│ │ └─ GMRES / BiCGSTAB
│ │ └─ 收敛: 残差 < tol
│ └─ 稀疏存储
│ │ └─ CSR (Compressed Sparse Row)
│ │ └─ COO (Coordinate)
│ │ └─ ELL (ELLPACK)
│ │ └─ Block Sparse
│ └─ 预条件子
│ │ └─ Jacobi / ILU
│ │ └─ AMG (Algebraic Multigrid)
│ │ └─ Krylov 子空间
├─ §03 凸集与凸函数
│ └─ 凸集
│ │ └─ 定义: 闭合于凸组合
│ │ └─ 凸包 / 凸锥
│ │ └─ 半空间 / 多面体
│ │ └─ 仿射集
│ └─ 凸函数
│ │ └─ 判别 1: 一阶条件
│ │ └─ 判别 2: Hessian 半正定
│ │ └─ 强凸 (μ > 0)
│ │ └─ 平滑 (L-smooth)
│ │ └─ 强凸 + 平滑 → 线性收敛
│ └─ Lipschitz 梯度
│ │ └─ ||∇f(x) - ∇f(y)|| ≤ L||x-y||
│ │ └─ SGD 收敛基础
│ └─ 共轭函数
│ │ └─ f*(y) = sup_x {yᵀx - f(x)}
│ │ └─ Fenchel-Young 不等式
├─ §04 对偶与 KKT
│ └─ Lagrange 函数
│ │ └─ L(x,λ,ν) = f(x) + λg(x) + νh(x)
│ │ └─ g ≤ 0 不等约束
│ │ └─ h = 0 等约束
│ └─ 对偶
│ │ └─ g(λ,ν) = inf_x L(x,λ,ν)
│ │ └─ 弱对偶: g ≤ f(x*)
│ │ └─ 强对偶: g(λ*) = f(x*)
│ │ └─ Slater 条件
│ │ └─ KKT 4 条件
│ │ └─ Stationarity
│ │ └─ Primal Feasibility
│ │ └─ Dual Feasibility
│ │ └─ Complementary Slackness
│ │ └─ SVM 推导经典
├─ §05 二阶方法
│ └─ Newton 方法
│ │ └─ x_{k+1} = x_k - H⁻¹ ∇f
│ │ └─ 二次收敛
│ │ └─ 每步 O(n³) Hessian 逆
│ └─ Quasi-Newton
│ │ └─ BFGS (秩 2 修正)
│ │ └─ L-BFGS (Limited)
│ │ └─ O(mn) 内存, 适合大模型
│ └─ Trust Region
│ │ └─ 信赖域内求 min
│ │ └─ 比 Line Search 稳健
│ └─ Natural Gradient
│ │ └─ F⁻¹ ∇L
│ │ └─ Fisher 信息矩阵
│ └─ K-FAC / Shampoo
│ │ └─ 实用化二阶方法
│ │ └─ Transformer 训练加速 2-3×
│ │ └─ Google Shampoo 2024
├─ §06 内点法与约束优化
│ └─ Interior Point
│ │ └─ Barrier Method
│ │ └─ 经典 KKT 求解
│ │ └─ 中等规模问题
│ └─ 投影梯度
│ │ └─ Projected Gradient
│ │ └─ 简单约束
│ └─ Frank-Wolfe
│ │ └─ 线性最小化 oracle
│ │ └─ 凸包优化
│ └─ SQP
│ │ └─ Sequential Quadratic Programming
│ │ └─ 强约束优化
│ └─ ADMM
│ │ └─ 增广 Lagrangian
│ │ └─ 分布式优化
├─ §07 分布式与随机优化
│ └─ 同步 SGD
│ │ └─ AllReduce 通信
│ │ └─ 稳定但慢
│ └─ 异步 SGD / Hogwild!
│ │ └─ 无锁并发
│ │ └─ 稀疏梯度有效
│ └─ AllReduce
│ │ └─ Ring AllReduce
│ │ └─ NCCL / Gloo
│ │ └─ O(N) 带宽最优
│ └─ Parameter Server
│ │ └─ 异步参数更新
│ │ └─ 超大规模
│ └─ FedAvg
│ │ └─ 联邦学习
│ │ └─ 客户端加权平均
│ │ └─ 隐私保护
│ └─ 弹性平均 (EA-SGD)
│ │ └─ Elastic Averaging
│ │ └─ 异步 + 一致性
│ │ └─ 拜占庭鲁棒