EM算法与经济学中的随机控制

2022-5-26 22:43:33

EM算法与随机控制不经济性*彭显华+徐兴波2016年11月6日摘要概括了广泛用于计算最大似然估计的经典EM算法的思想，我们提出了一种用于解决多周期有限时间随机控制问题的EM控制（EM-C）算法。新算法在每个时间段内通过蒙特卡罗模拟以前后向的方式依次更新控制策略；换言之，该算法在每次迭代中向前模拟，向后优化。与EM算法类似，EM-C算法在每次迭代中都具有性能改善的单调性，因此具有良好的收敛性。我们通过解决易逝性资产垄断定价中的随机控制问题和实际经济周期的研究，证明了该算法的有效性。关键词：EM算法、随机控制、递归模型、动态规划、垄断定价、实际经济周期、数值方法、随机逼近JEL分类：C44、C61、C63、D4、E3*新加坡国立大学风险管理学院和数学系，新加坡恒梅坑台21号。电子邮件：matsteve@nus.edu.sg.+香港九龙清水湾香港科技大学数学系。电子邮件：maxhpeng@ust。香港美国纽约哥伦比亚大学工业工程与运营研究系，邮编：10027。电子邮件：xx2126@columbia.edu.1引言1.1动机和主要结果随机控制问题广泛应用于宏观经济学（例如，真实商业周期的研究）、微观经济学（例如，效用最大化问题）和市场营销（例如，易腐资产的垄断定价）。这些控制问题可能是有限的时间范围。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-26 22:43:37

然而，由于最优控制策略不一定是静态的，因此有限时间随机控制问题比相关的有限时间随机控制问题更困难。通常必须借助数值方法来找到此类有限时间随机控制问题的解。由于维数的原因，通常很难用数值方法解决此类问题，尤其是在高维和复杂的随机动力学中。为了克服这些困难，在本文中，我们试图通过蒙特卡罗模拟来解决实时ho-RizontoCastic控制问题。更准确地说，我们提出了一种新的算法，EM控制（EM-C）算法，该算法使用蒙特卡罗模拟以向前向后的方式在每个时间段内顺序更新控制策略；换言之，在每次迭代中，算法在模拟中向前，在优化中向后。我们通过解决易逝性资产垄断定价和实际经济周期研究中的随机控制问题，证明了该算法的有效性。我们的算法源自不同领域的一种算法，即经典的期望最大化（EM）算法（Dempster、Laird和Rubin（1977）），该算法广泛用于计算缺失数据或潜在变量的最大似然估计（MLE）。在每次迭代中，EM算法首先根据前一次迭代的参数计算缺失数据的条件分布，然后根据刚更新的条件分布最大化全似然函数的期望值，以获得更新的参数。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-26 22:43:40

有趣的是，EM算法可以看作是一种在每次迭代中交替最大化一个具有一个分布参数和一个序数参数的目标函数的算法：分布参数是丢失数据的条件分布，普通参数是原始MLE问题的参数；参见第2.1节。我们的EM-C算法推广了EM算法的思想，用于解决多周期有限时间范围的随机控制问题，其中每个时间段都有对应的控制策略。EM-C算法是一种迭代算法，它在每一步操作中更新对应于一个时间段的一个控制策略。EM-C算法继承了EM算法的精神，通过优化仅在该时间段内与控制策略相关的目标函数，在给定时间段内更新控制策略，并且在算法迭代过程中，所有其他时间段的控制策略都固定在最新状态。新的EM-C算法与现有算法的区别在于四个方面：（i）与EM算法类似，所提出的EM-C算法在每次迭代时都具有性能改进的单调性，这使得EM-C算法具有良好的收敛性。（ii）EM-C算法不假设状态演化的特定动力学（即不限于随机过程的特定设置），正如EM算法可以应用于广泛的概率分布一样。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-26 22:43:43

（iii）EM-C算法不使用Bellman方程；相反，文献中的许多数值算法依赖于Bellman方程或其近似。（iv）与许多现有算法不同，EM-C算法处理有限时间范围的随机控制问题，其中最优策略不一定是平稳的。1.2文献综述由于EM算法是统计学中被引用最多的算法之一，因此该算法有许多扩展；例如，参见Wei和Tanner（1990年）、Meng和Rubin（1993年）、Gu和Li（1998年）以及Lange（2010年，第13章）中的评论。EM算法允许一般分布假设，并具有单调收敛的优点（Wu（1983））。经济学中有大量关于随机控制的文献。Hansen和Sargent（2013）详细讨论了可以解析求解Bellman方程的随机控制问题。Ljungqvist和Sargent（2013）讨论了动态规划方法及其对经济学中各种问题的应用。Judd（1998）、Miranda和Fackler（2002）提供了解决经济学中随机控制问题的递归方法的综合处理。Stokey、Lucas和Prescott（1989）描述了许多建模理论的例子。这里有一些Bellman方程可能不适用的随机控制问题。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-26 22:43:46

例如，当一般控制问题（6）中的效用函数不可时间分离时，则此类问题可能没有Bellman方程。使用动态规划和其他递归方法的经济学问题，包括最优经济增长、资源提取、委托代理问题、公共财政、企业投资、资产定价、要素供应和产业组织。Flemming和Soner（2005）深入讨论了连续时间随机控制问题及其应用。Kushner和Dupuis（2001）对利用马尔可夫链解决连续时间随机控制问题的数值方法进行了极好的综述。对于数学金融中连续时间随机控制问题的数值解也有很多研究；参见，例如，Zhang（2004年）、Bouchard和Touzi（2004年）、Crisan、Manolarakis和Touzi（2010年）、Fahim、Touzi和Warin（2011年）、Kharro ubi、Langreneé和Pham（2013a）、Kharroubi、Langreneé和Pham（2013b）以及Guo、Zhang和Zhuo（2012年），等等。这些研究大多集中于特定的随机过程，例如离散化扩散过程或Lévy过程，但我们的EM-C算法可以应用于一般的随机过程。此外，我们的方法是一种基于仿真的方法，适用于高维问题。近似动态规划（ADP）已被开发用于处理三个维度诅咒的来源：高维状态空间、控制策略空间和随机冲击空间；参见鲍威尔（2011）和贝特塞卡斯（2012）的著作。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

