优化理论

概述

优化理论是数学与工程的核心分支，研究如何在给定约束条件下找到目标函数的最优解。在机器学习与深度学习中，几乎所有模型训练都归结为优化问题。

\[ \min_{x \in \mathbb{R}^n} f(x) \quad \text{s.t.} \quad g_i(x) \leq 0, \; h_j(x) = 0 \]

---

1. 凸集与凸函数

1.1 凸集

集合 \(C \subseteq \mathbb{R}^n\) 是凸集，当且仅当对任意 \(x, y \in C\) 和 \(\theta \in [0, 1]\)：

\[ \theta x + (1 - \theta) y \in C \]

常见凸集：

• 超平面 \(\{x \mid a^T x = b\}\)
• 半空间 \(\{x \mid a^T x \leq b\}\)
• 球 \(\{x \mid \|x - x_c\| \leq r\}\)
• 多面体（线性不等式的交集）

性质：凸集的交集仍是凸集。

1.2 凸函数

函数 \(f: \mathbb{R}^n \to \mathbb{R}\) 是凸函数，当且仅当其定义域是凸集，且对任意 \(x, y\) 和 \(\theta \in [0, 1]\)：

\[ f(\theta x + (1 - \theta) y) \leq \theta f(x) + (1 - \theta) f(y) \]

等价条件（二次可微时）：

• 一阶条件：\(f(y) \geq f(x) + \nabla f(x)^T (y - x)\)
• 二阶条件：\(\nabla^2 f(x) \succeq 0\)（Hessian半正定）

常见凸函数：

函数	定义域	凸性
\(\|x\|_p\) (\(p \geq 1\))	\(\mathbb{R}^n\)	凸
\(e^{ax}\)	\(\mathbb{R}\)	凸
\(x \log x\)	\(\mathbb{R}_{++}\)	凸
\(-\log x\)	\(\mathbb{R}_{++}\)	凸
\(\max(x_1, \ldots, x_n)\)	\(\mathbb{R}^n\)	凸

1.3 凸优化问题

\[ \min_{x} f(x) \quad \text{s.t.} \quad g_i(x) \leq 0, \; Ax = b \]

其中 \(f\) 和 \(g_i\) 都是凸函数。

核心性质：凸优化的局部最优解即为全局最优解。

---

2. 无约束优化

2.1 梯度下降法

基本迭代：

\[ x_{k+1} = x_k - \alpha \nabla f(x_k) \]

其中 \(\alpha > 0\) 是学习率（步长）。

收敛性分析：

假设 \(f\) 是 \(L\)-光滑的（\(\|\nabla f(x) - \nabla f(y)\| \leq L\|x - y\|\)）：

• 步长 \(\alpha = \frac{1}{L}\) 时：\(f(x_k) - f^* \leq \frac{L\|x_0 - x^*\|^2}{2k}\)
• 收敛速率：\(O(1/k)\)（次线性）

若 \(f\) 还是 \(\mu\)-强凸的（\(\nabla^2 f(x) \succeq \mu I\)）：

• 收敛速率：\(O\left(\left(\frac{L - \mu}{L + \mu}\right)^k\right)\)（线性收敛）
• 条件数 \(\kappa = L / \mu\) 越大，收敛越慢

def gradient_descent(f_grad, x0, lr=0.01, tol=1e-6, max_iter=10000):
    """基本梯度下降法"""
    x = x0.copy()
    for k in range(max_iter):
        grad = f_grad(x)
        if np.linalg.norm(grad) < tol:
            break
        x = x - lr * grad
    return x, k

2.2 学习率选择

固定学习率：简单但需要调参

线搜索（Backtracking Line Search）：

给定下降方向 \(d\)，寻找步长 \(\alpha\) 满足 Armijo条件：

\[ f(x + \alpha d) \leq f(x) + c_1 \alpha \nabla f(x)^T d \]

其中 \(c_1 \in (0, 1)\)，通常 \(c_1 = 10^{-4}\)。

精确线搜索：

\[ \alpha^* = \arg\min_{\alpha > 0} f(x + \alpha d) \]

2.3 梯度下降变体

