金融网络中系统性风险的最优监控与缓解

与（45）类似，我们将拉格朗日定义为：L（p，c，q，y，z）=wTp- λ1Tc- qT（（IN×N）- πT）p- E- c）- 金伯利进程- yk- kc- zk=-NXi=1圆周率- （wi）- qi+2yi+NXj=1qj∏ij）pi-NXi=1词- (齐)- λ+2zi）ci+NXi=1秋- 易- 子（56）对偶问题的目标函数为：D（q，y，z）=max0≤P≤“p，c≥0L（p，c，q，y，z）那么对偶问题是：minq≥0D（q，y，z）拉格朗日乘数q由（55）更新，其中p和c最大化拉格朗日（56）。6.2.1算法A\'的实现我们针对这个问题的算法是算法A的简单修改。我们称之为算法A\'。其t-变形如下所示。1.每个节点i fix yi=yi（t）、zi=zi（t）和q=q（t），并计算piand ci:pi（t）=0如果π（t）<0如果π（t）>π（t）o.w.其中π（t）=yi（t）+（wi- 齐（t）+Xj∈Ciqj（t）∏ij）和ci（t）=子（t）+（气（t）- λ)+.然后每个节点i向每个节点j发送∏ijpi（t）∈ Ci。2.每个节点i从每个节点k接收∏kipk（t）∈ Biand更新气：气（t+1）=“气（t）+β（pi（t）- 工程安装- ci（t）-Xk∈Bi∏kipk（t））#+。然后每个节点i向每个k发送更新的qi（t+1）∈ 毕。3.每个节点i从每个j接收qj（t+1）∈ Ciand更新了一和子：一（t+1）=0如果yi（t+1）<0如果yi（t+1）>pi（t+1）o.w.其中yi（t+1）=yi（t）+wi- 齐（t+1）+Xj∈Ciqj（t+1）∏ij）和zi（t+1）=[zi（t+1）]+，其中<<zi（t+1）=zi（t）+（qi（t+1）- λ).每个节点i检查条件|yi（t+1）- |yi（t）|<δ和|zi（t+1）- ~zi（t）|<δ。如果两个条件都为空，则设置bi=1；否则，它将bi设置为0。然后将bito发送到中心节点Nc。如果bi=1表示所有ithen NCASK所有节点终止算法。这些步骤如图16.6.3数值结果6所示。3.1示例1：一个四节点网络在本节中，我们将说明我们的分布式算法对最优解的收敛性。我们使用图17（a）所示的四节点网络。

节点A欠B和C 50美元，节点B欠C 20美元，节点Cows欠A 80美元，节点D欠C 10美元。每个节点手头有1美元。在所有清算付款之后，借款人-贷款人网络缩减为图17（b）。在没有任何外部财务支持的情况下，节点A、C和DABD$ !“#%&\'（）*+-.0/01（a）初始网络。23456789:；<=>？@EFGHIJKLMO（b）无需任何救助的清算。图17：一个四节点网络。pqrtuvxyz[\\]^ adfghjklm图18：图17网络中的清算，用于15美元现金注入的优化分配。0 2000 4000 6000 8000 10000 1200002046080100迭代支付向量节点CNode（a）支付向量。0 2000 4000 6000 8000 10000 120000246810迭代现金注入向量节点阳极b节点CNode D（b）现金注入向量。图19:distributedalgorithm迭代过程中节点支付和现金注入的演变，用于在图17的网络中找到15美元现金注入的最佳分配。违约，未付债务总额为98美元。假设i=1,2，···，Nin LP（4）的wi=0.45，即每一美元未付债务对成本的贡献为0.45。在没有任何外部现金注入的情况下，成本函数的值为98×0.45=44.1。我们首先研究问题I，即注入现金的最高总金额固定的情况。我们假设我们最多可以向这个系统注入15美元。我们用初始y（0）=z（0）=q（0）=0和λ=0运行我们的算法。步长为α=β=0.1，停止公差为δ=δ=10-6.无花果。19（a）和19（b）分别举例说明了支付向量p和现金注入向量c的演变，作为拟议分布式算法迭代次数的函数。支付向量收敛到[pA，pB，pC，pD]=[76,20,75,10]；现金注入向量收敛到[cA，cB，cC，cD]=[0,0,6.0,9.0]。