点击查看更多内容…

2022-5-26 22:43:49

ADP算法可以大致分为两类：价值迭代和策略迭代。大多数ADP算法都是数值迭代算法，它采用Bellman方程来近似值函数。当值函数可以很好地逼近时，这些算法是有效的，但否则就不能保证值函数改进的单调性。作为替代，策略迭代算法会跟踪策略，而不是值函数。在每个周期，基于先前估计的策略计算值函数，然后在策略空间内进行改进。值迭代和策略迭代ADP算法可能不会对每次迭代的值函数进行单调改进。ADP也在计算机科学中以强化学习的名义发展（参见Sutton和Barto（19 98））。许多ADP算法专注于有限时间范围内的问题，其中最优值函数和策略是平稳的。相比之下，我们的EM-C算法关注的是有限时间范围的问题，即最优值函数和最优策略都不是平稳的。值函数迭代与随机动态规划的对偶方法密切相关；参见Brown、Smith和Sun（2010）、Brown和Smith（2014）、Brown和Haugh（2014）。我们的算法与策略迭代DP算法相关，但本质上不同，主要在于：（i）EM-C算法不使用Bellman方程；（ii）EM-C算法对每次迭代的值函数有单次改进；（iii）EM-C算法可以应用于目标函数不可时间分离的一般控制问题。ADP与模拟美式期权定价问题密切相关。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-26 22:43:54

Broadie和Glasserman（1997）为美式期权定价开发了一种隐式近似动态规划算法，该算法为随机抽样树中的每个分支分配相等的权重。Longstaff和Schwartz（2001）以及Tsitiklis和Van Roy（2001）在一组基函数上将模拟与回归相结合，以开发价值函数的低维近似；它们与Broadie和G la sserman（2004）中介绍的Stocastic网格方法有关，并对应于网格权重的隐式选择。更多讨论请参见Glasserman（2004年，第8章）。马尔可夫决策过程的文献主要研究具有有限状态空间或有限控制空间的多周期随机控制问题。马尔可夫决策过程也有基于模拟的算法；参见Chang、Fu、Hu和Marcus（2007）和Gosavi（2015）的著作，以了解全面的回顾和讨论。这些算法与我们的EM-C算法之间的主要区别是：（i）EM-C算法在每次迭代中都是单调的；（ii）EM Calgorithm不使用Bellman方程。论文的其余部分组织如下。在第2节中，我们提出了EM算法。在第3节中，我们展示了EM-C算法在每次迭代中改进了objectivefunction，因此具有良好的收敛性。在第4节中，我们提出了一种基于仿真和Stocastic近似算法的EM-C算法的实现。第5节和第6节分别介绍了EM-C算法在机票垄断定价和实际商业周期垄断定价中的两个应用。2 EM控制（EM-C）算法2.1 EM算法假设我们观察随机向量z的数据z，但不观察随机向量Y的数据。假设X=（Y，Z）的联合概率密度函数由p（Y，Z |θ）给出，θ为参数。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-26 22:43:59

Z的概率密度函数由p（Z |θ）给出。参数θ的最大似然估计是通过最大化对数似然L（θ）=对数p（z |θ）得到的。从初始估计θ开始，在第k次迭代时，EM alg算法更新θk-1通过两个步骤得到θkb：1。E步骤：计算qk（y）=p（y | z，θk-1），这是给定观测数据a z和参数估计θk的缺失数据y的条件密度-1来自上一次迭代。2.M步骤：将θkt设置为最大化seqk的θ[log p（y，z |θ）]：=^log p（y，z |θ）qk（y）dy，其中Eqk表示在条件分布qk下对y的期望。Neal和Hinton（1999）提供了EM算法的另一种观点，其中E步和M步都在最大化（或至少不减少）相同的目标函数。事实上，定义函数F（q，θ）asF（q，θ）：=等式[对数p（y，z |θ）]+H（q）=对数p（y，z |θ）q（y）dy+H（q），（1）其中H（q）：=-\'log q（y）·q（y）dy是概率密度q的熵。Neal和Hinton（1999，定理1）表明，在第k次迭代时，EMalgorithm的E步和M步等价于1。E步骤：将qkt设置为arg maxqF（q，θk-1）。2、M步：将θkt设置为arg maxθF（qk，θ）。因此，在每次迭代中，EM算法首先将目标函数F（q，θ）最大化（仅针对t o q且θ固定），然后将F（q，θ）最大化（仅针对θ且q固定）。EM算法允许（Y，Z）的非常一般的分布假设；italso在每次迭代中都具有单调性，因此具有良好的收敛性（Wu（1983））。2.2多周期有限时域随机控制问题现在，我们考虑一个一般的多周期有限时域随机控制问题，该问题考虑了向量值控制策略、向量值状态和向量值随机冲击。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-26 22:44:02

