📚 课程目录第2章凸优化基础

凸优化基础：凸集、凸函数与KKT条件

说实话，很多人一听到“凸优化”就觉得头大。我当年刚接触时也一样，觉得这玩意儿太数学了。但后来在实际项目中碰了几次壁，才明白这东西有多重要。

你想想看，我们做全局优化，最怕什么？最怕掉进局部最优的坑里出不来。而凸优化，恰恰能保证你找到的就是全局最优。这就是它的魅力所在。

凸集：一个“不凹”的集合

凸集的定义其实很直观：集合里任意两点连成的线段，整条线段都在集合内部。

用数学语言说：对于集合 \(C\)，如果任意 \(x_1, x_2 \in C\) 和任意 \(\theta \in [0,1]\)，都有 \(\theta x_1 + (1-\theta)x_2 \in C\)，那么 \(C\) 就是凸集。

我习惯这么记：凸集就是“不会凹进去”的集合。比如一个圆盘是凸的，但一个甜甜圈就不是——你从内圈和外圈各取一点，连线会穿过中间的空洞。

  常见凸集举例：
  整个 \(\mathbb{R}^n\) 空间
超平面 \(\{x | a^T x = b\}\)
半空间 \(\{x | a^T x \leq b\}\)
多面体（多个半空间的交集）
欧几里得球 \(\{x | \|x - x_0\|_2 \leq r\}\)

我在做资源分配项目时，经常用多面体来表示可行域。每个约束对应一个半空间，它们的交集就是所有可行解。嗯，这里要注意：凸集的交集还是凸集，但并集不一定。

凸函数：碗状的“好函数”

凸函数的定义也不复杂：函数图像上任意两点连成的弦，都在函数图像的上方。

数学上：函数 \(f\) 是凸的，当且仅当对任意 \(x_1, x_2\) 和 \(\theta \in [0,1]\)，有：

\[ f(\theta x_1 + (1-\theta)x_2) \leq \theta f(x_1) + (1-\theta) f(x_2) \]

说白了，就是函数长得像个碗。我刚开始学的时候，总把凸函数和凹函数搞混。后来一个老工程师告诉我：“凸函数就是碗口朝上的函数”，一下就记住了。

判断凸函数的实用方法：

一阶条件：\(f(y) \geq f(x) + \nabla f(x)^T (y - x)\)（切线在函数下方）
二阶条件：Hessian 矩阵半正定（\(\nabla^2 f(x) \succeq 0\)）
常见凸函数：\(x^2\)、\(e^x\)、\(-\log x\)、范数

我曾经在信号处理项目中，需要最小化一个非凸函数。折腾了好久都找不到全局最优。后来换了个思路，把问题重新建模成凸优化，一下子就解决了。所以，能用凸函数就别用非凸的，这是血的教训。

凸优化问题的标准形式

一个优化问题要成为凸优化，得满足三个条件：

目标函数是凸函数（最小化）
不等式约束是凸函数（\(f_i(x) \leq 0\)）
等式约束是仿射函数（\(h_i(x) = a_i^T x - b_i = 0\)）

标准形式长这样：

minimize    f₀(x)
subject to  fᵢ(x) ≤ 0,  i = 1,...,m
            hⱼ(x) = 0,  j = 1,...,p

其中 \(f_0, f_1, ..., f_m\) 都是凸函数，\(h_1, ..., h_p\) 是仿射函数。

注意：不是所有看起来“凸”的问题都是凸优化。比如最大化一个凸函数，或者约束里有非凸函数，都不算。我见过有人把最大化 \(x^2\) 当成凸优化来做，结果算法直接发散。

为什么凸优化这么重要？因为凸优化的局部最优就是全局最优。这意味着你不用担心算法卡在某个山头上出不来。而且，凸优化有非常高效的求解算法，比如内点法，可以处理上万维的问题。

拉格朗日对偶性：换个角度看问题

有时候，原问题不好解，但它的对偶问题却很好解。这就是拉格朗日对偶性的价值。

对于原问题：

