不确定性建模与优化Uncertainty Modeling and Optimization

前言

在处理不确定性问题时，建模与优化是关键。不确定性问题广泛存在于现实生活中，例如客户需求、行程时间、投资回报率等。传统方法包括随机规划（SO）、鲁棒优化（RO）和机会约束（CCP）。SO和CCP基于已知分布的随机变量，但在实际中往往难以获取。RO是近年来发展迅速的技术，放松了对概率分布的要求，提供更具鲁棒性的解，但可能过于保守。不同的建模范式有各自特点，例如SO的Apriori paradigm和reoptimization，RO的经典RO、Distributionally RO、Adaptive/Adjustable RO等。作者专业背景是电子信息，对凸优化和随机过程了解有限，但RO的应用广泛且内容严谨，适合实践。作者的内容着重于理解和应用，涵盖RO在设施选址、投资组合、车辆路径规划等领域的实际案例。作者会尽量详细列出知识来源，并在不确定的内容处进行标注。

1. 随机规划和机会约束简介

1.1 Chance-constraints programming

前文提到，不确定性的建模方法主要是SO，RO，CCP。这里我们先简单了解SO和CCP。对于一个简单的例子问题（1）：

图片

问题（1）是一个常规的线性规划（linear programming，简称LP）问题。在不确定性环境下，其中的参数A，b，c都可能是随机变量。问题就转化为了（2）：

图片

在问题（2）中，原问题的各个参数都由随机变量 ξ 控制。这个问题就已经超出了LP的处理范围。在SO和CCP中，我们通常“假定所有随机变量的分布函数已知”(似乎不是所有随机变量都有给定的分布函数的，这种说法不一定正确)。所以我们可以尝试使用一些随机变量的数字特征描述问题，比如期望：

图片

当然，问题（3）是一个确定性问题。这样估计显然有失偏颇，如前文所说，这种方式无法衡量风险的损失。因此，CCP用一个概率为风险兜底。这个概率也可以理解为概率论的参数估计中的置信度：

图片

问题（4）是一个很典型的机会约束模型。简单来说，他确保了满足约束的概率大于某个给定的下界，这个下界也决定了问题的保守程度。虽然概率 P不一定能转化为LP的形式处理，但我们有时可以进行一些简单的处理，得到确定性约束。文献[1]中关于旅行时间随机的车辆路径规划问题（SVRP）给出了对应的例子，读者可自行参阅。

1.2 Apriori paradigm

参考文献[2]将SO在SVRP中的应用分为Apriori paradigm和reoptimization。前者也被称为stochastic programming with recourse。Apriori将问题改变成两阶段问题：

图片

其中 Q ( x , ξ )代表 x和 ξ实现之后recourse的期望成本。在第一阶段，我们首先根据参数的期望值构造一个解。在第二阶段，如果随机变量的实现值使得该解违背了某些约束，则通过一个给定的recourse修复解，recourse的成本记入总成本。所以，我们可以在求解第一阶段的时候将recourse的期望成本加入成本计算中。

图片

以随机客户需求的VRP问题为例，假设原先路径为{depot,vi2,vi3,…,,vit,depot}，这条路径上所有客户的需求的期望值之和必须小于车辆总容量。但是，如果车辆到达节点vij后发现容量不足，那么车辆会返回depot，装/卸货后，再前往下一个节点。多出的路途 dvij,0+d0,vij+1−dvij,vij+1则作为recourse cost，乘上这种情况发生的概率，记入总成本。这里的recourse可以简单定义为，如果在点i发现剩余容量不够服务点i+1，则返回仓库补货。通过这种方式，Apriori paradigm考虑了失败的风险带来的成本。

Q一般不能直接用线性规划求解。但是，由于Apriori paradigm本身可以看作两阶段问题，因此可以使用处理两阶段问题的线性规划算法。常用的求解方式L-shaped algorithm就是基于branch-and-cut，或者说更类似于Benders decomposition，通过对第一阶段的最优解添加feasibility cut来保证解的可行性，添加optimality cut保证最优性。此外，由于第二阶段成本可以作为期望成本加入第一阶段，因此也可以使用常规非线性的解法，比如启发式算法、branch-and-price。

1.3 Reoptimization

另一种reoptimization的方式则利用了马尔科夫决策过程，动态调整解。在无后效性的马氏过程下，可以通过动态规划（DP）的方式构建模型，然后通过逆向求解的方式求解。计算成本的时候，我们依然使用期望值作为成本。

图片

以上式子给了一个DP公式的例子。这里p项为概率，为DP的cost-to-go函数，代表每个状态下的最优解，g代表当前决策带来的成本， u代表决策， x代表状态。所以，问题的目标值等于，在每一种状态xk下，选择使得期望成本最小的决策 uk时的期望成本。由于reoptimization完全建立在DP和马氏过程的基础上，因此相关求解算法也是离不开这两者。

参考资料：