graph TD
    GD[梯度下降] --> SGD[随机梯度下降]
    GD --> Mini[小批量梯度下降]
    GD --> Momentum[动量法]
    Momentum --> NAG[Nesterov加速]
    SGD --> Adam[Adam优化器]
    SGD --> Adagrad[Adagrad]
    Adagrad --> RMSProp[RMSProp]
    RMSProp --> Adam

动量法：

\[ v_{k+1} = \beta v_k + \nabla f(x_k), \quad x_{k+1} = x_k - \alpha v_{k+1} \]

Nesterov加速梯度（NAG）：

\[ v_{k+1} = \beta v_k + \nabla f(x_k - \alpha \beta v_k), \quad x_{k+1} = x_k - \alpha v_{k+1} \]

对于凸函数，NAG的收敛速率为 \(O(1/k^2)\)，优于普通梯度下降的 \(O(1/k)\)。

---

3. 约束优化

3.1 拉格朗日乘子法

对于等式约束优化问题：

\[ \min_x f(x) \quad \text{s.t.} \quad h_i(x) = 0, \; i = 1, \ldots, p \]

构造拉格朗日函数：

\[ \mathcal{L}(x, \nu) = f(x) + \sum_{i=1}^{p} \nu_i h_i(x) \]

必要条件：

\[ \nabla_x \mathcal{L} = 0, \quad h_i(x) = 0 \]

3.2 KKT条件

对于一般约束优化问题：

\[ \min_x f(x) \quad \text{s.t.} \quad g_i(x) \leq 0, \; h_j(x) = 0 \]

KKT条件（Karush-Kuhn-Tucker）：

\[ \begin{aligned} \nabla f(x^*) + \sum_i \lambda_i \nabla g_i(x^*) + \sum_j \nu_j \nabla h_j(x^*) &= 0 & \text{(驻点条件)} \\ g_i(x^*) &\leq 0 & \text{(原始可行性)} \\ \lambda_i &\geq 0 & \text{(对偶可行性)} \\ \lambda_i g_i(x^*) &= 0 & \text{(互补松弛)} \end{aligned} \]

互补松弛条件的含义：若 \(\lambda_i > 0\)，则 \(g_i(x^*) = 0\)（约束紧致）。

KKT条件的重要性

对于凸优化问题，KKT条件是充分必要条件。这意味着满足KKT条件的点一定是全局最优解。支持向量机（SVM）的求解就依赖于KKT条件。

3.3 约束优化示例

问题：在单位球上最小化线性函数

\[ \min_x c^T x \quad \text{s.t.} \quad \|x\|^2 \leq 1 \]

KKT条件：

• \(c + 2\lambda x^* = 0 \implies x^* = -\frac{c}{2\lambda}\)
• \(\lambda(\|x^*\|^2 - 1) = 0\)
• 由互补松弛：\(\lambda = \frac{\|c\|}{2}\)，\(x^* = -\frac{c}{\|c\|}\)

---

4. 对偶理论

4.1 拉格朗日对偶

拉格朗日对偶函数：

\[ g(\lambda, \nu) = \inf_x \mathcal{L}(x, \lambda, \nu) = \inf_x \left[ f(x) + \sum_i \lambda_i g_i(x) + \sum_j \nu_j h_j(x) \right] \]

性质：\(g(\lambda, \nu)\) 是凹函数（即使原问题非凸）。

弱对偶性：

\[ d^* = \max_{\lambda \geq 0, \nu} g(\lambda, \nu) \leq \min_x f(x) = p^* \]

对偶间隙：\(p^* - d^* \geq 0\)。

强对偶性：

当 Slater条件成立（存在严格可行点 \(\tilde{x}\)：\(g_i(\tilde{x}) < 0\)）时：

\[ p^* = d^* \]

4.2 对偶问题的应用

SVM的对偶形式是对偶理论最经典的应用之一：

原始问题：

\[ \min_{w, b} \frac{1}{2}\|w\|^2 \quad \text{s.t.} \quad y_i(w^T x_i + b) \geq 1 \]

对偶问题：

\[ \max_\alpha \sum_i \alpha_i - \frac{1}{2} \sum_{i,j} \alpha_i \alpha_j y_i y_j x_i^T x_j \quad \text{s.t.} \quad \alpha_i \geq 0, \; \sum_i \alpha_i y_i = 0 \]

---

5. 牛顿法与拟牛顿法

5.1 牛顿法

利用二阶信息进行优化：

