线性可分支持向量机的原理推导【补充知识部分】9-11极小极大化问题 公式解析

时间：2024-10-20 07:11:38

本文是将文章《线性可分支持向量机的原理推导》中的公式单独拿出来做一个详细的解析，便于初学者更好的理解。在主文章中，有一个部分是关于补充拉格朗日对偶性的相关知识，此公式即为这部分里的内容。

公式 9-11 是通过引入拉格朗日乘子法将一个带有约束的优化问题转化为无约束优化问题的关键一步。它通过将原始问题的最小化和对拉格朗日函数的最大化相结合，形成一个新的优化目标。公式 9-11 的表达式如下：
min ⁡ x θ p ( x ) = min ⁡ x max ⁡ α , β L ( x , α , β ) \min_x \theta_p(x) = \min_x \max_{\alpha, \beta} L(x, \alpha, \beta) xmin​θp​(x)=xmin​α,βmax​L(x,α,β)

1. 公式 9-11 的含义

公式 9-11 的核心思想是通过构造拉格朗日函数来处理带有约束条件的优化问题。它表示我们希望找到 x x x 使得拉格朗日函数 L ( x , α , β ) L(x, \alpha, \beta) L(x,α,β) 的最大值最小化。这种双重极值问题（即“最小化最大值”）将原始的带约束优化问题转化为一个无约束优化问题。

具体解释：

  • min ⁡ x \min_x minx​：我们希望找到一个 x x x 来最小化整个优化问题的目标函数。这个目标函数包含了原始的目标函数和约束条件。
  • max ⁡ α , β L ( x , α , β ) \max_{\alpha, \beta} L(x, \alpha, \beta) maxα,β​L(x,α,β)：对于给定的 x x x，我们要对拉格朗日乘子 α \alpha α 和 β \beta β 进行最大化，找到使拉格朗日函数 L ( x , α , β ) L(x, \alpha, \beta) L(x,α,β) 达到最大值的拉格朗日乘子组合。

2. 推导背景

原始问题和拉格朗日函数

我们开始于一个带约束的原始优化问题：
min ⁡ x f ( x ) \min_x f(x) xmin​f(x)

subject to c i ( x ) ≤ 0 , i = 1 , 2 , … , p \text{subject to} \quad c_i(x) \leq 0, \quad i = 1, 2, \dots, p subject toci​(x)≤0,i=1,2,…,p

h j ( x ) = 0 , j = 1 , 2 , … , q h_j(x) = 0, \quad j = 1, 2, \dots, q hj​(x)=0,j=1,2,…,q

该问题中，我们希望最小化目标函数 f ( x ) f(x) f(x)，同时满足一组不等式约束 c i ( x ) ≤ 0 c_i(x) \leq 0 ci​(x)≤0 和等式约束 h j ( x ) = 0 h_j(x) = 0 hj​(x)=0。

为了将这个带约束的优化问题转化为无约束问题，我们引入了拉格朗日乘子 α \alpha α 和 β \beta β，构造了拉格朗日函数 L ( x , α , β ) L(x, \alpha, \beta) L(x,α,β)：
L ( x , α , β ) = f ( x ) + ∑ i = 1 p α i c i ( x ) + ∑ j = 1 q β j h j ( x ) L(x, \alpha, \beta) = f(x) + \sum_{i=1}^{p} \alpha_i c_i(x) + \sum_{j=1}^{q} \beta_j h_j(x) L(x,α,β)=f(x)+i=1∑p​αi​ci​(x)+j=1∑q​βj​hj​(x)

双重极值问题的形成

在公式 9-10 中，我们定义了：
θ p ( x ) = max ⁡ α , β L ( x , α , β ) \theta_p(x) = \max_{\alpha, \beta} L(x, \alpha, \beta) θp​(x)=α,βmax​L(x,α,β)

即在给定 x x x 的情况下，拉格朗日函数相对于 α \alpha α 和 β \beta β 取最大值的结果。公式 9-11 进一步引申：我们希望在找到 α \alpha α 和 β \beta β 的最优组合后，对 x x x 进行最小化。因此，我们得到：
min ⁡ x max ⁡ α , β L ( x , α , β ) \min_x \max_{\alpha, \beta} L(x, \alpha, \beta) xmin​α,βmax​L(x,α,β)

这个公式表示，我们首先对拉格朗日函数中的 α \alpha α 和 β \beta β 进行最大化，然后对 x x x 进行最小化。这就是双重极值问题的形成。

3. 公式 9-11 的意义

公式 9-11 的含义可以总结为：在求解一个带有约束的最小化问题时，我们通过拉格朗日乘子法将约束条件融入到目标函数中。接着，我们先对这些约束施加的惩罚（通过拉格朗日乘子）进行最大化，确保约束的影响被充分考虑；然后，我们再对优化变量 x x x 进行最小化。

为什么先最大化后最小化？
  • 最大化部分：我们希望通过最大化拉格朗日函数来找到拉格朗日乘子的最优值，这样可以确保约束条件的作用被最大化体现。如果约束被违反（例如 c i ( x ) > 0 c_i(x) > 0 ci​(x)>0），拉格朗日乘子会增加惩罚，反之，如果约束被满足（ c i ( x ) ≤ 0 c_i(x) \leq 0 ci​(x)≤0），拉格朗日乘子的影响会减少甚至为零。
  • 最小化部分：在约束的惩罚机制已经确定后，我们再对 x x x 进行最小化，确保目标函数 f ( x ) f(x) f(x) 取得最优值，同时满足约束条件。

4. 拉格朗日对偶问题的初步构造

公式 9-11 是拉格朗日对偶问题的构造过程中的重要一步。在接下来的推导中，我们将进一步通过对拉格朗日函数进行最小化来构造对偶问题。对偶问题通过改变优化变量的顺序（即先对 α , β \alpha, \beta α,β 进行最小化，再对 x x x 进行最大化），为求解带约束的优化问题提供了另一种思路。

5. 公式 9-11 的几何直观

几何上，公式 9-11 可以理解为在一个受约束的空间中寻找最优解。我们首先通过最大化拉格朗日乘子来“扩展”约束的影响范围，确保任何违反约束的情况都能被放大惩罚；然后，在考虑这些约束的影响后，我们再去寻找 x x x 使得目标函数 f ( x ) f(x) f(x) 最小。

6. 总结

  • 公式 9-11 的核心是通过构造一个双重极值问题，将原始的带约束优化问题转化为无约束问题。
  • 我们通过最大化拉格朗日函数中的拉格朗日乘子，确保约束条件的影响被最大化，然后对 x x x 进行最小化，找到最优解。
  • 这个过程为后续的对偶问题构造奠定了基础，通过改变优化变量的顺序，我们可以更高效地求解复杂的约束优化问题。

相关文章