通过直接求解LP（4-6），这些都是最优的。通过外部现金注入，借款人-贷款人网络在所有付款后缩减至图18。现在，未付债务总额为29美元。因此，在最佳救助后，应付给救助责任的成本值为29×0.45=13.05。其次，我们在问题I的拉格朗日公式上测试我们的算法。在这个例子中，初始设置与前面的例子中相同。此外，我们确定拉格朗日乘数λ=1。Asnpqrtvwxy{|}~图20：以最佳救助金额和分配进行清算。0 100 200 300 400 500 600 700 800 900 10000204608100迭代支付向量节点阳极B节点CNode D（a）支付向量。0 100 200 300 400 500 600 700 800 900 10000246810迭代现金注入向量节点阳极b节点CNode D（b）现金注入向量。图21：通过分布式算法的迭代，节点支付和现金注入的演变，该算法优化了注入现金的金额和分配。如图21（a）和图21（b）所示，支付向量收敛于[pA，pB，pC，pD]=[81,20,80,10]，现金注入向量收敛于[cA，cB，cC，cD]=[0,0,8.5,9.0]。这些都是最优的，通过直接求解LP（8）来验证。通过外部现金注入，借款人-贷款人网络在所有付款后缩减至图20。现在，未付债务总额为19美元，现金注入金额为17.5美元。因此，最优救助后的成本函数值为17.5+19×0.45=26.05。通过注入17.5美元，我们将未付债务总额减少35.55美元，并将总成本减少35.55美元- $17.5 = $18.05.从图20中我们可以看出，虽然A仍然处于违约状态，但在最佳救助策略中，我们选择不向A注入任何现金。原因是，如果我们向图中的A注入一些现金x美元。

20，未付负债总额将减少x美元，因此成本函数的未付负债期限将减少0.45x，即，总体成本函数的价值将实际增加x- 0.45x=0.55x。6.3.2示例2：核心成熟网络在本节中，我们检查分布式算法的实用性。如第4节所述，我们假设美国银行间网络被很好地建模为一个核心-外围网络，由15家高度互联的银行组成，大多数其他银行与之连接[51]。我们在图13所示的模拟核心-外围网络上测试LP（8）的分布式算法。核心网络由15个完全连接的核心节点组成。每个核心节点有70个对应的外围节点，这些节点只欠这个核心节点钱。对于两个核心节点i和j的每一对，我们将lija设置为均匀分布在[0,10]中的随机数。对于核心节点i及其外围节点k，LKII设置为均匀分布在[0,1]中。所有这些义务在统计上是独立的。资产向量为e=0。此外，对于LP（8）中的i=1、2、··、N和λ=1，我们假设wi=0.3。我们从这个分布中提取了核心-外围网络的100个独立样本。因此，这些样本都具有相同的拓扑结构，但可靠性不同。

我们在初始条件y（0）=z（0）=q（0）=0.0 0.5 1 1.5 2 2.5 3x 1060510152003540迭代次数频率图22：δ=δ=10的核心外围网络的迭代次数-7.步长为β=0.01。分布式算法的停止准则是max{ky（t+1）-~y（t）k∞, k~z（t+1）-~z（t）k∞} < 10-7.设Td为我们的分布式算法计算出的总成本函数W+λC的值，设Tl为以集中方式直接求解线性规划得到的相应值。在该停止标准下，相对误差定义为| Td- Tl |/Tl，小于10-6对于我们模拟中的每个样本。迭代次数如图22所示。平均迭代次数为4.98×10。此外，从图22可以看出，在大多数情况下，算法在10次迭代内终止。每次迭代花费的时间包括两部分：计算时间和在节点之间传递消息所需的时间。在每次迭代中，节点需要向一组邻居发送两次信息：步骤1和2。注意，在步骤3中，停止符号BI被传输到中央节点。然而，节点无需在下一次迭代之前等待响应。因此，我们不将其计入一次迭代中的通信延迟。从洛杉矶到纽约需要13.2毫秒的光照，这是大陆上两个金融机构之间可能最长的距离。因此，一次迭代中的传播延迟可以粗略估计为13.2ms×2=26.4ms。因此，在大多数情况下，算法将在26.4ms×10=7.3h内终止，平均运行时间将低于26.4ms×4.98×10=3.65h。在夜间或周末运行这些计算的应用程序中，这些运行时间是可以接受的。

