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

（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算法来解决与机票的非垄断定价相关的两个问题。第一种是单产品航空公司机票定价，更多的是为了说明该算法的有效性，因为这里有一个可用于问题连续时间版本的分析解决方案，以及一个用于问题离散版本的良好启发式插件方法。

第二个问题是多产品机票定价问题，目前为止只有启发式方法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。

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个迭代。

我们将控制视为三个基函数的线性组合：φ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算法计算的最优策略下获得的离散问题的预期收益。

连续问题的理论最优策略下的预期收益由（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！。

（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，它们随着问题的规模变得越来越小而渐近最优。

这两种启发式策略都使用该问题确定性版本的最优控制，该问题假设控制λ是时不变和确定性的。确定性问题作为约束非线性优化问题求解。将相应的控制和价格表示为^λ*和^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，以引入容量约束。

在多产品情况下，封顶变得更加复杂，因为有多种方法可以将直飞航班的剩余容量分配给行程。因此，（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。

状态变量为剩余容量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循环”来实现，这是众所周知的缓慢过程。

如果用s C／C++这样的编译语言实现该算法，可以大大减少计算时间。EM-C算法获得的最佳收益为1872 92.9（标准误差为54.7）。标准误差等于（24）右侧N个样本的样本标准偏差除以√N、 模拟中的采样路径。与MTO和MTS相比，EM Calgorithm下的总收入分布具有更高的平均值、更高的偏度、更小的峰度和更高的分位数（分别为1%、5%、95%和99%）。表2还比较了EM-C算法、MTO和MTS分别获得的第3期和第6期的收入。在第三阶段，EM-C算法的性能类似于MTO和MTS；然而，在第6个周期，EM-C算法在平均值和标准误差方面优于其他两个算法。EM-C法产生的总收入为187292.9，标准误差为54.7；而两种标准启发式方法（MTO和MTS）分别给出185090.2和182433.5，标准误差分别为58.2和59.0。因此，EM-C方法预计收入分别增长1.2%和2.7%。鉴于收入大而利润小的航空公司利润率很低，这是一个非常显著的改善。图4比较了EM Calgorithm、MTO和MTS下获得的总收入直方图；EM-C算法实现了比其他两种策略更好的右尾分布。1.5 1.6 1.7 1.8 1.9 2 2.1EM-C×100.050.10.150.21.5 1.6 1.7 1.8 1.9 2.1MTO×100.050.10.150.21.5 1.6 1.7 1.8 1.9 2 2 2 2 2 2图4：多产品垄断定价：比较EM-C算法（左）、MTO（中）和MTS（右）得出的总收入直方图。