设Nc为控制策略的维度，Ns为状态的维度。假设有T个时段，在时段0，决策者观察初始状态s∈ Rns。在第tth阶段，决策者为州ZF服务∈ RNS然后选择nc尺寸控制ct∈ σ（st），由st生成的sigma字段。因此，政策CTI适用于截至t期的可用信息，并且可以表示为st的函数。因为sis知道0期，c期∈ RNCI也是确定性的。对于t≥ 1，我们假设ct=c（t，st，θt），t≥ 1，（2）其中c（·）是一个函数，θt=（θt，1，θt，2，…，θt，d）′∈ Rdi是第tth个周期的参数向量。例如，可以假设策略cti由一组基函数线性跨越，即ct：=Pdi=1θt，iφt，i（st），t≥ 1，式中{φt，i:Rns→ Rnc，i=1，d} 是第tth个周期的基函数集。状态st+1由控制ct通过以下状态演化方程st+1=ψt+1（st，ct，zt+1），（3）确定，其中ψt+1（·）是状态演化函数，zt+1∈ Rnzi是表示（t+1）t h周期内随机冲击的随机向量。在本文中，我们假设初始状态为已知的每iod 0。事实上，如果sis rando m在一个问题中，我们可以简单地将该问题中的周期0设为周期1，然后该问题的随机sin就变成了我们的问题公式。（3）中的状态演化动力学是一个一般的动力学，不限于离散化的扩散过程或列维过程。在时段0，决策者希望选择最优控制c∈ RNC和控制参数的顺序θ，θT-1，它确定控件c。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-26 22:44:05

，cT-1，以最大化他或她的效用最大值（c，θ，…，θT-（1）∈ΘE“T-1Xt=0ut+1（st+1，st，ct）c、 θ，θT-1#（4）s.t.ct=c（t，st，θt），t=0，1，T- 1，（5）st+1=ψt+1（st，ct，zt+1），t=0，1，T- 1，其中Θ是RN的子集，其中n=nc+（T-1） d；ut+1（·）是决策者在（t+1）时期的效用函数。值得注意的是，第一阶段的效用函数可以包括第0阶段的效用。一个比问题（4）更一般的控制问题由max（c，θ，…，θT）给出-（1）∈ΘE[u（s，c，s，c，…，sT-1，cT-1，sT）| c，θ，θT-1] （6）s.t.ct=c（t，st，θt），t=0，1，T- 1，st+1=ψt+1（st，ct，zt+1），t=0，1，T- 1，其中u（s，c，s，c，…，sT-1，cT-1，sT）是一个通用的效用函数，它可能不会像（4）中的函数那样在时间上是可分离的。为了便于说明，我们将给出问题（4）的ourEM-C算法；然而，EM-C算法也适用于一般问题（6）；详见附录D。为便于记法，我们表示x=（c，θ，θ，…，θT-1）用U（x）表示问题（4）的目标函数：=U（c，θ，θ，…，θt-1）：=E“T-1Xt=0ut+1（st+1，st，ct）c、 θ，θT-1#。（7）一般来说，（7）中的期望值不能以闭合形式计算，因此U（x）没有解析形式。2.3 EM控制（EM-C）算法的描述在本小节中，我们概括了EM算法的思想，提出了用于求解（4）的EM控制（EM-C）算法。EM-C算法是一种迭代算法，涉及多轮前后更新。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-26 22:44:10

EM-C算法继承了EM算法的精神，通过优化目标函数来更新给定时间段的控制策略，该目标函数仅针对该时间段的控制策略，并且所有其他时间段的控制策略固定在算法迭代中的最新状态。更准确地说，假设在（k）之后-1）第h次迭代，控制策略参数为xk-1： =（ck-1，θk-1，θk-1.θk-1吨-1）。在第k次迭代中，EM-C算法更新xk-1为xk：=（ck，θk，θk，…，θkT-1）根据更新规则：xk∈ M（xk-1），（8）其中M（·）是将映射设置在表示更新规则的Θ上的点（即，M（·）将Θ中的点映射到Θ的子集）。EM-C算法更新ck-1，θk-1，θk-1.θk-1吨-1及时后退；在每个时间段t=t- 1，T- 2.1，算法更新θk-1t为θkt，然后向后移动以更新θk-1吨-1.最后，算法更新ck-1确认。接下来，我们在（8）中指定精确的更新规则。在第k次迭代中，在周期t更新控制参数之前∈ {T-1，T-2.1} ，控制参数为（ck-1，θk-1.θk-1吨-1，θk-1t，θkt+1，θkt+2，θkT-1）。然后，在周期t，em-C算法更新θk-1t为θkt，使得u（ck-1，θk-1，θk-1.θk-1吨-1，θkt，θkt+1，θkT-（1）≥ U（ck-1，θk-1，θk-1.θk-1吨-1，θk-1t，θkt+1，θkT-1），（9）可以很容易地显示为等效toE“T-1Xj=tuj+1（sj+1，sj，cj）ck公司-1，θk-1.θk-1吨-1，θkt，θkt+1，θkT-1个#≥ E“T-1Xj=tuj+1（sj+1，sj，cj）ck公司-1，θk-1.θk-1吨-1，θk-1t，θkt+1，θkT-1#；（10）详见附录A。因此，可以通过找到问题maxθt的次优（o最优）解决方案来获得满足（9）的θkt∈ΘtE“T-1Xj=tuj+1（sj+1，sj，cj）ck公司-1，θk-1.θk-1吨-1，θt，θkt+1。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-26 22:44:13