\[ x_{k+1} = x_k - [\nabla^2 f(x_k)]^{-1} \nabla f(x_k) \]

收敛性：在最优解附近具有二次收敛速率。

优点：

• 收敛速度快（二次收敛）
• 对条件数不敏感

缺点：

• 需要计算和存储 \(n \times n\) 的Hessian矩阵
• 每步计算复杂度 \(O(n^3)\)
• Hessian可能不正定

5.2 拟牛顿法（BFGS）

用矩阵 \(B_k\) 近似Hessian：

\[ x_{k+1} = x_k - \alpha_k B_k^{-1} \nabla f(x_k) \]

BFGS更新公式：

\[ B_{k+1} = B_k - \frac{B_k s_k s_k^T B_k}{s_k^T B_k s_k} + \frac{y_k y_k^T}{y_k^T s_k} \]

其中 \(s_k = x_{k+1} - x_k\)，\(y_k = \nabla f(x_{k+1}) - \nabla f(x_k)\)。

L-BFGS：有限内存版本，只存储最近 \(m\) 步的 \(\{s_k, y_k\}\)，适用于大规模问题。

5.3 各方法比较

方法	收敛速率	每步复杂度	内存	适用场景
梯度下降	\(O(1/k)\)	\(O(n)\)	\(O(n)\)	大规模、简单
牛顿法	二次	\(O(n^3)\)	\(O(n^2)\)	小规模、精确
BFGS	超线性	\(O(n^2)\)	\(O(n^2)\)	中等规模
L-BFGS	超线性	\(O(mn)\)	\(O(mn)\)	大规模

---

6. 凸优化特殊问题

6.1 线性规划（LP）

\[ \min_x c^T x \quad \text{s.t.} \quad Ax \leq b, \; x \geq 0 \]

求解方法：单纯形法、内点法。

6.2 二次规划（QP）

\[ \min_x \frac{1}{2} x^T Q x + c^T x \quad \text{s.t.} \quad Ax \leq b \]

SVM就是一个二次规划问题。

6.3 半正定规划（SDP）

\[ \min_X \langle C, X \rangle \quad \text{s.t.} \quad \langle A_i, X \rangle = b_i, \; X \succeq 0 \]

应用：松弛组合优化问题、控制理论。

---

7. 非凸优化

7.1 挑战

• 存在多个局部极小值
• 鞍点问题（高维空间中普遍存在）
• NP-hard（一般情况下）

7.2 深度学习中的非凸优化

深度神经网络的损失函数是高度非凸的，但实践中SGD及其变体仍然有效：

• 过参数化：参数远多于数据点，局部极小值质量趋于一致
• SGD的隐式正则化：噪声有助于逃离尖锐极小值
• 损失曲面结构：实际中鞍点多于坏的局部极小值

# Adam优化器实现
def adam(f_grad, x0, lr=0.001, beta1=0.9, beta2=0.999, eps=1e-8, max_iter=10000):
    x = x0.copy()
    m = np.zeros_like(x)  # 一阶矩估计
    v = np.zeros_like(x)  # 二阶矩估计
    for t in range(1, max_iter + 1):
        grad = f_grad(x)
        m = beta1 * m + (1 - beta1) * grad
        v = beta2 * v + (1 - beta2) * grad**2
        m_hat = m / (1 - beta1**t)  # 偏差修正
        v_hat = v / (1 - beta2**t)
        x = x - lr * m_hat / (np.sqrt(v_hat) + eps)
    return x

---

8. 优化理论与机器学习的联系

graph LR
    A[优化理论] --> B[模型训练]
    A --> C[超参数调优]
    A --> D[约束学习]
    B --> E[损失函数最小化]
    B --> F[正则化 = 约束优化]
    C --> G[贝叶斯优化]
    D --> H[公平性约束]
    D --> I[物理约束]

机器学习概念	优化理论对应
训练	无约束/约束优化
正则化	拉格朗日对偶
SVM	二次规划 + KKT
神经网络	非凸优化
超参数搜索	黑盒优化

---

参考资料

• Boyd & Vandenberghe, Converta Optimization（经典教材，免费在线阅读）
• Nocedal & Wright, Numerical Optimization
• Bertsekas, Nonlinear Programming

相关章节：

• 深度学习：优化与正则
• 微积分
• 线性代数

---

评论