稀疏优化问题

1. 稀疏性的形式化定义

在讨论稀疏优化问题之前，我们必须首先形式化地定义“稀疏性”。

设 $\mathbf{x}\in {\mathbb{R}}^n$ 是一个 $n$ 维的实数向量。 我们通过计算向量中非零分量的个数来量化其稀疏程度。

1.1 ${\ell }_0$ 伪范数（Pseudo-Norm）

稀疏性是通过 ${\ell }_0$ 伪范数来衡量的。

定义 1.1 ( ${\ell }_0$ 伪范数): $\Vert \mathbf{x}{\Vert }_0\triangleq |\{i\in \{1,\dots ,n\}:x_i\ne 0\}|$ 其中 $|\cdot |$ 表示集合的势（cardinality，即元素的数量）。

注: 尽管我们称其为“范数”，但 ${\ell }_0$ 伪范数不满足范数的同次性（homogeneity）公理（即 $\Vert c\mathbf{x}{\Vert }_0\ne |c|\Vert \mathbf{x}{\Vert }_0$ 当 $|c|<1$ 时），因此在严格意义上它不是一个真正的范数，但它是稀疏性度量的事实标准。

当且仅当 $\Vert \mathbf{x}{\Vert }_0\ll n$ 时，我们称向量 $\mathbf{x}$ 是稀疏的。

---

2. 稀疏优化问题的形式化结构

一个稀疏优化问题是指目标在于最小化某个代价函数 $f(\mathbf{x})$，同时要求解向量 $\mathbf{x}$ 具有高度稀疏性的优化问题。

我们主要有两种形式来构造稀疏优化问题：约束形式和正则化形式。

2.1 约束形式 (Constrained Form)

在这种形式中，稀疏性是作为对解空间的一个硬性限制。我们要求解向量的非零分量数量不超过某个预设的上限 $k$。

定义 2.1 (稀疏约束优化): ${\min }_{\mathbf{x}\in {\mathbb{R}}^n}f(\mathbf{x})$ $\text{subject to }\Vert \mathbf{x}{\Vert }_0\le k$ $\text{and }\mathbf{x}\in \mathcal{C}$ 其中 $k$ 是一个远小于 $n$ 的正整数，代表稀疏度要求；$\mathcal{C}$ 代表其他的可行域约束（例如线性或凸约束）。

2.2 正则化形式 (Regularization Form)

在这种形式中，稀疏性是通过向原始目标函数添加一个惩罚项（penalty term）来实现的。我们希望通过最小化这个扩展的目标函数，在拟合数据 $f(\mathbf{x})$ 和保持稀疏性 $\Vert \mathbf{x}{\Vert }_0$ 之间取得平衡。

定义 2.2 (稀疏正则化优化): ${\min }_{\mathbf{x}\in {\mathbb{R}}^n}F(\mathbf{x})=f(\mathbf{x})+\lambda \Vert \mathbf{x}{\Vert }_0$ 其中 $\lambda >0$ 是一个正则化参数，它控制了对稀疏性要求的权重。较大的 $\lambda$ 会强制更稀疏的解。

---

3. 稀疏优化的计算复杂性： ${\ell }_0$ 的非凸性

现在，我们必须面对一个核心理论挑战：使用 ${\ell }_0$ 伪范数定义的稀疏优化问题，在计算上是极其困难的。

3.1 ${\ell }_0$ 函数的性质分析

${\ell }_0$ 伪范数具有以下关键性质，导致优化问题难以求解：

1. 非凸性 (Non-Convexity): 集合 $\{\mathbf{x}:\Vert \mathbf{x}{\Vert }_0\le k\}$ 不是一个凸集。
   • 证明思路: 考虑 ${\mathbb{R}}^2$ 中，设 $k=1$。向量 ${\mathbf{x}}_1=(1,0)$ 和 ${\mathbf{x}}_2=(0,1)$ 都满足 $\Vert \mathbf{x}{\Vert }_0\le 1$。然而，它们的凸组合 ${\mathbf{x}}_{\theta }=\theta {\mathbf{x}}_1+(1-\theta ){\mathbf{x}}_2$ （对于 $0<\theta <1$），例如 $\theta =0.5$， ${\mathbf{x}}_{0.5}=(0.5,0.5)$，其 ${\ell }_0$ 范数 $\Vert {\mathbf{x}}_{0.5}{\Vert }_0=2$。因此，该集合不是凸集。
2. 不连续性 (Discontinuity): ${\ell }_0$ 函数在 $\mathbf{x}=0$ 处是不连续的。这使得传统的基于梯度的优化方法（如梯度下降）无法直接应用。

3.2 结论：NP-Hardness