，θkT-1#，其中Θt={θ∈ Rd |（ck-1，θk-1.θk-1吨-1，θ，θkt+1，θkT-（1）∈ Θ}。θk之后-1更新为θkt，控制策略参数更新自（ck-1，θk-1.θk-1吨-1，θk-1t，θkt+1，θkT-1）至（ck-1，θk-1，θk-1吨-1，θkt，θkt+1，θkT-1）。类似地，在周期0，ck之前-1已更新，控制策略参数为（ck-1，θk，θkT-1）。然后，EM-C算法更新ck-1使u（ck，θk，θk，…，θkT-（1）≥ U（ck-1，θk，θk，θkT-1）。（11）然后，从（ck）更新控制参数-1，θk，θkT-1） to（ck，θk，…，θkT-1）。简而言之，算法1总结了用于解决问题（4）的EM-C算法。有两条注释：（i）在EM-C算法中，当我们更新θk时-1ttoθktor更新ck-1要检查，如果目标函数没有改进，我们只需设置θkt=θk-1或设置ck=ck-1.（ii）EM-C算法不使用动态规划原理（即Bellman方程）。相比之下，文献中的ADP算法是基于Bellman方程的。此外，由于EM-C算法不使用Bellman方程，因此它可以应用于效用函数不可时间分离的一般控制问题（6）。详见附录D。inNeal和Hinton（1999）对EM算法的直觉以及我们的EM-C算法的直觉也与块坐标下降（BCD）算法有关，在该算法中，坐标被划分为块，并且在迭代的每个子步中，仅以循环顺序更新一个坐标块。然而，算法的细节差别很大：（i）本质上，EM-C算法试图更新控制策略，就像EM算法一样，它可以被视为在函数空间（即（1）中的分布空间q）而不是实数空间中的广义BCD搜索。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

大多数88

2022-5-26 22:44:16

这就是为什么EM-C算法的收敛性证明类似于EM算法的收敛性证明（如Wu（1983））。（ii）BCD方法用于最大化确定性目标函数，但算法1用于解决问题（4）1的EM-C算法。初始化k=1和x=（c，θ，θ，…，θT-1）。2、迭代k，直到满足某些停止条件。在第k次迭代中，updatexk-1=（ck-1，θk-1，θk-1.θk-1吨-1）至xk=（ck，θk，θk，…，θkT-1）从t=t向后移动- 1到t=0，如下所示：（a）从t=t向后移动- 1至t=1。在每个周期t，更新θk-1t为θkt，使e“T-1Xj=tuj+1（sj+1，sj，cj）ck公司-1，θk-1.θk-1吨-1，θkt，θkt+1，θkT-1个#≥ E“T-1Xj=tuj+1（sj+1，sj，cj）ck公司-1，θk-1.θk-1吨-1，θk-1t，θkt+1，θkT-1#。这样的θkt可以设置为问题maxθt的次优（最优）解∈ΘtE“T-1Xj=tuj+1（sj+1，sj，cj）ck公司-1，θk-1.θk-1吨-1，θt，θkt+1，θkT-1#。（12）（b）在时段0，更新e ck-1确保-1Xj=0uj+1（sj+1，sj，cj）ck，θk，θkT-1个#≥ E“T-1Xj=0uj+1（sj+1，sj，cj）ck公司-1，θk，θkT-1#。这种CKC可以设置为问题MaxC的次优（最优）解∈ΘE“T-1Xj=0uj+1（sj+1，sj，cj）c、 θk，θkT-1#，（13）式中Θ={c∈ Rnc |（c，θk，…，θkT-（1）∈ Θ}。EM-C算法用于最大化随机效用函数的期望值（即（7）），通常无法对其进行分析评估。这就是为什么我们必须采用模拟和随机优化来实现EM-C算法（见第4节）。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-26 22:44:19

（iii）EM-C算法在优化要求方面更加灵活。与BCD算法不同，EM-C算法不需要将控制参数更新为子问题（12）或（13）的精确最小值，也不需要根据目标函数的梯度更新控制参数，部分原因是，在EM-C算法可解的问题中，通常没有目标函数（即（7）），也没有目标函数的梯度可以通过分析来计算。（iv）EM-C算法的收敛性满足underweaker条件。BCD算法的收敛性是基于对目标函数的各种假设获得的，例如目标函数是凸的或是光滑函数和凸可分函数的和，或满足一定的可分性和正则性条件；相反，EM-C算法的收敛性证明类似于EM算法的收敛性证明，如Wu（1983）所述，该算法不需要对目标函数进行此类假设。详见第3节。3收敛性分析EM-C算法的收敛性与EM算法相似。首先，EM-C算法在每次迭代中都具有单调性。其次，在温和的假设下，迭代EM-C算法生成的目标函数值序列收敛到一个平稳值（即，在平稳点评估的目标函数值）或局部最大值。第三，EM-C算法迭代生成的控制参数序列在一些额外的正则性条件下收敛到一个平稳点或一个局部极大点。Luo和Tseng（1992）证明了当目标函数是两次连续可微的严格凸时，坐标下降（CD）算法的收敛性。Bertsekas（1999年，第二章。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

kedemingshi

2022-5-26 22:44:24

2.7）显示了当每个子问题的精确最小值唯一且用于更新坐标块时，CD a算法的收敛性。Tsung（2001）研究了当目标函数具有一定的可分性和正则性，并且当每个子问题的精确极小值用于更新坐标块时，块CD方法的收敛性。Wright（2015）讨论了当目标函数为凸函数时，以及当坐标根据目标函数的梯度更新时，CD算法的收敛性。3.1单调性定理1。（7）中定义的目标函数U（·）在EM-C算法的每次迭代中单调递增，即U（xk）=U（ck，θk，θk，…，θkT-（1）≥ U（xk-1） =U（ck-1，θk-1，θk-1.θk-1吨-1），则，k、（14）证明。见附录B。1.3.2{U（xk）}k的收敛性≥0到固定值或本地最大值let{xk}k≥0be由EM-C算法生成的控制参数序列。在本小节中，我们考虑U（xk）收敛到平稳值或局部最大值的问题。我们对（7）中定义的目标函数U（·）做出以下温和假设：对于任何x，U（x）>-∞, {x∈ Θ| U（x）≥ U（x）}是紧的。（15） U（·）在Θ中是连续的，在Θ内部是可区分的。（16）需要假设（16），因为我们需要确定U（·）的固定点。假设目标函数U（·）满足（15）和（16）。那么，我们有{U（xk）}k≥对于U（x）>-∞. （17）通过（14）和（17），U（xk）单调收敛于某个U*. 我们不能保证*是U onΘ的glo ba l最大值。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