请注意，与这些通信时间相比，每个节点的计算时间可以忽略不计，因此我们在这些估计中忽略了它。另一种可能的设置是每个机构提供一台客户端计算机，我们将这些计算机集中在一个房间里。假设该房间中最长的网络电缆为100米，每次迭代的传播延迟约为2×100/（3×10）=6.67×10-7秒。对于计算时间，我们只分析核心节点，因为外围节点没有借款人，只有一个债权人，所以外围节点的计算时间比核心节点小得多。通常，乘法决定计算时间。在每次迭代中，一个核心节点计算其所有债权人j的qj（t）∏ij、∏ijpi（t）和qj（t+1）ij。由于核心网络是一个具有15个核心节点的完全连接的网络，一个核心节点有14个债权人，因此每次迭代的乘法次数少于50次。假设每次乘法需要500个cpu周期，客户端计算机上的cpu为3GHz，那么每次迭代的计算时间约为50×500/（3×10）=8.33×10-6秒。因此，在大多数情况下，算法在（8.33×10）以内终止-6+ 6.67 × 10-7) × 10≈ 10秒。通过将系统中所有金融机构的客户端计算机集中在一起，我们可以显著减少分布式算法的运行时间，从而使0 2000 4000 6000 10000 12000 14000051015202530迭代次数频率图23：δ=δ=10的核心外围网络的迭代次数-3.一天内可以轻松运行多次。在监控应用程序中，我们的目标可能是近似计算付款，而不是精确计算。在这种情况下，可以通过放宽终止容差来缩短运行时间。我们将停止标准设置为max{ky（t+1）-~y（t）k∞, k~z（t+1）-~z（t）k∞} < 10-3.

在此停止标准下，相对误差| Td- Tl |/Tl，在我们的模拟中，每个样本约为1%。图23示出了迭代次数。平均人数为4260人。在大多数情况下，迭代次数少于10000次。通过相似分析，非同址场景的平均运行时间为26.4ms×4260≈ 2分钟。在大多数情况下，算法将在26.4ms×10内终止≈ 4.4分钟。如果我们将所有金融机构的客户端计算机集中在一起，算法将在（8.33×10）内终止-6+ 6.67 × 10-7) × 10≈ 0.1秒。上述运行时间分析是针对问题I的拉格朗日公式，其中λ是一个常数。在问题I中，λ是一个也需要收敛的对偶变量。因此，问题I的分布式算法的运行时间将大于其拉格朗日公式的运行时间。从图19和图21中，我们观察到，在相同的停止容差下，问题II的分布式算法的迭代次数大约是其拉格朗日公式迭代次数的10倍。因此，对于问题I，为了计算准确的支付向量，算法将在约70小时内终止（对于非同位场景），并在100秒内终止（对于同位场景）。为了在1%误差范围内获得付款，对于非同址和同址场景，该算法将在大约44分钟n和1秒钟内终止。7结论在这项工作中，我们开发了一个线性规划，以在一个周期的非动态金融系统中获得最佳的现金注入政策，最小化未付负债的加权和。我们进一步建议重新称重l最小化算法基于此线性规划和贪心算法，以找到使系统中的默认数量最小化的现金注入分配策略。

