基于线性规划的交替方向乘子法求解示例
问题描述
考虑一个分布式优化问题：有两个智能体需要协同最小化一个总成本函数，但各自有私有约束。目标函数可分解为两个局部函数之和，且决策变量通过线性等式耦合。数学模型如下：
minimize \(f_1(x_1) + f_2(x_2)\)
subject to:
\(A_1 x_1 + A_2 x_2 = b\)
\(x_1 \in \mathcal{X}_1, x_2 \in \mathcal{X}_2\)
其中，\(f_1\) 和 \(f_2\) 是凸函数（本例中为线性函数），\(\mathcal{X}_1\) 和 \(\mathcal{X}_2\) 是凸集（如多面体）。耦合约束 \(A_1 x_1 + A_2 x_2 = b\) 要求两个智能体的决策在全局层面保持一致。
解题过程
- 问题重构
- 引入拉格朗日乘子 \(\lambda\) 对耦合约束进行松弛，得到增广拉格朗日函数：
\[ L_\rho(x_1, x_2, \lambda) = f_1(x_1) + f_2(x_2) + \lambda^\top (A_1 x_1 + A_2 x_2 - b) + \frac{\rho}{2} \|A_1 x_1 + A_2 x_2 - b\|^2 \]
其中 $ \rho > 0 $ 为惩罚参数，用于增强收敛性。
- ADMM迭代步骤
- 初始化：选择初始乘子 \(\lambda^0\)、参数 \(\rho > 0\)，设定容忍误差 \(\epsilon\)。
- 迭代更新（第 \(k\) 步）：
- 更新 \(x_1\)：
\[ x_1^{k+1} = \arg\min_{x_1 \in \mathcal{X}_1} \left[ f_1(x_1) + \lambda^k^\top A_1 x_1 + \frac{\rho}{2} \|A_1 x_1 + A_2 x_2^k - b\|^2 \right] \]
此步骤仅依赖 $ x_2^k $ 和 $ \lambda^k $，可并行或顺序求解。
2. **更新 $ x_2 $**：
\[ x_2^{k+1} = \arg\min_{x_2 \in \mathcal{X}_2} \left[ f_2(x_2) + \lambda^k^\top A_2 x_2 + \frac{\rho}{2} \|A_1 x_1^{k+1} + A_2 x_2 - b\|^2 \right] \]
利用最新 $ x_1^{k+1} $ 更新 $ x_2 $。
3. **更新乘子 $ \lambda $**：
\[ \lambda^{k+1} = \lambda^k + \rho (A_1 x_1^{k+1} + A_2 x_2^{k+1} - b) \]
通过残差调整乘子，推动解趋向可行域。
- 收敛判断
- 检查原始残差 \(r^k = A_1 x_1^k + A_2 x_2^k - b\) 和对偶残差 \(s^k = \rho A_1^\top A_2 (x_2^k - x_2^{k-1})\) 的范数：
\[ \|r^k\| \leq \epsilon \quad \text{且} \quad \|s^k\| \leq \epsilon \]
若满足，则终止迭代；否则返回步骤2。
示例演示
设具体问题：
- \(f_1(x_1) = x_1, f_2(x_2) = 2x_2\)
- \(\mathcal{X}_1 = \{x_1 \geq 0\}, \mathcal{X}_2 = \{x_2 \geq 0\}\)
- 耦合约束：\(x_1 + x_2 = 5\)
ADMM求解：
- 增广拉格朗日函数：
\[ L_\rho = x_1 + 2x_2 + \lambda(x_1 + x_2 - 5) + \frac{\rho}{2}(x_1 + x_2 - 5)^2 \]
- 迭代（取 \(\rho=1, \lambda^0=0, \epsilon=10^{-3}\)）：
- 第1步：更新 \(x_1\)
\[ x_1^1 = \arg\min_{x_1 \geq 0} \left[ x_1 + 0 \cdot x_1 + \frac{1}{2}(x_1 + 0 - 5)^2 \right] \]
求导得 $ 1 + (x_1 - 5) = 0 \Rightarrow x_1^1 = 4 $
- 第2步：更新 \(x_2\)
\[ x_2^1 = \arg\min_{x_2 \geq 0} \left[ 2x_2 + 0 \cdot x_2 + \frac{1}{2}(4 + x_2 - 5)^2 \right] \]
求导得 $ 2 + (x_2 - 1) = 0 \Rightarrow x_2^1 = -1 $，投影到非负域得 $ x_2^1 = 0 $
- 第3步：更新 \(\lambda\)
\[ \lambda^1 = 0 + 1 \cdot (4 + 0 - 5) = -1 \]
- 残差 \(|r^1| = |4+0-5| = 1 > \epsilon\)，继续迭代。
经多轮迭代后，解收敛至 \(x_1^*=3, x_2^*=2\)，满足约束且成本最小（总成本=7）。
关键点
- ADMM通过分解协调实现分布式优化，适合大规模问题。
- 乘子更新步长由 \(\rho\) 控制，影响收敛速度。
- 实际应用中需调节 \(\rho\) 并可能使用自适应策略。