两阶段随机优化（Matlab实现）

目录

1 概述

2 单级随机优化算法

2.1 随机化-最小化

2.2 随机逐次凸近似 （SCA）

3 两级随机优化算法

3.1 批处理算法

3.2 在线算法

4 Matlab代码实现

1 概述

在与随机系统状态向量关联的两阶段随机优化问题中，优化变量分为两组。长期变量适应随机状态的分布/统计，随机状态以较慢的时间尺度变化。短期变量适应系统状态的实现，系统状态以更快的时间尺度变化。因此，两阶段随机优化问题可以分解为一系列短期（第二阶段）子问题和长期（第一阶段）主问题。长期主问题的目标函数包含期望算子 w.r.t. 随机系统状态， 期望算子的论证涉及短期子问题的最优解.基于长期主问题/短期子问题的结构，我们可以将两阶段随机优化问题分为几类。具体而言，在两阶段随机线性规划（LP）/凸问题中，长期主问题和短期子问题都属于LP/凸问题，而在两阶段非凸优化问题中，长期主问题或短期子问题都是非凸的。

两阶段随机优化在各种关键应用领域中发挥着关键作用，例如无线资源优化、金融工程和风险管理、交通网络设计、机器学习等。然而，它仍然远未成熟，缺乏高效和通用的两阶段随机优化算法，如下所述。

---

2 单级随机优化算法

由于许多算法用于求解单级随机优化1 可以扩展为求解两阶段随机优化问题，我们首先回顾一下求解单级问题的常用算法。单阶段随机非凸优化有三种主要的现有方法。

基于随机梯度的方法：随机梯度/次梯度 是解决随机优化问题的常用方法。在每次迭代中，获得目标函数梯度的无偏估计，并执行梯度样更新。在某些技术条件下，几乎可以肯定可以建立与静止点的收敛。随机梯度法的变体已经提出。例如，提出了一种梯度平均方法，其中每次迭代时更新的梯度投影基于当前和过去梯度样本的平均值。此外，还有一些算法在梯度和迭代（优化变量）中均值。

2.1 随机化-最小化

随机正数最小化 （MM）是众所周知的 MM 方法的随机对应物。具体而言，在每次迭代中，首先获得一个示例代理函数作为示例目标函数的上限。然后通过最小化平均代理项函数来获得更新的优化变量。直观地说，平均代理函数倾向于收敛到目标函数的确定性上限，该上限与目标函数的值及其导数在极限点匹配，从中可以证明算法的任何极限点都是静止点。

2.2 随机逐次凸近似 （SCA）

SCA 与MM相似，因为它也迭代最小化了代理函数序列。但是，代理项函数上的条件是不同的。SCA 要求代理函数是凸的，但不一定是目标函数的上限。 针对多智能体网络中的非凸随机和效用优化问题， 提出了一种随机并行SCA方法.在中，提出了一种约束随机SCA（CSSCA）算法来查找一般单级随机优化问题的稳态点，其目标函数和约束函数都是非凸的。

---

3 两级随机优化算法

现有的两阶段随机优化算法可以分为两类：批量算法和在线算法。迭代时t，批处理算法使用所有可用的t系统状态的样本以更新长期变量，需要求解 t短期子问题。另一方面，在线算法仅使用系统状态的当前样本来更新长期变量，并且在每次迭代时解决一个短期子问题。因此，在线算法比批处理算法更受欢迎，因为它的内存要求和复杂性较低。

3.1 批处理算法

大多数两阶段随机优化算法属于批处理算法。一种广泛使用的批处理算法是随机切割平面算法（SCPA），它仅适用于两阶段随机凸问题，在一些文献中，提出了一种近似随机切割平面算法（ASCPA），为一类具有分段线性目标函数的两阶段随机非凸优化问题找到次最优解。在[2]中，提出了一种批量交替优化（AO）算法来寻找两阶段随机非凸优化问题的静止点。上述所有批处理算法都需要在每次迭代时求解大量短期子问题，如果短期问题没有闭合形式的解决方案，其复杂性可能会变得不可接受。

3.2 在线算法

只有少数在线算法可用于两阶段随机优化。在某些情况下，当短期子问题为凸时，可以从凸优化中的扰动和灵敏度分析中获得长期主问题的目标函数的梯度/次梯度。在这种情况下，可以使用简单的随机梯度/顺层算法来解决长期主问题。然而，已知随机梯度/次梯度算法具有较慢的收敛速度。对于极端情况，当短期子问题具有闭合形式解时，我们可以将长期主问题转换为单阶段随机优化问题，并应用各种单阶段在线算法来解决长期主问题。

4 Matlab代码实现