大多数88

2022-5-26 22:44:27

一般来说，如果目标函数uh有几个局部极大值和平稳点，则EM-C算法生成的序列收敛到哪种类型的点取决于起始点x的选择；EM算法也是如此。从X的点到X的子集的映射ρ称为在X上设置映射的点（Wu（1983））。设M为（8）中定义的EM-C算法的点对集映射。定义：=U（·）inΘ的局部极大值集，S：=U（·）inΘ的固定点集，M（a）：={x∈ M | U（x）=a}，（18）S（a）：={x∈ S | U（x）=a}。（19）关于{U（xk）}k的收敛性，我们有以下定理≥0表示EM-C算法。定理2。提供满足条件（15）和（16）的目标函数。设{xk}k≥0be由xk生成的序列∈ M（xk-1）在EM-C算法中。（1）假设U（xk）>U（xk-1）对于任何xk-1个/∈ S（分别为xk-1个/∈ M）。（20）然后，所有{xk}k的极限点≥0是U的平稳点（对应于局部极大值），U（xk）单调收敛于U*= U（x*) 对于s ome x*∈ S（分别为x*∈ M）。（2）假设在EM-C算法的每次迭代中，k和所有t，θkt和ck分别是问题（12）和（13）的最优解。然后，{xk}的所有极限点都是U的平稳点，U（xk）单调收敛于*= U（x*) 对于s ome x*∈ S、证明。见附录B。2.3.3{xk}k的收敛性≥0到一个固定点或局部最大小点M（a）和S（a）分别在（18）和（19）中定义。在ORM2条件下，U（xk）→ U*{xk}的所有极限点都在S（U）中*) （分别为M（U*)).然而，这并不自动意味着{xk}k的收敛≥0到a点X*. 但是，如果S（U*) （分别为M（U*)) 由单个点x组成*, i、 e.，t此处不能是两个不同的固定点（分别为局部极大值），具有相同的U*, 然后下面的定理说xk→ x个*.

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-26 22:44:30

下面的定理还提供了xk→ x个*.定理3。设{xk}k≥0是满足定理2条件的EM-C算法的一个实例，并让U*是{U（xk）}k的极限≥0.（1）如果S（U*) = {x*} （分别为M（U*) = {x*}), 然后是xk→ x个*作为k→ ∞.（2）如果kxk+1-xkk公司→ 0 a s k→ ∞, 然后，在S（U）的连通紧致子集中，xkare的所有极限点*) （分别为M（U*)). 特别是，如果S（U*) （分别为M（U*))是Discrete，即其唯一连接的组件是Singleton，然后XkConverge到一些x*以S（U）为单位*) （分别为M（U*)).证据见附录B。当然，从实用的角度来看，值函数{U（xk）}k的收敛性≥0到平稳值或局部最大值比{xk}k的收敛性更重要≥0.4 EM-C算法的实现4.1通过模拟EM-C算法来实现EM-C算法，我们需要找到问题（12）和（13）的次优（最优）解决方案。在实践中，这些问题的目标函数中的期望值可能无法以封闭形式进行评估，这使得解决这些问题变得困难。我们建议使用一种基于模拟的方法来解决这些问题，称为随机近似（SA）算法。SA是一种经典的迭代随机优化算法，它试图找到无法直接计算的期望值的零或极值。更准确地说，在EM-C算法的每次迭代中，使用currentpolicy模拟样本路径，然后应用SA在每个时间段查找控制策略的更新，以改进目标函数。在第k次迭代开始时，我们首先模拟N i.i.d.状态的样本路径（s、s、…、sT-1）根据控制参数（ck-1，θk-1.θk-1吨-1），在（k）末尾获得- 1）第次迭代。我们将这些采样路径表示为（s，sk1，l，sk2，l。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

kedemingshi

2022-5-26 22:44:34

，skT-1，l），l=1，N、 SA算法由Robbins和Monro（1951）以及Kiefer和Wolfowitz（1952）提出。它已广泛用于强化学习，以改进时间差异方法中的政策（参见Chang、Fu、Hu和Marcus（2007））。有大量关于SA算法的文献；例如，参见Gu和Li（19 98）、Lai（2003）的调查论文以及Kushner和Yin（2003）和Spall（2003）的著作。Broadie、Cice k和Zeevi（2011）提出了一种SA算法，改进了k iefer-Wolfowitz算法的实时性能。然而，不必使用SA算法来实现我们的EM-C算法。其中一条渠道还使用了其他随机优化算法，如cro ss熵算法（Rubinsteinand Kroese（2004））。在算法1的步骤2（a）o中，我们应用SA算法来解决问题（12）。（12）目标函数中的期望值等于T-1Xj=tuj+1（sj+1，sj，cj）ck公司-1，θk-1.θk-1吨-1，θt，θkt+1，θkT-1#=E（NNXl=1“ut+1（skt+1，l（θt），skt，l，ckt，l（θt））+t-1Xj=t+1uj+1（skj+1，l（θt），skj，l（θt），ckj，l（θt））），（21）其中ckt，l（θt）=c（t，skt，l，θt）（见（5））和（skt+1，l（θt），ckt+1，l（θt），skT公司-1，l（θt），ckT-1，l（θt），skT，l（θt））是一个模拟样本，从skT开始，然后遵循控制参数θt，θkt+1，θkT-1、SA算法使用▄f（θt）：=NNXl=1“ut+1（skt+1，l（θt），skt，l，ckt，l（θt））+t-1Xj=t+1uj+1（skj+1，l（θt），skj，l（θt），ckj，l（θt））#（22）作为解决问题时目标函数的近似值。因此，在SA算法的每次迭代中（在对应于该迭代的参数θt处），我们只需要模拟周期t+1到周期t期间的N个状态样本路径，即（skt+1，l（θt），skT公司-1，l（θt），skT，l（θt）），l=1，N、样品skt，l，l=1。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-26 22:44:37

