凸优化与拉格朗日对偶理论

概述

凸优化是优化理论中最重要的分支之一，它研究的是凸函数在凸集上的最小化问题。凸优化的魅力在于：任何局部最优解都是全局最优解，且存在高效的算法来求解这些问题。¹

为什么凸优化重要？

• SVM的推导依赖于凸优化对偶
• GAN的训练涉及非凸优化，但可以用凸松弛分析
• 深度学习优化器的理论分析常常在凸设定下进行

---

凸集与凸函数

凸集的定义

定义：集合 $C\subseteq {\mathbb{R}}^n$ 称为凸集，如果对于任意 $x,y\in C$ 和任意 $\lambda \in [0,1]$，有：

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

几何直观：连接凸集中任意两点的线段完全落在集合内部。

凸集示例：                    非凸集示例：
    ┌─────┐                       ╱ ╲
   ╱       ╲                     ╱   ╲
  │         │                   ╱     ╲
  │         │                  ○───────○
   ╲       ╱                     凹口
    └─────┘

常见凸集

类型	定义	凸性验证
超平面	$\{x:a^{T}x=b\}$	凸
半空间	$\{x:a^{T}x\le b\}$	凸
球	$\{x:\Vert x-x_c\Vert \le r\}$	凸
多面体	$\{x:Ax\le b,Cx=d\}$	凸
凸锥	$\{x:x={\sum }_i{\lambda }_i{v}_i,{\lambda }_i\ge 0\}$	凸

凸函数的定义

定义：函数 $f:{\mathbb{R}}^n\to \mathbb{R}\cup \{+\infty \}$ 称为凸函数，如果其定义域 $\text{dom}(f)$ 是凸集，且对任意 $x,y\in \text{dom}(f)$ 和 $\lambda \in [0,1]$：

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

几何直观：函数图像上任意两点之间的线段位于函数图像上方。

    f(y)
     ╱
    ╱   ╲
   ╱  ╲  ╲        ← 凸函数：弦在函数上方
  ╱    ╲  ╲
 ╱──────╲──╲────
   λx+(1-λ)y

凸函数判定

一阶条件：可微函数 $f$ 凸 $⟺$ $\nabla f$ 是单调的：

$$f(y)\ge f(x)+\nabla f(x{)}^T(y-x),\forall x,y$$

二阶条件：二阶可微函数 $f$ 凸 $⟺$ Hessian矩阵半正定：

$${\nabla }^{2}f(x)⪰0,\forall x$$

常见凸函数

函数	定义	Hessian
指数函数	$e^{ax}$	$a^2{e}^{ax}I⪰0$
负对数	$-\log (x)$	$\frac{1}{x^2}⪰0$
范数	$\Vert x{\Vert }_p$	取决于 $p$
二次函数	$x^{T}Qx+b^{T}x+c$（$Q⪰0$）	$Q$
Logistic损失	$\log (1+e^{-y})$	半正定

---

凸优化问题

标准形式

凸优化问题的标准形式为：

$$\begin{array}{rl}\underset{x}{\min }& f(x)\\ \text{s.t.}& g_i(x)\le 0,i=1,\dots ,m\\ & h_j(x)=0,j=1,\dots ,p\end{array}$$

其中：

• $f$ 必须是凸函数
• $g_i$ 必须是凸函数
• $h_j$ 必须是仿射函数（$Ax=b$ 形式）

注意：约束 $g_i(x)\le 0$ 定义了凸集 $\{x:g_i(x)\le 0\}$。

机器学习中的凸优化例子

1. 支持向量机（SVM）

原始问题：

$$\begin{array}{rl}\underset{w,b,\xi }{\min }& \frac{1}{2}\Vert w{\Vert }^2+C\sum _{i=1}^n{\xi }_i\\ \text{s.t.}& y_i(w^T{x}_i+b)\ge 1-{\xi }_i\\ & {\xi }_i\ge 0\end{array}$$

2. LASSO回归

$$\underset{w}{\min }\Vert y-Xw{\Vert }^2+\lambda \Vert w{\Vert }_1$$

3. Logistic回归

$$\underset{w}{\min }\sum _{i=1}^n\log (1+e^{-y_i{w}^T{x}_i})$$

---

拉格朗日函数

定义

对于原始问题：

$$\begin{array}{rl}\underset{x}{\min }& f(x)\\ \text{s.t.}& g_i(x)\le 0\end{array}$$

拉格朗日函数定义为：

$$L(x,\lambda )=f(x)+\sum _{i=1}^m{\lambda }_i{g}_i(x)$$

其中 ${\lambda }_i\ge 0$ 称为拉格朗日乘子或对偶变量。

对偶函数

对偶函数（Dual Function）是拉格朗日函数关于 $x$ 的下确界：

$$d(\lambda )=\underset{x\in \mathcal{D}}{\inf }L(x,\lambda )=\underset{x\in \mathcal{D}}{\inf }\left(f(x)+\sum _{i=1}^m{\lambda }_i{g}_i(x)\right)$$

