466 lines
11 KiB
Markdown
466 lines
11 KiB
Markdown
## 凸优化
|
||
|
||
### 核心概念
|
||
|
||
#### 凸函数
|
||
|
||
定义：$f(x)$ 是凸函数当且仅当
|
||
$$
|
||
f(\theta x_1 + (1-\theta)x_2) \leq \theta f(x_1) + (1-\theta)f(x_2), \quad \forall x_1,x_2 \in \text{dom}(f), \theta \in [0,1]
|
||
$$
|
||
|
||
示例：$f(x)=x^2$, $f(x)=e^x$
|
||
|
||
**验证 $f(x) = x^2$ 是凸函数：**
|
||
|
||
代入 $f(x) = x^2$：
|
||
$$
|
||
(\theta x_1 + (1-\theta) x_2)^2 \leq \theta x_1^2 + (1-\theta) x_2^2
|
||
$$
|
||
|
||
1. 展开左边：
|
||
$$
|
||
(\theta x_1 + (1-\theta) x_2)^2 = \theta^2 x_1^2 + 2\theta(1-\theta)x_1x_2 + (1-\theta)^2 x_2^2
|
||
$$
|
||
|
||
2. 右边：
|
||
$$
|
||
\theta x_1^2 + (1-\theta) x_2^2
|
||
$$
|
||
|
||
3. 计算差值（右边减左边）：
|
||
$$
|
||
\theta x_1^2 + (1-\theta) x_2^2 - \theta^2 x_1^2 - 2\theta(1-\theta)x_1x_2 - (1-\theta)^2 x_2^2
|
||
$$
|
||
化简：
|
||
$$
|
||
= \theta(1-\theta)x_1^2 + (1-\theta)\theta x_2^2 - 2\theta(1-\theta)x_1x_2
|
||
$$
|
||
|
||
$$
|
||
= \theta(1-\theta)(x_1^2 + x_2^2 - 2x_1x_2)
|
||
$$
|
||
|
||
$$
|
||
= \theta(1-\theta)(x_1 - x_2)^2 \geq 0
|
||
$$
|
||
|
||
4. **结论**：
|
||
|
||
- 因为 $\theta \in [0,1]$，所以 $\theta(1-\theta) \geq 0$，且 $(x_1 - x_2)^2 \geq 0$。
|
||
|
||
- 因此，右边减左边 $\geq 0$，即：
|
||
$$
|
||
(\theta x_1 + (1-\theta) x_2)^2 \leq \theta x_1^2 + (1-\theta) x_2^2
|
||
$$
|
||
|
||
- **$f(x)=x^2$ 满足凸函数的定义**。
|
||
|
||
|
||
|
||
#### 凸集
|
||
|
||
**集合中任意两点的连线仍然完全包含在该集合内**。换句话说，这个集合没有“凹陷”的部分。
|
||
|
||
定义：集合$X$是凸集当且仅当
|
||
$$
|
||
\forall x_1,x_2 \in X, \theta \in [0,1] \Rightarrow \theta x_1 + (1-\theta)x_2 \in X
|
||
$$
|
||
|
||
- 示例：超平面、球体
|
||
|
||
|
||
|
||
### 凸优化问题标准形式
|
||
|
||
$$
|
||
\min_x f(x) \quad \text{s.t.} \quad
|
||
\begin{cases}
|
||
g_i(x) \leq 0 & (凸不等式约束) \\
|
||
h_j(x) = 0 & (线性等式约束) \\
|
||
x \in X & (凸集约束)
|
||
\end{cases}
|
||
$$
|
||
|
||
|
||
|
||
## 交替方向乘子法（ADMM）
|
||
|
||
**Alternating Direction Method of Multipliers (ADMM)** 是一种用于求解大规模优化问题的高效算法，结合了拉格朗日乘子法和分裂方法的优点。
|
||
|
||
### 基本概念
|
||
|
||
- **优化问题分解**
|
||
ADMM 的核心思想是将复杂优化问题分解为多个较简单的子问题，通过引入辅助变量将原问题转化为约束优化问题，使子问题独立求解。
|
||
|
||
- **拉格朗日乘子**
|
||
利用拉格朗日乘子处理约束条件，构造增强拉格朗日函数，确保子问题求解时同时考虑原问题的约束信息。
|
||
|
||
- **交替更新**
|
||
通过交替更新子问题的解和拉格朗日乘子，逐步逼近原问题的最优解。
|
||
|
||
---
|
||
|
||
### 算法流程
|
||
|
||
1. **问题分解**
|
||
将原问题分解为两个子问题。假设原问题表示为：
|
||
$\min_{x, z} f(x) + g(z) \quad \text{s.t.} \quad Ax + Bz = c$
|
||
其中 $f$ 和 $g$ 是凸函数，$A$ 和 $B$ 为给定矩阵。
|
||
|
||
2. **构造增强拉格朗日函数**
|
||
引入拉格朗日乘子 $y$，构造增强拉格朗日函数：
|
||
$L_\rho(x, z, y) = f(x) + g(z) + y^T(Ax+Bz-c) + \frac{\rho}{2}\|Ax+Bz-c\|^2$
|
||
其中 $\rho > 0$ 控制惩罚项的权重。
|
||
|
||
3. **交替更新**
|
||
- **更新 $x$**：固定 $z$ 和 $y$，求解 $\arg\min_x L_\rho(x, z, y)$。
|
||
- **更新 $z$**：固定 $x$ 和 $y$，求解 $\arg\min_z L_\rho(x, z, y)$。
|
||
- **更新乘子 $y$**：按梯度上升方式更新：
|
||
$y := y + \rho(Ax + Bz - c)$
|
||
|
||
4. **迭代求解**
|
||
重复上述步骤，直到原始残差和对偶残差满足收敛条件（如 $\|Ax+Bz-c\| < \epsilon$）。
|
||
|
||
|
||
|
||
### 例子
|
||
|
||
下面给出一个简单的数值例子，展示 ADMM 在求解分解问题时的迭代过程。我们构造如下问题：
|
||
|
||
$$
|
||
\begin{aligned}
|
||
\min_{x, z}\quad & (x-1)^2 + (z-2)^2 \\
|
||
\text{s.t.}\quad & x - z = 0.
|
||
\end{aligned}
|
||
$$
|
||
|
||
**注意**：由于约束要求 $x=z$，实际问题等价于
|
||
$$
|
||
\min_{x} (x-1)^2 + (x-2)^2,
|
||
$$
|
||
|
||
其解析最优解为：
|
||
|
||
$$
|
||
2(x-1)+2(x-2)=4x-6=0\quad\Rightarrow\quad x=1.5,
|
||
$$
|
||
|
||
因此我们希望得到 $x=z=1.5$。
|
||
|
||
|
||
|
||
**构造 ADMM 框架**
|
||
|
||
将问题写成 ADMM 标准形式：
|
||
|
||
- 令
|
||
$$
|
||
f(x)=(x-1)^2,\quad g(z)=(z-2)^2,
|
||
$$
|
||
|
||
- 约束写为
|
||
$$
|
||
x-z=0,
|
||
$$
|
||
即令 $A=1$、$B=-1$、$c=0$。
|
||
|
||
增强拉格朗日函数为
|
||
|
||
$$
|
||
L_\rho(x,z,y)=(x-1)^2+(z-2)^2+y(x-z)+\frac{\rho}{2}(x-z)^2,
|
||
$$
|
||
|
||
其中 $y$ 是拉格朗日乘子，$\rho>0$ 是惩罚参数。为简单起见，我们选取 $\rho=1$。
|
||
|
||
|
||
|
||
**ADMM 的更新公式**
|
||
|
||
针对本问题可以推导出三个更新步骤：
|
||
|
||
$\arg\min_x\; $表示在变量 $x$ 的可行范围内，找到使目标函数 $f(x)$ 最小的 $x$ 的具体值。
|
||
|
||
$k$ 代表当前的迭代次数
|
||
|
||
1. **更新 $x$：**
|
||
|
||
固定 $z$ 和 $y$，求解
|
||
$$
|
||
x^{k+1} = \arg\min_x\; (x-1)^2 + y^k(x-z^k)+\frac{1}{2}(x-z^k)^2.
|
||
$$
|
||
对 $x$ 求导并令其为零：
|
||
$$
|
||
2(x-1) + y^k + (x-z^k)=0 \quad\Rightarrow\quad (2+1)x = 2 + z^k - y^k,
|
||
$$
|
||
得到更新公式：
|
||
$$
|
||
x^{k+1} = \frac{2+z^k-y^k}{3}.
|
||
$$
|
||
|
||
2. **更新 $z$：**
|
||
|
||
固定 $x$ 和 $y$，求解
|
||
$$
|
||
z^{k+1} = \arg\min_z\; (z-2)^2 - y^kz+\frac{1}{2}(x^{k+1}-z)^2.
|
||
$$
|
||
注意：由于 $y(x-z)$ 中关于 $z$ 的部分为 $-y^kz$（常数项 $y^kx$ 可忽略），求导得：
|
||
$$
|
||
2(z-2) - y^k - (x^{k+1}-z)=0 \quad\Rightarrow\quad (2+1)z = 4 + y^k + x^{k+1},
|
||
$$
|
||
得到更新公式：
|
||
$$
|
||
z^{k+1} = \frac{4+y^k+x^{k+1}}{3}.
|
||
$$
|
||
|
||
3. **更新 $y$：**
|
||
|
||
按梯度上升更新乘子：
|
||
$$
|
||
y^{k+1} = y^k + \rho\,(x^{k+1}-z^{k+1}).
|
||
$$
|
||
这里 $\rho=1$，所以
|
||
$$
|
||
y^{k+1} = y^k + \bigl(x^{k+1}-z^{k+1}\bigr).
|
||
$$
|
||
|
||
|
||
|
||
**数值迭代示例**
|
||
|
||
**第 1 次迭代：**
|
||
|
||
- **更新 $x$：**
|
||
|
||
$$
|
||
x^1 = \frac{2+z^0-y^0}{3}=\frac{2+0-0}{3}=\frac{2}{3}\approx0.667.
|
||
$$
|
||
|
||
- **更新 $z$：**
|
||
|
||
$$
|
||
z^1 = \frac{4+y^0+x^1}{3}=\frac{4+0+0.667}{3}\approx\frac{4.667}{3}\approx1.556.
|
||
$$
|
||
|
||
- **更新 $y$：**
|
||
|
||
$$
|
||
y^1 = y^0+(x^1-z^1)=0+(0.667-1.556)\approx-0.889.
|
||
$$
|
||
|
||
---
|
||
|
||
**第 2 次迭代：**
|
||
|
||
- **更新 $x$：**
|
||
|
||
$$
|
||
x^2 = \frac{2+z^1-y^1}{3}=\frac{2+1.556-(-0.889)}{3}=\frac{2+1.556+0.889}{3}\approx\frac{4.445}{3}\approx1.4817.
|
||
$$
|
||
|
||
- **更新 $z$：**
|
||
|
||
$$
|
||
z^2 = \frac{4+y^1+x^2}{3}=\frac{4+(-0.889)+1.4817}{3}=\frac{4-0.889+1.4817}{3}\approx\frac{4.5927}{3}\approx1.5309.
|
||
$$
|
||
|
||
- **更新 $y$：**
|
||
|
||
$$
|
||
y^2 = y^1+(x^2-z^2)\approx -0.889+(1.4817-1.5309)\approx -0.889-0.0492\approx -0.938.
|
||
$$
|
||
|
||
---
|
||
|
||
**第 3 次迭代：**
|
||
|
||
- **更新 $x$：**
|
||
|
||
$$
|
||
x^3 = \frac{2+z^2-y^2}{3}=\frac{2+1.5309-(-0.938)}{3}=\frac{2+1.5309+0.938}{3}\approx\frac{4.4689}{3}\approx1.4896.
|
||
$$
|
||
|
||
- **更新 $z$：**
|
||
|
||
$$
|
||
z^3 = \frac{4+y^2+x^3}{3}=\frac{4+(-0.938)+1.4896}{3}\approx\frac{4.5516}{3}\approx1.5172.
|
||
$$
|
||
|
||
- **更新 $y$：**
|
||
|
||
$$
|
||
y^3 = y^2+(x^3-z^3)\approx -0.938+(1.4896-1.5172)\approx -0.938-0.0276\approx -0.9656.
|
||
$$
|
||
|
||
---
|
||
|
||
从迭代过程可以看出：
|
||
|
||
- $x$ 和 $z$ 的值在不断调整，目标是使两者相等，从而满足约束。
|
||
- 最终随着迭代次数增加，$x$ 和 $z$ 会收敛到约 1.5，同时乘子 $y$ 收敛到 $-1$（这与 KKT 条件相符）。
|
||
|
||
|
||
|
||
### 应用领域
|
||
|
||
- **大规模优化**
|
||
在大数据、机器学习中利用并行计算加速求解。
|
||
- **信号与图像处理**
|
||
用于去噪、压缩感知等稀疏表示问题。
|
||
- **分布式计算**
|
||
在多节点协同场景下求解大规模问题。
|
||
|
||
---
|
||
|
||
### 优点与局限性
|
||
|
||
| **优点** | **局限性** |
|
||
| ------------------ | ---------------------- |
|
||
| 分布式计算能力 | 小规模问题可能收敛较慢 |
|
||
| 支持稀疏性和正则化 | 参数 $\rho$ 需精细调节 |
|
||
| 收敛性稳定 | — |
|
||
|
||
|
||
|
||
## KKT 条件
|
||
|
||
KKT 条件是用于求解约束优化问题的一组必要条件，特别适用于非线性规划问题。当目标函数是非线性的，并且存在约束时，**KKT 条件提供了优化问题的最优解的必要条件**。
|
||
|
||
### 一般形式
|
||
|
||
考虑优化问题：
|
||
$$
|
||
\min_x f(x)
|
||
$$
|
||
约束条件：
|
||
$$
|
||
g_i(x) \leq 0, \quad i = 1, 2, \dots, m
|
||
$$
|
||
|
||
$$
|
||
h_j(x) = 0, \quad j = 1, 2, \dots, p
|
||
$$
|
||
|
||
### KKT 条件
|
||
|
||
**1. 拉格朗日函数**
|
||
|
||
构造拉格朗日函数：
|
||
$$
|
||
\mathcal{L}(x, \lambda, \mu) = f(x) + \sum_{i=1}^m \lambda_i g_i(x) + \sum_{j=1}^p \mu_j h_j(x)
|
||
$$
|
||
其中：
|
||
|
||
- $\lambda_i$ 是不等式约束的拉格朗日乘子
|
||
- $\mu_j$ 是等式约束的拉格朗日乘子
|
||
|
||
**2. 梯度条件（驻点条件）**
|
||
$$
|
||
\nabla_x \mathcal{L}(x, \lambda, \mu) = 0
|
||
$$
|
||
即：
|
||
$$
|
||
\nabla f(x) + \sum_{i=1}^m \lambda_i \nabla g_i(x) + \sum_{j=1}^p \mu_j \nabla h_j(x) = 0
|
||
$$
|
||
|
||
**3. 原始可行性条件**
|
||
$$
|
||
g_i(x) \leq 0, \quad i = 1, 2, \dots, m
|
||
$$
|
||
|
||
$$
|
||
h_j(x) = 0, \quad j = 1, 2, \dots, p
|
||
$$
|
||
|
||
**4. 对偶可行性条件**
|
||
$$
|
||
\lambda_i \geq 0, \quad i = 1, 2, \dots, m
|
||
$$
|
||
|
||
**5. 互补松弛性条件**
|
||
$$
|
||
\lambda_i g_i(x) = 0, \quad i = 1, 2, \dots, m
|
||
$$
|
||
（即：$\lambda_i > 0 \Rightarrow g_i(x) = 0$，或 $g_i(x) < 0 \Rightarrow \lambda_i = 0$）
|
||
|
||
|
||
|
||
### 示例：
|
||
|
||
我们有以下优化问题：
|
||
$$
|
||
\min_x \quad f(x) = x^2 \\
|
||
\text{s.t.} \quad g(x) = x - 1 \leq 0
|
||
$$
|
||
|
||
首先，我们可以直观地理解这个问题：
|
||
|
||
- 目标函数f(x)=x²是一个开口向上的抛物线，无约束时最小值在x=0
|
||
- 约束条件x-1≤0意味着x≤1
|
||
- 所以我们需要在x≤1的范围内找f(x)的最小值
|
||
|
||
显然，无约束最小值x=0已经满足x≤1的约束，因此x=0就是最优解。但让我们看看KKT条件如何形式化地得出这个结论。
|
||
|
||
**1. 构造拉格朗日函数**
|
||
|
||
拉格朗日函数为：
|
||
$$
|
||
\mathcal{L}(x, \lambda) = x^2 + \lambda(x-1), \quad \lambda \geq 0
|
||
$$
|
||
|
||
这里λ是拉格朗日乘子，必须非负（因为是不等式约束）。
|
||
|
||
**2. KKT条件**
|
||
|
||
KKT条件包括：
|
||
|
||
1. 平稳性条件：∇ₓℒ = 0
|
||
2. 原始可行性：g(x) ≤ 0
|
||
3. 对偶可行性：λ ≥ 0
|
||
4. 互补松弛性：λ·g(x) = 0
|
||
|
||
**平稳性条件**
|
||
|
||
对x求导：
|
||
$$
|
||
\frac{\partial \mathcal{L}}{\partial x} = 2x + \lambda = 0 \quad (1)
|
||
$$
|
||
|
||
**互补松弛性**
|
||
$$
|
||
\lambda(x-1) = 0 \quad (2)
|
||
$$
|
||
|
||
这意味着有两种情况：
|
||
|
||
- 情况1：λ=0
|
||
- 情况2：x-1=0（即x=1）
|
||
|
||
##### 情况1：λ=0
|
||
|
||
| **步骤** | **计算过程** | **结果** |
|
||
| ---------- | ------------------------------ | -------- |
|
||
| 平稳性条件 | $2x + 0 = 0 \Rightarrow x = 0$ | $x = 0$ |
|
||
| 原始可行性 | $g(0) = 0 - 1 = -1 \leq 0$ | 满足 |
|
||
| 对偶可行性 | $\lambda = 0 \geq 0$ | 满足 |
|
||
| 互补松弛性 | $0 \cdot (-1) = 0$ | 满足 |
|
||
|
||
##### 情况2：x=1
|
||
|
||
| **步骤** | **计算过程** | **结果** |
|
||
| ---------- | --------------------------------------------- | ---------------------- |
|
||
| 平稳性条件 | $2(1) + \lambda = 0 \Rightarrow \lambda = -2$ | $\lambda = -2$ |
|
||
| 对偶可行性 | $\lambda = -2 \geq 0$ | **不满足**（乘子为负） |
|
||
|
||
**唯一满足所有KKT条件的解是x=0, λ=0。**
|
||
|
||
|
||
|
||
### 总结
|
||
|
||
KKT 条件通过拉格朗日乘子法将约束和目标函数结合，为求解约束优化问题提供了必要的最优性条件。其核心是：
|
||
|
||
1. 拉格朗日函数的梯度为零
|
||
2. 原始约束和对偶约束的可行性
|
||
3. 互补松弛性
|