，N对于SA算法的所有迭代都是相同的。在算法1的步骤2（b）中，我们应用SA算法来解决问题（13）。（13）中的期望值等于t oE“t-1Xj=0uj+1（sj+1，sj，cj）c、 θk，θkT-1#=E（NNXl=1“u（sk1，l（c），s，c）+T-1Xj=1uj+1（skj+1，l（c），skj，l（c），ckj，l（c）），（23），其中{（sk1，l（c），ck1，l（c），…，skT-1，l（c），ckT-1，l（c），skT，l（c））}Nl=1是N i.i.d.样本路径（s，c，…，sT-1，cT-1，sT），从砂开始模拟，然后遵循控制参数（c，θk，…，θkT-1）。SA算法使用▄f（c）：=NNXl=1“u（sk1，l（c），s，c）+T-1Xj=1uj+1（skj+1，l（c），skj，l（c），ckj，l（c））#（24），作为解决问题时目标函数的近似值（13）。附录XC中描述了用于解决问题（12）和（13）的SA算法的详细信息。假设我们在SA算法中使用固定数量的m次迭代。然后，解决问题（12）和（13）的计算成本分别为O（m（T-t+1）和O（mT）。因此，EM-Calgorithm每次迭代的计算成本为O（mT）。4.2数值示例：一个简单的随机增长模型我们考虑一个简单的随机增长问题，如下所示Maxcte“Xt=0ut+1（st+1，st，ct）#=E”Xt=0log ct+log s#（25）s.t.st+1=st公司-st1+exp（ct）exp（a+bzt+1），t=0，1，2，s=1，ct∈ R、 t=0，1，2，其中a是常数，b>0是波动率，a和zt+1，t=0，1，2是具有标准正态分布的i.i.d.随机噪声。在第tth个时间段，amountst1+exp（ct）从资本st中消耗，剩余资本按倍数exp（a+bzt+1）增长。所有可用资本将在年底消耗掉（t=3）。该问题可以用以下最优控制和最优值函数解析求解C*t=对数（3- t），t=0，1，2，（26）V（s）=6a- 4对数4+4对数s。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-26 22:44:40

（27）为了对我们的算法进行数值测试，我们选择a=-0.1，b=0。2、我们在模拟中使用了n=10000条样本路径，在SAalgorithm中使用了m=200 0次迭代。我们考虑两种基函数。在第一个规范中，我们仅使用一个基函数φ（s）=s；ct=θt，1φ（st）。在第二个规范中，我们使用两个基函数φ（s）=1，φ（s）=s；ct=θt，1φ（st）+θt，2φ（st）。从（26）可以看出，理论最优策略c*由第二个规范中的基础（对应于最佳控制参数θ）线性规划的空间中的指数*t=（对数（3- t），0）\'），但不在第一个中。在EM-C算法中，我们选择C=0，θt=0，t、图1显示了EM-C算法通过使用两种规格的基函数在问题（25）的5次迭代中的目标函数值。在这两种情况下，EM-C算法经过两次迭代后，即使在第一种情况下仅使用一个基本函数，也会快速收敛到接近（27）给出的理论最优目标函数值。每次迭代大约需要3分钟。5应用1：易腐产品的垄断定价在本节中，我们将应用EM-C算法来解决与机票的非垄断定价相关的两个问题。第一种是单产品航空公司机票定价，更多的是为了说明该算法的有效性，因为这里有一个可用于问题连续时间版本的分析解决方案，以及一个用于问题离散版本的良好启发式插件方法。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-26 22:44:43

第二个问题是多产品机票定价问题，目前为止只有启发式方法0 1 2 3 4 5迭代-6.9-6.8-6.7-6.6-6.5-6.4-6.3-6.2-6.1使用一个基本EM-C和两个基本EM-C的理论最优EM-C图1：EM-C a lg算法在5次迭代中的目标函数值（25）。在实现中，我们在模拟中使用N=10000个样本路径，在SA算法中使用m=2000个迭代。EM-C算法经过2次迭代后收敛。每次迭代大约需要3分钟。理论最优目标函数值为-6.1452。当仅使用一个基函数时，EM-C算法获得的最佳目标函数值为-6.1421（7.4659e-0 3），当使用两个基函数时，目标函数值为-6.1358（7.4755e-03）。括号中的数字表示使用N个样本路径估计目标函数的标准误差，等于右侧N个样本的样本标准偏差除以√N、方法可用。与启发式方法相比，EM-C算法不仅提供了严格的解决方案，而且还产生了显著的价值函数改进。5.1单一产品案例5.1.1单一产品垄断定价模型考虑了Gallego和Van Ryzin（1994）提出的机票单一产品垄断定价。这是一个只有一个状态和一个控制的有限视界问题。假设短期内的收入（t，t+t）由p（λt）给出Nλ，其中λt是时间t的销售强度，Nλ是强度为λt的泊松计数过程，p（λt）是时间t的价格，以及Nλ是时间间隔（t，t+t）。连续时间问题表示为V（nc，T）=supλsE^Tp（λs）dNλs（28）s.t。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

kedemingshi

2022-5-26 22:44:47