其中 $\mathcal{D}={\bigcap }_i\text{dom}(g_i)$ 是定义域交集。

弱对偶性

定理（弱对偶性）：对于任意 $\lambda ⪰0$：

$$d(\lambda )\le p^{\star }$$

其中 $p^{\star }$ 是原始问题的最优值。

证明：

$$d(\lambda )=\underset{x}{\inf }L(x,\lambda )\le L(x^{\star },\lambda )\le f(x^{\star })=p^{\star }$$

其中第一个不等号来自下确界定义，第二个不等号来自 ${\lambda }_i\ge 0$ 和 $g_i(x^{\star })\le 0$。

强对偶性

定义：如果 $d^{\star }=p^{\star }$，其中 $d^{\star }={\sup }_{\lambda }d(\lambda )$ 是对偶问题的最优值，则称强对偶性成立。

Slater条件：如果存在严格可行点 $x$ 使得：

$$g_i(x)<0,\forall i$$

则强对偶性成立（对于仿射约束也成立）。

几何直观：

        原始最优 p*
         │
    p*   │    ╭─────── 弱对偶间隙
         │   ╱
         │  ╱
    d*   │ ╱
         │╱
         ─────────────────  λ

---

KKT最优性条件

KKT条件（Karush-Kuhn-Tucker）

对于凸优化问题，如果满足Slater条件，则 $x^{\star }$ 是最优解当且仅当存在 ${\lambda }^{\star }⪰0$ 使得：

1. 平稳性（Stationarity）：

   $$\nabla f(x^{\star })+\sum _{i=1}^m{\lambda }_i^{\star }\nabla g_i(x^{\star })=0$$

2. 原始可行性（Primal Feasibility）：

   $$g_i(x^{\star })\le 0,\forall i$$

3. 对偶可行性（Dual Feasibility）：

   $${\lambda }_i^{\star }\ge 0,\forall i$$

4. 互补松弛性（Complementary Slackness）：

   $${\lambda }_i^{\star }{g}_i(x^{\star })=0,\forall i$$

互补松弛性的含义

• 如果 ${\lambda }_i^{\star }>0$，则 $g_i(x^{\star })=0$（该约束在边界）
• 如果 $g_i(x^{\star })<0$，则 ${\lambda }_i^{\star }=0$（该约束非活跃）

直观：只有”活跃”的约束才会对对偶问题有贡献。

无约束情形

当 $m=0$（无不等式约束）时，KKT条件退化为：

$$\nabla f(x^{\star })=0$$

这正是我们熟悉的梯度为零的极值条件。

---

拉格朗日对偶在机器学习中的应用

1. SVM的对偶推导

SVM的原始问题是：

$$\underset{w,b,\xi }{\min }\frac{1}{2}\Vert w{\Vert }^2+C\sum _{i=1}^n{\xi }_i$$

其对偶问题为：

