4.5 约束优化与拉格朗日乘子法：支持向量机的数学基础

4.5 约束优化与拉格朗日乘子法：支持向量机的数学基础

在许多人工智能与机器学习问题中，我们寻找的最优解不仅需要优化某个目标函数，还必须满足一系列附加条件或限制，这类问题被称为约束优化问题。支持向量机作为经典的监督学习模型，其核心数学形式便是一个带不等式约束的凸二次规划问题。理解并求解此类问题的关键数学工具是拉格朗日乘子法及其相关的对偶理论。本节将系统阐述约束优化问题的分类与形式化，深入剖析拉格朗日乘子法的原理与几何直观，并引入求解不等式约束问题的KKT条件，最终阐明这些理论如何为支持向量机构建坚实的数学基础。

4.5.1 约束优化问题：分类与形式化描述

约束优化问题根据约束条件的形式，主要分为两类：

1. 等式约束优化问题：
   min ⁡ x f ( x ) s.t. h i ( x ) = 0 , i = 1 , … , m \begin{aligned} \min_{\mathbf{x}} \quad & f(\mathbf{x}) \\ \text{s.t.} \quad & h_i(\mathbf{x}) = 0, \quad i = 1, \ldots, m \end{aligned}xmin​s.t.​f(x)hi​(x)=0,i=1,…,m​
   其中，x ∈ R n \mathbf{x} \in \mathbb{R}^nx∈Rn是优化变量，f : R n → R f: \mathbb{R}^n \rightarrow \mathbb{R}f:Rn→R是目标函数，h i : R n → R h_i: \mathbb{R}^n \rightarrow \mathbb{R}hi​:Rn→R是等式约束函数。约束集Ω = { x ∣ h i ( x ) = 0 , ∀ i } \Omega = \{\mathbf{x} | h_i(\mathbf{x}) = 0, \forall i\}Ω={x∣hi​(x)=0,∀i}定义了可行域。

2. 不等式约束优化问题（更一般的形式）：
   min ⁡ x f ( x ) s.t. g j ( x ) ≤ 0 , j = 1 , … , p h i ( x ) = 0 , i = 1 , … , m \begin{aligned} \min_{\mathbf{x}} \quad & f(\mathbf{x}) \\ \text{s.t.} \quad & g_j(\mathbf{x}) \le 0, \quad j = 1, \ldots, p \\ & h_i(\mathbf{x}) = 0, \quad i = 1, \ldots, m \end{aligned}xmin​s.t.​f(x)gj​(x)≤0,j=1,…,phi​(x)=0,i=1,…,m​
   其中，g j : R n → R g_j: \mathbb{R}^n \rightarrow \mathbb{R}gj​:Rn→R是不等式约束函数。支持向量机的优化问题即属于此类，其约束确保所有样本被正确分类且满足间隔要求。

求解约束优化问题的核心挑战在于，最优解可能出现在可行域的内部（此时约束不起作用，称为非积极约束），也可能出现在可行域的边界上（此时约束起决定性作用，称为积极约束）。拉格朗日乘子法为系统化地处理这两种情况提供了统一的框架。

4.5.2 拉格朗日乘子法：等式约束情形

对于等式约束问题，拉格朗日乘子法的核心思想是将约束条件融入目标函数，构造一个称为拉格朗日函数的辅助函数。

1. 拉格朗日函数的构造：引入拉格朗日乘子λ i ∈ R \lambda_i \in \mathbb{R}λi​∈R，为每个等式约束h i ( x ) = 0 h_i(\mathbf{x}) = 0hi​(x)=0配备一个。拉格朗日函数定义为：
   L ( x , λ ) = f ( x ) + ∑ i = 1 m λ i h i ( x ) \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}) = f(\mathbf{x}) + \sum_{i=1}^{m} \lambda_i h_i(\mathbf{x})L(x,λ)=f(x)+i=1∑m​λi​hi​(x)
   其中，λ = [ λ 1 , … , λ m ] T \boldsymbol{\lambda} = [\lambda_1, \ldots, \lambda_m]^Tλ=[λ1​,…,λm​]T为乘子向量。

2. 一阶必要条件：在一定的正则性条件下（如约束梯度线性无关，即满足约束品性），若x ∗ \mathbf{x}^*x∗是等式约束优化问题的局部极值点，则存在唯一的拉格朗日乘子向量λ ∗ \boldsymbol{\lambda}^*λ∗，使得( x ∗ , λ ∗ ) (\mathbf{x}^*, \boldsymbol{\lambda}^*)(x∗,λ∗)是拉格朗日函数的平稳点，即满足：
   ∇ x L ( x ∗ , λ ∗ ) = ∇ f ( x ∗ ) + ∑ i = 1 m λ i ∗ ∇ h i ( x ∗ ) = 0 ∇ λ L ( x ∗ , λ ∗ ) = h ( x ∗ ) = 0 \begin{aligned} \nabla_{\mathbf{x}} \mathcal{L}(\mathbf{x}^*, \boldsymbol{\lambda}^*) &= \nabla f(\mathbf{x}^*) + \sum_{i=1}^{m} \lambda_i^* \nabla h_i(\mathbf{x}^*) = \mathbf{0} \\ \nabla_{\boldsymbol{\lambda}} \mathcal{L}(\mathbf{x}^*, \boldsymbol{\lambda}^*) &= \mathbf{h}(\mathbf{x}^*) = \mathbf{0} \end{aligned}∇x​L(x∗,λ∗)∇λ​L(x∗,λ∗)​=∇f(x∗)+i=1∑m​λi∗​∇hi​(x∗)=0