通过构造三种可以直接计算最优解的拓扑结构，我们对两种算法进行了测试，并通过仿真表明，重新加权的结果是正确的l最小化算法接近最优，贪婪算法的性能在很大程度上取决于网络拓扑。我们还使用三种随机网络对这两种算法进行了比较，对于这三种随机网络，最优解是不可用的。此外，我们还提出了一种基于对偶的分布式算法来求解线性规划。分布式算法是迭代的，基于每个节点及其邻居之间的消息传递。不需要集中收集大量数据，每个参与机构都避免向其他机构披露其专有图书信息。仿真结果证明了分布式算法的收敛性和实用性。我们还考虑了机构到期时的资本是具有已知分布的随机向量的情况。我们开发了一个随机线性规划来寻找最优的现金注入政策，以最小化对未付债务加权和的期望。为了解决这个问题，我们提出了两种基于蒙特卡罗抽样的算法：Benders分解算法和投影随机梯度下降算法。此外，我们还证明了全有或全无支付机制的引入将最优现金注入分配问题转化为一个NP难的混合整数线性规划。

然而，我们通过使用优化软件包CVX[33,32]的模拟表明，对于与美国银行网络规模相当的网络规模，这个问题可以在几秒钟内准确解决。附录A计算清算支付向量的三种算法的比较。1比例支付机制[20]假设破产成本为零，并提出了三种确定清算支付向量的方法：定点算法、实际违约算法和优化方法。在本节中，我们首先介绍和分析这三种方法，然后比较它们在不同网络拓扑下的计算时间。A.1.1固定点算法通过定义，清算支付向量是以下映射的固定点：Φ（p）=min{（πTp+e），\'p}。其中，两个向量的最小值为分量。在[20]中规定的某些温和假设下，固定点是唯一的。它可以通过以下算法迭代找到[20]。定点算法：1。初始化：设置p←“p，k← 0，并根据精度要求将停止公差δ设置为较小的正数。2.pk+1← Φ（pk）。如果kpk+1- 库尔德工人党∞< δ、 停止并输出清算支付向量pk+1；否则，设置k← k+1，然后转到第2步。在每次迭代中，计算复杂度由∏Tp决定，即Θ（N）。迭代次数在很大程度上取决于网络拓扑结构和负债金额。A.1.2虚拟违约算法[20]第3.1节提出了虚拟违约算法。基本思路是首先假设所有节点全额支付债务。如果在这种假设下，每个节点都有足够的资金全额支付，那么算法终止。如果一些节点没有足够的资金全额支付，这意味着即使所有其他节点全额支付，这些节点也将默认。

在算法验证期间识别的此类默认值称为一阶默认值。在第二次迭代中，我们假设只出现一阶默认值。每个非违约节点k全额支付，即pk=`pk；每个默认节点都会支付其所有可用资金，即pi=NXj=1∏jipj+ei。如果在第二次迭代期间没有新的默认节点，则算法终止。否则，新的默认节点称为二阶默认值，我们继续进行第三次迭代。在第三次迭代中，我们假设出现了一阶和二阶默认值。我们计算新的支付向量，然后再次检查defaultingnodes集。我们不断迭代，直到没有新的默认值出现。由于系统中有N个节点，该算法保证在N次迭代中终止。具体的默认算法如下。虚构的默认算法：1。初始化：p←“p，k← 1和D（0）← .2.对于所有节点i，计算它们的收入和义务之间的差异：v（k）i←NXj=1∏jip（k）j+ei- “pi3。将D（k）定义为默认节点集：D（k）=ni:v（k）i<0o。4.如果D（k）=D（k-1） ，终止。5.否则，设置p（k+1）i← “我只想6∈ D（k）。尽管我∈ D（k），通过求解以下方程组来计算支付额p（k+1）i:p（k+1）i=ei+Xj∈D（k）πjip（k+1）j+Xj6∈尽管我∈ D（k）6。设定k← k+1并转至步骤2。在实际默认算法的每次迭代中，计算复杂性主要取决于第5步中线性方程的求解。这些方程中的未知数和方程的个数都等于D（k）中的元素个数。在最坏的情况下，系统中默认节点的数量与N的顺序相同。