$$\begin{array}{rl}\underset{\alpha }{\max }& \sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i,j}{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j\\ \text{s.t.}& 0\le {\alpha }_i\le C\\ & \sum _{i=1}^n{\alpha }_i{y}_i=0\end{array}$$

KKT条件解读：

• ${\alpha }_i=0\Rightarrow x_i$ 在间隔之外（非支持向量）
• $0<{\alpha }_i<C\Rightarrow x_i$ 在间隔边界上（自由支持向量）
• ${\alpha }_i=C\Rightarrow x_i$ 在间隔内部或错误一侧（边界支持向量）

2. Logistic回归的对偶形式

Logistic回归的对偶形式揭示了它与最大熵模型的联系：

$$\underset{\alpha }{\max }\sum _{i=1}^n{\alpha }_i{y}_i-\sum _{i=1}^n\log \left(1+\exp \left(-{\alpha }_i\right)\right)-\frac{1}{2C}\Vert X^{T}y\alpha {\Vert }^2$$

3. 核SVM与表示定理

当使用核函数 $K(x,x^{\prime })$ 时，对偶变量 $\alpha$ 的稀疏性使得SVM具有高效的表示：

$$f(x)=\sum _{i\in SV}{\alpha }_i{y}_{i}K(x_i,x)+b$$

表示定理（Representer Theorem）：对于形如 ${\min }_{f\in {\mathcal{H}}_K}{\sum }_i\ell (f(x_i),y_i)+\lambda \Vert f{\Vert }_K^2$ 的问题，最优解可以表示为核函数的有限线性组合。

---

对偶计算实例

Python实现：SVM对偶求解

import numpy as np
from scipy.optimize import minimize
 
def solve_dual_svm(X, y, C=1.0):
    """
    求解SVM对偶问题
    
    对偶问题：
    max_α Σα_i - 1/2 Σα_iα_jy_iy_j(x_i·x_j)
    s.t. 0 ≤ α_i ≤ C, Σα_i y_i = 0
    """
    n, d = X.shape
    
    # 定义目标函数（取负号因为scipy是最小化）
    def objective(alpha):
        alpha = np.array(alpha)
        # 线性核
        K = X @ X.T
        return -np.sum(alpha) + 0.5 * (alpha * y) @ K @ (alpha * y)
    
    # 约束
    constraints = [
        {'type': 'eq', 'fun': lambda a: np.dot(a, y)}  # Σα_i y_i = 0
    ]
    
    # 边界
    bounds = [(0, C) for _ in range(n)]
    
    # 初始点
    alpha0 = np.zeros(n)
    
    # 求解
    result = minimize(objective, alpha0, method='SLSQP',
                     bounds=bounds, constraints=constraints)
    
    return result.x
 
# 示例
np.random.seed(42)
X = np.random.randn(50, 2)
y = np.sign(X[:, 0] + 0.5 * X[:, 1] + np.random.randn(50) * 0.3)
 
alpha = solve_dual_svm(X, y, C=1.0)
print(f"非零α的数量（支持向量数）: {np.sum(alpha > 1e-6)}")
print(f"α的范围: [{alpha.min():.4f}, {alpha.max():.4f}]")

C++实现：简单凸优化验证

#include <bits/stdc++.h>
using namespace std;
 
// 验证二次凸函数
// f(x) = (1/2)x^T Q x + b^T x + c
// Hessian: Q (需要正定)
 
int main() {
    // 定义二次函数 f(x1, x2) = 0.5*(x1^2 + 2*x2^2) - x1 - 2*x2
    // Hessian = [[1, 0], [0, 2]] (正定)
    
    cout << "二次凸函数最小化演示" << endl;
    cout << "f(x1, x2) = 0.5*(x1^2 + 2*x2^2) - x1 - 2*x2" << endl;
    cout << "最优解: x* = (1, 0.5)" << endl;
    cout << "最优值: f* = -2.5" << endl;
    
    // 验证KKT条件
    // ∇f(x) = [x1 - 1, 2*x2 - 2] = 0
    // x1 = 1, x2 = 1 (原设定有误，修正为1)
    // 实际上 ∇f = [x1 - 1, 2*x2 - 2] = 0 => x1 = 1, x2 = 1
    
    double x1 = 1.0, x2 = 1.0;
    double f_val = 0.5*(x1*x1 + 2*x2*x2) - x1 - 2*x2;
    
    cout << "\n在 x = (1, 1) 处:" << endl;
    cout << "梯度: [" << (x1 - 1) << ", " << (2*x2 - 2) << "]" << endl;
    cout << "函数值: " << f_val << endl;
    
    // 验证凸性
    Eigen::Matrix2d Q;
    Q << 1, 0, 0, 2;
    cout << "\nHessian矩阵 Q:" << endl;
    cout << Q << endl;
    
    // 计算特征值
    Eigen::SelfAdjointEigenSolver<Eigen::Matrix2d> solver(Q);
    cout << "特征值: " << solver.eigenvalues().transpose() << endl;
    cout << "（正定，因为特征值 > 0）" << endl;
    
    return 0;
}

---

对偶问题的几何解释

对偶间隙

对偶间隙（Duality Gap）是原始目标值与对偶目标值之间的差距：

$$\text{gap}=p^{\star }-d^{\star }\ge 0$$

当强对偶性成立时，对偶间隙为0。

几何直观：约束满足区域

         可行域
         ╱ ╲
        ╱   ╲
       ╱     ╲___  等高线 f(x) = c
      ╱         ╲ ╲
     ╱           ╲  ╲
    ╱───────────────╲__╲
                      最优点

互补松弛的可视化

约束 g(x) ≤ 0：
                    g(x)
                      │
         ─────────────┼────────────  g(x) = 0
                      │
                      │    活跃约束
                      │    λ > 0
                      │
    非活跃约束         │
    λ = 0             │
                      ↓
                ←─ x* ─→
                  
当 g(x*) = 0 时，约束在边界上
当 g(x*) < 0 时，约束非活跃

---

拉格朗日乘子法的扩展

1. 广义拉格朗日（Generalized Lagrangian）

对于同时有不等式和等式约束的问题：

$$L(x,\lambda ,\nu )=f(x)+\sum _i{\lambda }_i{g}_i(x)+\sum _j{\nu }_j{h}_j(x)$$

2. 增广拉格朗日（Augmented Lagrangian）

为改善收敛性：

$$L_A(x,\lambda ,\rho )=f(x)+\sum _i{\lambda }_i{g}_i(x)+\frac{\rho }{2}\sum _i{g}_i(x{)}^2$$

3. 对偶上升法（Dual Ascent）

对于强对偶问题：

$${\lambda }^{k+1}={\lambda }^k+{\alpha }^k\nabla d({\lambda }^k)$$

---

总结

概念	核心要点
凸集	线段上的点仍在集合内
凸函数	弦在函数图像上方
拉格朗日函数	$L=f+\sum {\lambda }_i{g}_i$
对偶函数	$d(\lambda )={\inf }_{x}L(x,\lambda )$
弱对偶	$d^{\star }\le p^{\star }$（总是成立）
强对偶	$d^{\star }=p^{\star }$（Slater条件时成立）
KKT条件	平稳性+可行性+互补松弛

---

参考

Footnotes

1. Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press. ↩