供应链｜MnSc论文精读：采用 RSOME 轻松实现稳健的随机优化

在数据分析的时代，常用的确定性的数学优化框架，如线性、混合整数和圆锥形优化模型，以及它们对改进管理决策的影响，不能被低估。代数建模包和最先进的优化求解器已经在这些成功的框架上开发出来，以解决各种各样的现实世界中的问题。相比之下，支持不确定性下的通用建模和优化的框架，尽管它们很重要，但相对较少建立。这些框架包括随机线性优化、鲁棒优化，以及最近的分布鲁棒优化；每一种都有其优缺点。

在本文中，我们引入了一种新的分布鲁棒优化模型，我们称为鲁棒随机优化（RSO）。从方法论的角度来看，RSO模型将基于场景的随机线性优化和分布鲁棒优化统一在一个可处理的框架中。具体来说，RSO框架包含了离散和连续的随机变量，并引入了事件静态和事件仿射适应来解决追索权决策的非预期性。

为了获得易于处理的重新表述，我们引入了两种类型的追索权决策，它们是分别用x (s)和y（·, ·）表示的函数映射，这里，x（·）只适应随机场景s的结果，而y（·, ·）适应s和z的结果。函数映射y (s、z）依赖z，如下所示：

为了描述目标函数和约束m∈ [M]，我们首先为所有对象定义以下随机变量映射：

RSO模型将最小化的目标模型为：

随机线性优化和分布鲁棒优化有不同的方法来解决动态决策，其中不确定性是分阶段揭示的，并且在不同阶段做出的追索决策应该不预测不确定性的实现。在分布式鲁棒优化中，这可以通过限制追索决策对已揭示的不确定性z̃子集的依赖性来实现（参见图1中的示例）。

与之形成鲜明对比的是，基于场景树的随机线性优化中的动态建模涉及更多，并且需要枚举从决策范围开始到结束的完整样本路径。在这方面，场景代表样本路径，场景树通常用于展示样本路径和决策。

图 2 展示了具有五个场景的三阶段问题的场景树：根据非预期性，第一阶段决策 w 独立于场景，追索权决策x1（·）满足x1(1) =x1(2)= x1(3)和x1(4)= x1(5)，而追索权决策x2（·）可以根据方案1、2、...、5采取不同的结果。场景树的第二个层次给出了两个MECE事件的集合，{1、2、3}和{4,5}，而第三个层次给出了五个单例MECE事件的集合：{1}、{2}、{3}、{4}和{5}。与较低级别（例如，第三级）相关联的MECE事件的集合嵌套在与较高级别（例如，第二级）相关联的集合中。

受这两种独特方法的启发，作者提出了一种新颖的逐事件追索适应方案，该方案在建模动态决策方面结合了它们的本质：所提出的方案允许追索决策适应事件实现，如在随机线性优化中， 并且仿射适应揭示的不确定性，如分布鲁棒优化。当只有一种场景（即事件）时，逐事件追索适应减少到 Bertsimas 等人的仿射追索适应。

为了正式指定追索决策的逐事件适应 x(··)，我们首先通过场景子集定义事件E ⊆ [S]。然后，场景的划分会引发mutually exclusive and collectively exhaustive (MECE) 事件的集合C。相应地，我们定义一个映射 Hc : [S] 7C 使得 Hc (s) = E，其中E是C中唯一包含场景 s 的事件。给定 MECE 事件的集合 C，我们定义了event-wise static adaptation，这与基于场景树的随机线性优化类似。

请注意，场景树的每一级自然会给出一个场景分区，从而引发一个集合MECE 事件的数量，而这些事件又用于输入与该级别（即阶段）相关的追索决策的事件追索适应；。

类似地，对于追索决策 y(·, ·)，我们定义了event-wise affine adaptation。

对于子集 I ⊆ [I z ]。与分布鲁棒优化一样，在某个阶段采取的追索决策 y(·,·) 的信息集I会跟踪直到该阶段所揭示的不确定性指标，并且 y(·) 仿射自适应于 z驻留在信息集中。连同 MECE 事件的集合 C，信息集捕获了 y(·,·) 的非预期性。

有了event-wise recourse adaptations，我们提出了以下RSO框架：

给定MECE事件的Cxj , j ∈ [Jx]，Cyj , j∈ [Jy]，信息索引集Iyj , j ∈ [Jy]。RSO模型（2）在其表达中包括静态和自适应多阶段问题：当场景中只有一个MECE事件且没有逐事件仿射自适应时它是静态的，否则是动态的；当在多个阶段中实现不确定性并在每次实现不确定性之后做出追索决定时，它跨越两个以上的阶段。

众所周知，仿射追索适应可以扩展到多阶段问题，方法是将追索决策限制为选择性地依赖于在必须做出追索决定时已经实现的不确定参数的子集。当只有一种情况（即 S = 1）且没有软约束（即没有第二组约束）时，RSO 模型（2）将恢复 Bertsimas 等人的一般多阶段问题。

对于给定的场景 s ∈ [S]，RSO 模型中的目标函数和约束是基础决策变量 r(s) ∈ R J r 的双仿射函数。因此，我们可以写

对于参数G m (s)∈R ,J r×I z和hm (s) ∈R。这种关系将使我们能够使用标准鲁棒优化技术将硬约束重新表述为确定性约束系统，用于易处理的受不确定性影响的线性表示 不等式;使用作者开发的代数建模工具箱 RSOME，可以将扩展 RSO 模型重新表述为确定性优化问题。

作者提出了基于事件的模糊集，它可以用以下格式表示：

对于给定的事件 E k , k ∈ [K] 和给定的闭凸集 Z s , s ∈ [S], Q k , k ∈ [K] 和 P ⊆ { p ∈ P R S ++ | s∈[S] p s = 1 } 。随机变量 s̃ 表示一组随机场景，其实现概率可能不确定。对于不同的场景，对随机变量z̃的支持可能不同，在以事件实现为条件的同时，对z̃的期望也可能不同。值得注意的是，我们可以通过解决经典的鲁棒优化问题来有效地确定事件模糊集F上的最坏情况期望。

问题 (4) 的易处理性取决于不确定性集 Zs、s∈[ S]、Q k、k∈[k] 和P。为了实用性，这些集合仅限于易处理的圆锥可表示集合，例如多面体或二阶圆锥可表示集合。通过使用诸如 RSOME 之类的代数建模工具箱，经典的鲁棒优化问题会自动转换为多项式大小的线性或二阶圆锥优化问题，这可以通过 CPLEX、Gurobi 和 MOSEK 等商业求解器来解决。

另外不确定的离散分布的Event-wise模糊集，广义矩模糊集，Wasserstein 模糊集，混合分布模糊集，K-means模糊集等都有在文中展示，且在文中做了一系列的建模示例来展示RSO的框架范围广泛，包含基于场景树的随机线性优化和分布稳健的优化模型。它基于双仿射函数的期望，但它也可以提供文献中已知的某些二次函数类别的最坏情况期望的严格表征。

RSO 模型统一了一类重要的基于场景树的随机线性优化问题和一些已被孤立考虑的分布鲁棒优化模型（基于凸广义矩、混合分布、φ-散度、Wasserstein 度量等。同时RSO 模型也为一些新方法开辟了道路，包括那些受机器学习技术启发的方法。基于这样一个在不确定性下进行通用建模和优化的统一框架，RSOME 等代数建模包将帮助我们探索和评估更多的方法在实践中解决各种受不确定性影响的优化问题。

微信公众号后台回复

加群：加入全球华人OR|AI|DS社区硕博微信学术群

资料：免费获得大量运筹学相关学习资料

人才库：加入运筹精英人才库，获得独家职位推荐

电子书：免费获取平台小编独家创作的优化理论、运筹实践和数据科学电子书，持续更新中ing...

加入我们：加入「运筹OR帷幄」，参与内容创作平台运营

知识星球：加入「运筹OR帷幄」数据算法社区，免费参与每周「领读计划」、「行业inTalk」、「OR会客厅」等直播活动，与数百位签约大V进行在线交流

                    

        

文章须知

文章作者：东南数智港

责任编辑：张琪 马玺渊

微信编辑：疑疑

文章转载自『东南数智港』公众号，原文链接：成果快照 | RSOME使鲁棒随机优化简单

关注我们 

       FOLLOW US