随机规划中的序贯决策与在线凸优化
我将为您系统讲解这个融合了随机规划、序贯决策和在线优化的前沿领域。让我们从基础概念开始，逐步深入其数学原理和算法实现。
1. 基本概念框架
在线凸优化(Online Convex Optimization, OCO) 是一个序贯决策框架，其核心流程如下：
- 在每个时段t=1,2,...,T：
- 决策者从凸集K中选择一个决策x_t
- 环境揭示凸损失函数f_t: K→R
- 决策者遭受损失f_t(x_t)
这里的"在线"特性体现在决策者必须在观察到损失函数之前做出决策，而只能基于历史信息进行优化。
2. 核心性能指标：遗憾(Regret)
遗憾是衡量在线算法性能的关键指标，定义为：
\[R_T = \sum_{t=1}^T f_t(x_t) - \min_{x∈K} \sum_{t=1}^T f_t(x) \]
随机环境下的期望遗憾：
\[E[R_T] = E\left[\sum_{t=1}^T f_t(x_t)\right] - \min_{x∈K} E\left[\sum_{t=1}^T f_t(x)\right] \]
优秀在线算法的目标是实现次线性遗憾，即lim_{T→∞} R_T/T = 0，这意味着平均表现渐近接近最优固定决策。
3. 经典算法：在线梯度下降
在线梯度下降(Online Gradient Descent) 算法：
- 初始化：x_1 ∈ K
- 对于t=1到T：
- 选择决策x_t
- 观察到f_t，计算梯度∇f_t(x_t)
- 更新：y_{t+1} = x_t - η_t ∇f_t(x_t)
- 投影：x_{t+1} = Π_K(y_{t+1})
其中η_t是步长，Π_K是到集合K的欧几里得投影。
4. 随机规划视角的扩展
在随机规划框架下，我们考虑更一般的序贯决策问题：
\[\min_{π} E\left[\sum_{t=1}^T f_t(x_t, ξ_t)\right] \]
满足x_t = π_t(ξ_1,...,ξ_{t-1}) ∈ K_t
其中ξ_t是随机噪声，π是决策策略，K_t是可能随时间变化的可行域。
5. 信息结构与适应性
信息结构的分类：
- 完全信息：决策后观察到完整函数f_t
- Bandit反馈：只观察到损失值f_t(x_t)
- 随机梯度反馈：观察到噪声梯度估计
适应性决策的关键在于利用递增信息流：
\[\mathcal{F}_t = σ(ξ_1,...,ξ_t) \]
决策x_t必须是\(\mathcal{F}_{t-1}\)可测的。
6. 理论保证与收敛性
在适当条件下，在线梯度下降算法能达到：
- 凸函数：O(√T)遗憾界
- 强凸函数：O(log T)遗憾界
- 随机环境：几乎必然收敛到最优解
关键假设：
- 梯度有界：‖∇f_t‖ ≤ G
- 可行集直径有界：D = max_{x,y∈K} ‖x-y‖
- 对于强凸情况，还需要模参数μ > 0
7. 实际应用与变体算法
实际应用场景：
- 在线投资组合选择
- 网络路由优化
- 实时定价决策
- 在线资源调度
重要变体算法：
- 在线镜像下降：使用Bregman散度替代欧几里得距离
- 自适应梯度方法：如AdaGrad，适应问题几何结构
- Bandit凸优化：在有限反馈下的扩展
这个框架将随机规划的建模能力与在线优化的实时决策相结合，为动态环境下的序贯决策问题提供了强大的理论基础和实用算法。