NλT≤ nc，p（λs）=-αlogλsa，对于s≤ T、其中ncis为总剩余容量，T为到期时间。在这个问题中，状态变量是剩余容量Rs=nc- Nλs控制为λs，它决定票价p（λs）和未来到达的动态。显然，对于任何nc和任何T，V（nc，0）=V（0，T）=0。当α=1时，幸运的是，（Gallego and Van Ryzin（1994））V（nc，t）=logncXk=0（aT/e）kk！！，f或任何nc∈ N+，t>0，（29）p*t=p（λ*t） =V（Rt，t-t）- V（Rt- 1，T- t） +1，用于Rt≥ 1, 0≤ t型≤ T、（30）我们将时间范围[0，T]离散为n相等的周期，表示为T=0，tnT=T，并将问题（28）的离散形式表示为：maxcti，i=0,1，。。。，nT公司-1E“nT-1Xi=0p（λti）（Ncti+1- Ncti）#（31）s.t.Nλti+1- Nλtid~ 泊松（λtiT/nT），i=0，1，nT公司- 1，（32）Ncti+1- Ncti=最小值（nc- Ncti，Nλti+1- Nλti），i=0，1，nT公司- 1，（33）p（λti）=-αlogλtia，i=0，1，nT公司- 1，λti=a1+exp（cti），i=0，1，nT公司- 1、（34）cti∈ R、 i=0，1，nT公司- 1，其中（32）表示Nλti+1- Nλti具有平均λtiT/nT的泊松分布；Nctis在[0，t]期间到达并购买机票的客户总数；（33）是指NCTI上限为nc；（34）用于引入约束λti∈ （0，a）。在离散问题（31）中，状态变量为剩余电容rti=nc- Ncti。离散问题没有解析解（31）；但当α=1时，连续问题的最优策略（30）可以用作离散问题的插件策略。5.1.2数值结果在问题（31）的以下数值示例中，我们分别选择a=20、α=1、T=1、nT=4和nc=20、10和5。我们在模拟中使用N=10000个样本路径，在SA算法中使用m=1000个迭代。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-26 22:44:52

我们将控制视为三个基函数的线性组合：φi（R）：=Ri，i=0，1，2；ct=θt，1φ（Rt）+θt，2φ（Rt）+θt，3φ（Rt）。在该算法中，我们选择c=0，θt=0作为所有t的初值。表1比较了在三种策略下分别获得的连续问题（28）和离散问题（31）的预期收益：（i）在理论最优策略（30）下连续问题的预期收益；（ii）在插件策略下获得的离散问题的预期收入（30）；（iii）在EM-C算法计算的最优策略下获得的离散问题的预期收益。对于离散问题，EM-C算法得到的最优策略的期望均匀性似乎略好于插入式策略。为了证明EM-C算法的收敛性，图2显示了EM-C算法在5次迭代中的目标函数值nc=20 nc=10 nc=5连续离散连续离散插入EM-C插件EM Cmean 7.3576 7.3494 7.3777 7.2231 7.2207 7.2237 6.000 5.8964 5.9419std。误差N/A 0.0271 0.0270 N/A 0.0257 0.0260 N/A 0.0205 0.0204表1：单一产品的垄断定价：分别在三种策略下获得的连续问题（28）和离散问题（31）的预期收益：（i）“连续”是指理论最优策略（30）下连续问题的预期收益；（ii）“插件”是指根据插件策略（30）获得的Discrete问题的预期收入；（iii）“EM-C”是指在EM-C算法计算的最优策略下获得的离散问题的预期收益。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-26 22:44:55

连续问题的理论最优策略下的预期收益由（29）计算得出；插件和EM-C策略下离散问题的预期收益是通过N=10000个样本路径估计的。我们考虑三种情况：nc=20、10和5。“标准误差”表示预计收入估计的标准误差，等于（24）右侧N个样本的标准偏差除以√N、对于离散问题（31），当nc分别为20、10和5时。5.2多产品案例5.2.1多产品垄断定价模型正如inGallego和Van Ryzin（1997）首次研究的那样，我们将单产品单多定价模型扩展为多产品模型。在高维情况下，这个问题无法解析求解。更准确地说，假设航空公司航班网络有NLLEGS（直飞航班），基于此有NICINERAGES。定义矩阵：=【akj】∈ Rnl×ni，其中akj∈ {0，1}a和akj=1当且仅当直射光k是行程j的一部分。例如，考虑一个具有3个节点的简单网络，{1，2，3}，两个直射光{1→ 2，2→ 3} ，以及三条行程{1→ 2，2→ 3，1→ 2.→ 3} 。那么对于该灯光网络，A=1 0 10 1！。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-26 22:45:00

（35）正如人们所看到的，这个问题的规模增长非常快，蒙特卡罗方法可能会为解决这样一个问题带来现实的希望。0 1 2 3 4迭代6.9577.057.17.157.27.257.37.357.4目标函数值离散问题的连续近似EM-C（a）nc=200 1 2 3 4迭代66.26.66.877.27.4目标函数值离散问题的连续近似EM-C（b）nc=100 1 2 3 4迭代33.544.555.56目标函数值离散问题的连续近似EM-C（C）nc=5图2：目标EM Calgorithm在单产品垄断定价问题的5次迭代中获得的函数值（预期收入）（31）。EM-C算法经过2次迭代后收敛。每次迭代大约需要3分钟。让p∈ Rnibe是NITineraries的价格向量。需要NITineraries的客户根据流程Nλ来买票∈ NNI，到达率λ∈ Rni。假设p是客户到达率λ的函数。让直射灯的初始容量为nc∈ Nnl。目标是通过选择价格p或等效的客户到达率λ来优化预期收入。更准确地说，多产品垄断定价问题可以用asV（nc，T）=supλsE来表示^Tp（λs）′dNλs（36）s.t.V（n，0）=V（0，t）=0，n∈ Nnl，t>0，^TAdNλs≤ nc，p（λs）j=（-10，jlogλ0，jλs，j+1）p0，j，对于s≤ T、 j=1，镍。由于与问题（36）相对应的高维HJB方程很难解决，G allego和Van Ryzin（1997）提供了两种启发式策略，称为MTS和MTO，它们随着问题的规模变得越来越小而渐近最优。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

可人4

2022-5-26 22:45:03

