随机规划中的序贯决策与分布式在线次梯度法 基础概念：次梯度法 在非光滑凸优化中，目标函数的梯度不一定处处存在，此时需使用次梯度（subgradient）。次梯度是梯度概念的推广：若函数 \( f \) 在点 \( x \) 处不可微，则存在次梯度集合 \( \partial f(x) \)，满足对任意 \( y \)，有 \( f(y) \geq f(x) + g^T (y-x) \)（其中 \( g \in \partial f(x) \)）。次梯度法的迭代格式为： \[ x_ {k+1} = x_ k - \alpha_ k g_ k, \quad g_ k \in \partial f(x_ k), \] 其中 \( \alpha_ k \) 为步长。与传统梯度法不同，次梯度法在非光滑问题中仍能收敛，但需满足步长条件 \( \sum \alpha_ k = \infty, \sum \alpha_ k^2 < \infty \)。 随机规划中的序贯决策 在动态随机环境中，决策者需依次观测随机变量 \( \xi_ 1, \xi_ 2, \dots \)，并在每步做出决策 \( x_ t \)，目标是最小化长期期望成本： \[ \min \mathbb{E} \left[ \sum_ {t=1}^T f_ t(x_ t, \xi_ t) \right ], \] 其中 \( f_ t \) 可能非光滑。例如，在随机资源分配中，每步需根据实时需求调整资源，且成本函数包含不可微的惩罚项（如资源短缺损失）。 分布式优化框架 假设多个智能体（如传感器网络或分布式计算节点）通过通信网络协作求解全局目标： \[ \min \sum_ {i=1}^n \mathbb{E} [ F_ i(x, \xi_ i) ], \] 其中 \( F_ i \) 是局部函数，仅智能体 \( i \) 能观测到随机数据 \( \xi_ i \)。智能体需在局部计算和邻居通信间平衡，避免中心节点瓶颈。 在线次梯度法的融合 将序贯决策与分布式优化结合，每个智能体在时刻 \( t \) 执行以下步骤： 局部更新 ：根据当前观测 \( \xi_ {i,t} \) 计算次梯度 \( g_ {i,t} \in \partial F_ i(x_ {i,t}, \xi_ {i,t}) \)。 通信协调 ：与邻居交换决策信息，通过共识（consensus）步骤逼近全局最优解： \[ x_ {i,t+1} = \sum_ {j \in N_ i} w_ {ij} x_ {j,t} - \alpha_ t g_ {i,t}, \] 其中 \( w_ {ij} \) 是共识权重矩阵的元素，\( N_ i \) 是邻居集合。 收敛性关键条件 步长设计 ：需满足 \( \alpha_ t = O(1/\sqrt{t}) \) 以平衡探索与利用。 网络连通性 ：共识权重矩阵需双随机（doubly stochastic），且通信图连通。 有界次梯度 ：假设 \( \| g_ {i,t} \| \leq G \)，确保迭代稳定性。 应用场景 该方法适用于分布式机器学习（如联邦学习中的非光滑正则化）、智能电网动态调度（考虑实时电价与需求波动）、多机器人协同路径规划（应对环境随机障碍）等场景，其中问题兼具非光滑性、动态数据流和分布式架构特点。