minimize    f₀(x)
subject to  fᵢ(x) ≤ 0,  i = 1,...,m
            hⱼ(x) = 0,  j = 1,...,p

我们构造拉格朗日函数：

\[ L(x, \lambda, \nu) = f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{j=1}^p \nu_j h_j(x) \]

其中 \(\lambda_i \geq 0\) 是拉格朗日乘子。然后定义对偶函数：

\[ g(\lambda, \nu) = \inf_x L(x, \lambda, \nu) \]

对偶问题就是最大化这个对偶函数：

maximize    g(λ, ν)
subject to  λ ≥ 0

  弱对偶性：对偶问题的最优值 ≤ 原问题的最优值

  强对偶性：对偶问题的最优值 = 原问题的最优值（在 Slater 条件下成立）

我习惯把对偶理解成“从另一个维度看问题”。原问题是从变量 \(x\) 的角度出发，对偶问题是从约束的“价格”出发。有时候，对偶问题比原问题简单得多。比如在 SVM 中，原问题是二次规划，对偶问题也是二次规划，但对偶问题能自然地引入核函数。

KKT条件：最优解的“身份证”

KKT条件（Karush–Kuhn–Tucker条件）是判断一个点是否为最优解的充要条件（对于凸优化且满足约束规格的情况）。

假设原问题满足强对偶性，且 \(x^*\) 和 \((\lambda^*, \nu^*)\) 分别是原问题和对偶问题的最优解，那么它们必须满足：

条件	表达式	说明
原始可行	\(f_i(x^) \leq 0, \; h_j(x^) = 0\)	\(x^*\) 必须在可行域内
对偶可行	\(\lambda_i^* \geq 0\)	乘子非负
互补松弛	\(\lambda_i^* f_i(x^*) = 0\)	要么约束起作用，要么乘子为0
梯度为零	\(\nabla f_0(x^) + \sum \lambda_i^ \nabla f_i(x^) + \sum \nu_j^ \nabla h_j(x^*) = 0\)	拉格朗日函数梯度为0

KKT条件说白了就是：在最优解处，目标函数的梯度必须能被约束函数的梯度线性表示。互补松弛条件则告诉我们：不起作用的约束，对应的乘子一定是0。

我的经验：在实际项目中，我经常用 KKT 条件来验证算法是否收敛。如果解不满足 KKT 条件，那肯定不是最优解。另外，很多经典算法（如 SMO 算法）本质上就是在求解 KKT 条件。

知识结构总览

下面这张图把本章的核心概念串起来了：

一个简单的例子

来看个具体的。假设我们要最小化：

minimize    x² + y²
subject to  x + y ≥ 2

首先，目标函数 \(x^2 + y^2\) 是凸函数（Hessian 是单位矩阵，正定）。约束 \(x + y \geq 2\) 可以写成 \(-x - y \leq 0\)，也是凸函数。所以这是个凸优化问题。

构造拉格朗日函数：

\[ L(x, y, \lambda) = x^2 + y^2 + \lambda(-x - y + 2), \quad \lambda \geq 0 \]

对 \(x, y\) 求偏导并令为0：

\[ \frac{\partial L}{\partial x} = 2x - \lambda = 0 \Rightarrow x = \frac{\lambda}{2} \] \[ \frac{\partial L}{\partial y} = 2y - \lambda = 0 \Rightarrow y = \frac{\lambda}{2} \]

代入约束：\(x + y = \lambda \geq 2\)，所以 \(\lambda^* = 2\)，\(x^* = y^* = 1\)。

检查 KKT 条件：原始可行（\(1+1=2\)），对偶可行（\(\lambda=2 \geq 0\)），互补松弛（\(\lambda( -x - y + 2) = 2 \times 0 = 0\)），梯度为零（已满足）。完美！

  结论：最优解是 \((1, 1)\)，最优值是 \(2\)。而且因为问题是凸的，这就是全局最优。

你看，有了凸优化这套工具，求解过程清晰又可靠。我在实际项目中，遇到优化问题第一件事就是判断它是不是凸的。如果是，那就放心用现成的求解器；如果不是，就得想办法近似或者转换。