这两种启发式策略都使用该问题确定性版本的最优控制，该问题假设控制λ是时不变和确定性的。确定性问题作为约束非线性优化问题求解。将相应的控制和价格表示为^λ*和^p*分别地更准确地说，MTS和MTO政策如下：（i）MTS政策：将价格设置为确定性最优价格^p*并相应地为每个行程预先分配座位。如果预定座位f或行程j用完，停止销售行程j的机票；（ii）MTO政策：将价格设定为确定性最优价格^p*并按客户到达的顺序售票。当至少一架直飞航班k的库存严格低于akj时，停止销售行程J的机票。我们关注问题的离散时间设置。时间范围[0，T]被划分为n个相等的周期，表示为T=0<T<···<tNT-1<tNT=T。离散时间问题表示为Maxctk，j，k=0，。。。，nT公司-1，j=1，。。。，niE“nT-1Xk=0p（λtk）′（Nctk+1- Nctk）#（37）s.t.Nλtk+1，j- Nλtk，j~ P oisson（λtk，jT/nT），j=1，ni，kNctk+1=G（nc，Nctk，Nλtk+1- Nλtk），k、（38）p（λtk）j=（-10，jlogλ0，jλtk，j+1）p0，j，j=1，ni，k、 λtk，j=最小值（λ0，je0，j，max（ctk，j，0）），j=1，ni，k、（39）ctk，j∈ R、 j=1，镍。在公式中，λtk，j应满足0<λtk，j<λ0，je0，j的约束。约束由（39）计算，这意味着λtk，j=ctk，jif 0<ctk，j<λ0，je0，j和λtk，j=0如果ctk，j≤ 0和λtk，j=λ0，je0，jif ctk，j≥ λ0，je0，j。问题的控制为ctk=（ctk，1，…，ctk，ni）′。问题的状态变量是剩余容量Rtk=nc- ANctk公司。与单个产品的情况类似，我们将客户到达流程限制在NCO，以引入容量约束。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

可人4

2022-5-26 22:45:07

在多产品情况下，封顶变得更加复杂，因为有多种方法可以将直飞航班的剩余容量分配给行程。因此，（38）中的函数G定义为G（nc，Nctk，Nλtk+1- Nλtk）：=Nctk+Nλtk+1- Nλtk，如果A（Nctk+Nλtk+1- Nλtk）≤ nc，Nctk+ctk+1，否则，（40），其中ctk+1=arg maxNp（λtk）′Ns。t、 AN≤ Rtk，N≥ 0，N≤ Nλtk+1- Nλtk，N∈ Nni公司。条件A（Nctk+Nλtk+1- Nλtk）≤ ncin（40）是指不超过容量的情况，在此情况下不执行封顶。如果某些直射灯的容量超过了容量，则剩余容量将被优化分配，以在实施过程中实现最大化，我们实际上使用sλtk，j=min（（1- δ） λ0，je0，j，max（ctk，j，Δλ0，je0，j）），以确保0<λtk，j<λ0，je0，j，其中δ=10-5.本期收入[塔卡，塔卡+1]。这表明，当门票即将售出时，剩余的座位将分配给那些产生更多收入的行程。5.2.2数值结果我们考虑问题（37）的一个特殊情况，其中灯光网络有3个节点，{1，2，3}，两个直射灯光{1→ 2，2→ 3} ，以及三条行程{1→ 2，2→3，1→ 2.→ 3} 。假设直射灯的容量为nc=（nc1→2，nc2→3） ′=（300200）′。假设p=（p0，j）=（220，250，400）\'，=（0，j）=（1.0，1.2，1.1）\'，λ=（λ0，j）=（300，300）\'。设T=1，nT=6。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-26 22:45:10

状态变量为剩余容量R=（R1→2，R2→3） ′=nc-ANc，其中矩阵A在（35）中给出。我们使用状态变量的线性函数作为控制函数C=（c1→2，c2→3，c1→2.→3） ′，即基函数为φ1,1→2（R）=（1，0，0）′，φ1,2→3（R）=（0，1，0）′，φ1,1→2.→3（R）=（0，0，1）′，φ2,1→2（R）=（R1→2，0，0）′，φ2,2→3（R）=（0，R1→2，0）′，φ2,1→2.→3（R）=（0，0，R1→2） ′，φ3,1→2（R）=（R2→3，0，0）′，φ3,2→3（R）=（0，R2→3，0）′，φ3,1→2.→3（R）=（0，0，R2→3） ′。我们将周期t的控制参数表示为θt=（θt，k，l）k=1,2,3，l∈{1→2,2→3,1→2.→3} 。然后，控制ctisct=Xk=1Xl∈{1→2,2→3,1→2.→3} θt，k，lφk，l（Rt）。然后，我们将EM-C算法应用于该问题。我们在模拟中使用N=10000个采样路径，在SA算法中使用m=2000个迭代。初始控制参数candθtar设置为c=（100，100，100′）和θt，1，l=100，θt，2，l=θt，3，l=0，l、，t、图3显示了EM-C算法在6次迭代中的目标函数值。EM-C算法经过5次迭代后收敛。似乎（严格的）EM-C算法比两种启发式算法MTO和MTS产生的收入要高得多。表2比较了EM-C算法、MTO、a和MTS分别获得的收入分布，使用N=10，0000 1.721.741.761.781.81.821.841.861.88×10EM CMTSMTOFigure 3：两种启发式方法的目标函数值，MTO和MTS，以及（严格的）EM-C算法。EM-C算法经过5次迭代后收敛。它在模拟中使用N=10000个样本路径，在SA算法中使用m=2000个迭代。在Matlab程序下，每次迭代需要1.3小时。该程序的瓶颈是SA算法的迭代，该算法需要在Matlab中通过“for循环”来实现，这是众所周知的缓慢过程。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