[1] Xiangyong Li, Peng Tian, Stephen C.H. Leung. Vehicle routing problems with time windows and stochastic travel and service times: Models and algorithm. Int. J. Production Economics.[2] Michel Gendreau, Ola Jabali, Walter Rei. 50th Anniversary Invited Article—Future Research Directions in Stochastic Vehicle Routing. Transportation Science.

2. 传统鲁棒优化求解

前面我们介绍，鲁棒优化有经典的传统RO，Distributionally RO，Adaptive/Adjustable RO，ADRO等。DRO, ARO, ADRO都是对经典RO在某些方面的改进，他们的处理方法都以RO为基础。而RO的求解方法，归根到底，都是基于线性规划中的对偶理论。

2.1 Robust Counterpart

引入如下问题：

图片

这里的A,b,c关于ξ是一种线性关系，可以称为robust linear constrains。为了方便起见，这里的b是一个标量而非向量。对于SO而言，ξ是一个已知分布的随机变量。如果有多个变量，一般还假设iid（独立同分布）。在RO中，我们不知道ξ的分布。但我们假设知道 ξ的取值范围：ξ∈Z。这里的集合 Z被称为不确定集（uncertainty set）。这显然放松了对 ξ的要求。RO需要解有足够的鲁棒性，也就是说解应该在任何情况下都可行、都由目标函数确保有准确的下界。在SO with recourse中，为了保证在某些情况下解的不可行带来的成本，我们在目标函数中添加了Q项。在RO中，我们不添加这样的成本，而是选择让目标函数以下界的形式确保其鲁棒性。我们可以将问题（6）写成如下的鲁棒对应形式（Robust Counterpart, RC）：

图片

首先保证约束条件对所有情况可行，其次目标函数变成一个max-min形式。我们的优化对象变成了目标函数的下界。但是，max-min并不是线性算子。我们将问题转化为上境图（epigraph）形式：

图片

这里的epigraph应该是凸优化中的一个概念。函数f的上境图定义为：

图片

其中dom f 表示f 的定义域。这种形式应该叫epigraph的RC。RO的epigraph应该是不写成不确定集的。在epigraph形式下，RO已经转化为了一个线性形式。但是，很多情况下Z是无限集合，比如连续型随机变量。一般的LP显然无法处理无限个约束的问题。因此，我们用一种称为reformulation的方法将原问题转化为可以求解的LP问题。

2.2 Reformulation

考虑一个简化的例子：

图片

 这里的不确定性只在约束的一次项系数中出现。当目标项有不确定性时，可以通过如上的epigraph转化到约束中；当常数项b中存在不确定性时，可以写成b(ξ)Tx0的形式，固定x0=−1，将其转化到一次项中。此外，我们还用 a + P ξ表示了A(ξ)。这里的P是一个矩阵。这种模型被称为factor model。相比于a+a^ξ的均值+离差形式，这种model能反映出更多的ξ的组成。

图片

如上图所示，factor model可以表示Example 2的情况，而a+a^ξ不可以。详细可以参考文献[2]的讲解。（也是原图出处）第二个约束可以进一步转化为如下形式：

图片

上式第二步加的转置，是为了后续子问题写成“参数的转置*变量”的形式，没有其他意义。由于是标量，所以可以直接加。上一步实际上将约束转化为一个子问题。接下来，接下来我们从最简单的Box uncertainty set开始，展示如何通过对偶进行reformulation。首先介绍Box uncertainty set：

图片

上式展示了Box不确定集的两种写法。其中U一般代表不确定项的取值。这一不确定集由范数描述，在这个不确定集下，对该问题取对偶，得：

图片

图片

将对偶问题带入原问题，得：

图片

这样就转化为了一个可用LP直接求解的问题。在上述步骤中，我们实际上将最初RC中无穷个约束的问题，转化为子问题中的变量。LP本身就可以解决无穷个变量的情况，也就可以解决原问题了。

2.3 Adversarial approach

回到epigraph形式，LP其实也有办法解决无限个约束的情况。这种处理RO的方法被称为adversarial approach。它的核心思想是，从一个有限的不确定集的子集Z′∈Z开始，接触最优解，再判断该解在整个集合Z的环境下是否可行。如果不可行，再将导致不可行的scenario，或者叫ξ的可能的取值，加入到 Z′中。详细介绍见参考文献[1]。这种方法其实类似于branch-and-cut的思想。但总体来说，reformulation依然是更常见的解法。

参考资料：

[1] Bram L. Gorissen, İhsan Yanıkoğlu, Dick den Hertog. A practical guide to robust optimization. Omega.

[2] 章宇,鲁棒优化及其在车辆路径问题中的应用简介。

以上知识仅仅是对不确定建模的入门理论介绍，后续仍然有许多需要延伸的地方，例如不确定集，对偶理论，如何选取不确定参数，ARO的建模与求解，精确解，近似解，DRO的建模与求解，锥线性规划，矩约束，Wasserstein下的DRO，ADRO等等。每一个部分展开都需要很多的知识点，由于篇幅与精力有限，本篇入门级理论讲解暂时先进行到这里，后续若有时间，会继续进行深入讲解。作者水平有限，文中不足之处，还望海涵。

本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请点击举报。