由于 ${\ell }_0$ 优化问题的非凸、离散性质，求解这类问题通常涉及对所有可能的 $k$ 个非零分量进行组合搜索。在一般情况下，包括在最常见的最小二乘框架下（即 $f(\mathbf{x})=\Vert A\mathbf{x}-\mathbf{b}{\Vert }_2^2$），稀疏优化问题是 NP-hard 的。

---

4. 实践中的解决方案：凸松弛 (${\ell }_1$ 范数)

由于 ${\ell }_0$ 问题的计算难度，在实际应用中，我们必须寻求一个在计算上可处理（即凸的）且在统计上能有效诱导稀疏性的替代度量。这种技术称为凸松弛 (Convex Relaxation)。

4.1 引入 ${\ell }_1$ 范数

${\ell }_1$ 范数是 ${\ell }_0$ 伪范数最常用的凸替代品。

定义 4.1 ( ${\ell }_1$ 范数): $\Vert \mathbf{x}{\Vert }_1\triangleq {\sum }_{i=1}^n|x_i|$

关键性质：

1. 凸性 (Convexity): ${\ell }_1$ 范数是一个标准的凸函数，因此 $\Vert \mathbf{x}{\Vert }_1\le C$ 定义的集合是一个凸集。
2. 诱导稀疏性 (Sparsity Induction): 尽管 ${\ell }_1$ 范数是连续的，但在正则化框架中，它会天然地倾向于产生稀疏解。

4.2 ${\ell }_1$ 诱导稀疏性的几何解释

考虑一个二维优化问题： ${\min }_{\mathbf{x}}f(\mathbf{x})\text{subject to }\Vert \mathbf{x}{\Vert }_p\le t$

• 使用 ${\ell }_2$ 范数 ($\Vert \mathbf{x}{\Vert }_2\le t$): 可行域是一个圆盘。最优解通常发生在目标函数 $f(\mathbf{x})$ 的等高线与圆盘边界光滑相切的点。这些切点极少位于坐标轴上，因此解向量 $\mathbf{x}$ 的两个分量通常都是非零的。
• 使用 ${\ell }_1$ 范数 ($\Vert \mathbf{x}{\Vert }_1\le t$): 可行域是一个菱形（或正方形，在 ${\mathbb{R}}^2$ 中）。这个菱形在坐标轴上具有尖锐的角点（Vertices）。当目标函数 $f(\mathbf{x})$ 的等高线与 ${\ell }_1$ 约束区域相切时，最优解更有可能“抓住”这些尖角。
  • 在尖角处，解向量 $\mathbf{x}$ 的某些分量为零。例如，在 ${\mathbb{R}}^2$ 中，尖角是 $(t,0),(0,t),(-t,0),(0,-t)$。这些解是稀疏的。

4.3 经典的 ${\ell }_1$ 稀疏优化模型：Lasso

将 ${\ell }_1$ 正则化应用于经典的最小二乘问题，产生了稀疏优化的奠基性模型：Lasso (Least Absolute Shrinkage and Selection Operator)。

定义 4.3 (Lasso 模型): 假设我们有观测数据 $\mathbf{b}\in {\mathbb{R}}^m$，设计矩阵 $A\in {\mathbb{R}}^{m\times n}$，我们需要找到系数向量 $\mathbf{x}$。 ${\min }_{\mathbf{x}\in {\mathbb{R}}^n}\frac{1}{2}\Vert A\mathbf{x}-\mathbf{b}{\Vert }_2^2+\lambda \Vert \mathbf{x}{\Vert }_1$ 其中：

• $\frac{1}{2}\Vert A\mathbf{x}-\mathbf{b}{\Vert }_2^2$ 是数据拟合项（一个凸的二次函数）。
• $\Vert \mathbf{x}{\Vert }_1$ 是 ${\ell }_1$ 稀疏性惩罚项。
• $\lambda >0$ 是正则化参数。

由于这个目标函数是严格凸的（二次项凸，${\ell }_1$ 范数凸，凸函数之和仍是凸函数），Lasso 模型具有唯一最优解（或至少唯一最优值），并且可以使用高效的算法（如坐标下降法、近端梯度法 (Proximal Gradient Methods) 等）在多项式时间内求解。

---

总结

稀疏优化问题旨在找到具有最少非零分量的解。

特征	${\ell }_0$ 稀疏优化 (理想)	${\ell }_1$ 稀疏优化 (实践)
形式	$\min f(\mathbf{x})+\lambda \Vert \mathbf{x}{\Vert }_0$	$\min f(\mathbf{x})+\lambda \Vert \mathbf{x}{\Vert }_1$
数学性质	非凸、不连续	凸、连续
计算难度	NP-hard	可在多项式时间内求解
应用	理论基石	压缩感知、高维统计、特征选择