随机规划中的序贯决策与分布式随机拟梯度法
1. 基础概念引入
随机规划中的序贯决策是指决策者需根据逐步揭示的随机信息（如市场需求、资源价格等）分阶段调整策略。例如，在多阶段库存管理中，每个阶段需根据当前库存和随机需求决定补货量。分布式随机拟梯度法则是一种在分布式计算环境下求解此类问题的方法，其核心思想是将问题分解到多个计算节点并行处理，每个节点基于局部信息计算拟梯度（一种梯度的近似），并通过协调机制更新全局解。
2. 序贯决策的数学建模
假设一个多阶段随机规划问题形式为：
\[\min_{x_1,\dots,x_T} \mathbb{E}\left[\sum_{t=1}^T f_t(x_t, \xi_t) \right] \quad \text{s.t.} \quad x_t \in \mathcal{X}_t(x_{t-1}, \xi_t) \]
其中：
- \(x_t\) 是第 \(t\) 阶段的决策变量，依赖于前一阶段决策 \(x_{t-1}\) 和当前随机参数 \(\xi_t\)（如随机需求）；
- \(f_t\) 是阶段 \(t\) 的成本函数；
- \(\mathcal{X}_t\) 是决策约束集（如库存容量限制）。
序贯决策要求每个阶段 \(t\) 的决策 \(x_t\) 仅依赖于已观测到的随机实现 \(\xi_1,\dots,\xi_t\)（非预期策略）。
3. 分布式计算的挑战与分解思路
当问题规模庞大（如供应链网络涉及多个地域仓库）时，集中式求解计算成本高。分布式方法将问题按子系统（如每个仓库）分解：
- 每个子系统 \(i\) 维护局部决策变量 \(x_t^i\)，目标函数分解为 \(\sum_i f_t^i(x_t^i, \xi_t)\)；
- 子系统间存在耦合约束（如总资源限制 \(\sum_i x_t^i \leq C_t\)）。
通过拉格朗日松弛或对偶分解，将耦合约束转化为惩罚项，使各子系统可并行求解局部问题。
4. 随机拟梯度法的核心思想
拟梯度是真实梯度的无偏或渐近无偏估计。在随机环境中，直接计算梯度 \(\nabla f_t(x_t, \xi_t)\) 不可行（因 \(\xi_t\) 分布未知），需通过随机样本估计。例如，在阶段 \(t\)，采样一个随机场景 \(\xi_t^k\)，计算拟梯度：
\[g_t^k = \nabla f_t(x_t^k, \xi_t^k) + \text{误差修正项} \]
其中误差修正项可能包含对偶变量或历史梯度信息，以减小方差。
5. 分布式随机拟梯度法的算法步骤
以对偶分解为例：
- 初始化：全局协调器设置拉格朗日乘子 \(\lambda_0\)，各子系统初始化决策 \(x_0^i\)。
- 并行局部更新（第 \(k\) 轮迭代）：
- 每个子系统 \(i\) 根据当前乘子 \(\lambda_k\) 和局部随机样本 \(\xi_t^{i,k}\)，计算拟梯度 \(g_k^i\)，更新局部决策：
\[ x_{k+1}^i = \Pi_{\mathcal{X}^i} \left(x_k^i - \eta_k g_k^i \right) \]
其中 \(\Pi\) 是投影算子，\(\eta_k\) 为步长。
3. 全局协调：
- 协调器收集所有子系统的决策 \(x_{k+1}^i\)，更新乘子以处理耦合约束：
\[ \lambda_{k+1} = \lambda_k + \alpha_k \left( \sum_i x_{k+1}^i - C_t \right) \]
其中 \(\alpha_k\) 为协调步长。
4. 迭代至收敛：步长需满足 \(\sum \eta_k = \infty, \sum \eta_k^2 < \infty\)（如 \(\eta_k = 1/k\)），保证算法渐近收敛。
6. 关键技术与理论保证
- 方差缩减：通过动态采样或梯度聚合（如SAGA、SVRG技术）降低拟梯度的随机误差；
- 通信效率：采用异步更新或压缩通信（如量化梯度）减少节点间数据传输；
- 收敛性：在目标函数凸且步长适当时，算法几乎必然收敛到全局最优；对于非凸问题，可证明收敛到局部最优或驻点。
7. 实际应用示例
在分布式能源调度中，每个风电场需根据局部风速（随机变量）决定发电量，同时满足电网总负荷需求（耦合约束）。各风电场并行计算发电计划，中央调度器根据拟梯度更新电价信号（对偶变量），实现动态协调。