我们使用W*（e，c）表示未偿付负债加权和的相应最小值。如果e是一个随机向量，那么W*（e，c）是一个随机变量。给定现金总量C，我们的目标是找到最佳现金分配策略C，以最小化对未支付负债加权和的预期。这可以表示为以下两阶段随机LP:mincEe[W*（e，c）]（26）根据≤ C、 C≥ 0，其中*（e，c）=minpwT（\'p- p） （27）以0为准≤ P≤“p，p≤ πTp+e+c。即使已知e的联合分布，p的分布*（e，c）和W*（e，c）不能以封闭形式计算。为了解（26），我们取资产向量的M个独立样本，表示为ase、e、···、eM，并使用mmxm=1W*（em，c）近似为Ee[W*（e，c）]。根据弱大数定律，当M足够大时，样本平均值是Ee[W]的良好估计*（e，c）]。这激发了近似情商。（26）如下所示：mincMMXm=1W*（em，c）（28）根据≤ C、 C≥ 0.与定理1类似，优化问题（27）和（28）可以组合成一个LP:maxc，pmMXm=1wTpm（29）受C约束≤ C、 C≥ 0,0 ≤ 下午≤p，对于m=1,2,m,pm≤ πTpm+em+c，对于m=1,2，··，m。由于c和pm对于m=1,2，··，m都是N维向量，LP（29）包含MN+N变量。求解具有mn+N个变量的LP的计算复杂度为O（（mn+N））[53]。为了达到高精度，M需要是一个大的数字。如果我们想直接求解Lp（29），那么计算量很大。内存复杂度为O（MN），对于较大的M和N也可能是禁止的。因此，需要高效的算法来求解LP（29）。5.1 Benders分解如果现金注入向量c是固定的，那么LP（29）可以分成M个较小的独立LP，每个样本em一个，每个样本em可以独立求解每个pm。

在这种情况下，我们不是用MN变量求解anLP，而是用N个变量求解M个LP，这显著降低了计算复杂度。受此启发，我们将Benders分解应用于LP（29）。Benders分解（见[6,50,38]）对c和pm（m=1,2，·m，m）进行了划分，并允许我们在每个步骤中用固定的c进行迭代。事实上，对于我们的问题，由于（29）的一些特殊性质，Benders分解可以进一步简化。从引理1的证明中，我们知道，对于任何固定c，pmis的可行区域都是非空的。因此，（29）相当于以下问题：maxcV（c）（30）服从toTc≤ C、 C≥ 其中v（c）=maxpmMXm=1wTpm（31）主题主题主题≥ 0，对于m=1，2，··，m，pm≤p，对于m=1,2，··，m，（32）pm≤ πTpm+em+c，对于m=1，2，···，m.（33）我们让u，··，uMbe为m约束的对偶变量（32），我们让ν，··，νMbe为m约束的对偶变量（33）。然后可以从以下对偶问题中得到V（c）：V（c）=minum，νmMXm=1\'pTum+emTνm+cTνm（34）以um为准≥ 0，对于m=1，2，··，m，νm≥ 0，对于m=1，2，··，m，νm≥ πνm+w- um，对于m=1,2，··，m。请注意，由于V（c）使受LP（34）约束的LP（34）的目标函数最小化，我们认为V（c）是受这些约束的该目标函数的最大下界。因此，LP（30）被等价地重写为LP（34）目标函数下界的最大化，受LP（30）和LP（34）的约束：maxc，θ（35）受toTc约束≤ C、 C≥ 0,θ ≤MXm=1\'pTum+emTνm+cTνm（36）对于（34）可行区域内的所有（um，νm）。LP（35）是（29）的等效版本，具有数量有限的（36）形式的约束，因为来自LP（34）可行区域的每对（um，νm）必须满足约束（36）。

关键思想是通过忽略除少数约束（36）外的所有约束来解决（35）的放松版本。假设这个松弛程序的最优解是（c）*, θ*). 如果解满足所有忽略的约束，则找到了最优解；否则，我们通过用固定的c=c求解（34）来生成一个新的约束*此外还有一个轻松的问题。以下是Benders分解算法的总结：1。初始化：设置θ← -∞, K← 0，c← 0，l← 0.2. 修正cl，求解M=1,2，···，M的以下M个子程序：Vm=minuM，νmMXm=1\'pTum+emTνm+clTνm以um为准≥ 0，对于m=1，2，··，m，νm≥ 0，对于m=1，2，··，m，νm≥ πνm+w- um，对于m=1,2，··，m.表示溶液为（um*, νm*), 对于m=1，2，··，m.3。如果mxm=1Vm=θl，则终止，CLI为最佳值。4.设定l← l+1，K← K+1，（um（K），νm（K））← （微米）*, νm*), 对于m=1，2，··，m.5。解决以下主要问题：maxc，θ（37）subject toTc≤ C、 C≥ 0,θ ≤MXm=1\'pTu（k）m+emTν（k）m+cTν（k）m对于k=1，2，··，k.将溶液表示为（c*, θ*). 设θl← θ*, 氯← C*. 然后进入第2步。在该算法中，在每次迭代中，我们用N个变量求解M+1个LPs，而不是用MN+N个变量求解一个LP，这节省了计算复杂度和内存开销。注意，与Benders分解的一般形式（见[50]第2.3节）相比，上述算法更简单。由于LP（31）总是可行且有界的，因此在[50]中没有必要考虑约束（22b）。[50]中的步骤（2\'）也可以移动，因为（37）总是有界的。5.2投影随机梯度下降在本节中，我们引入投影随机梯度下降法来求解（26）。这是一个在线算法，它允许我们一次处理一个样本，而无需构建一个庞大的线性程序。

其基本思想是，对于每个样本em，我们沿着W的负梯度方向移动溶液c*（em，c）关于c，然后将结果投影到（26）约束定义的集合上。如果步长选择得当，该过程将收敛到最优解[11]。算法如下。在迭代m，1。对资产向量em.2进行采样。沿着W的负梯度移动c*（em，cm）-1） 根据以下等式：~cm=cm-1.- γmcW*（em，cm）-1). (38)3. 将cmas设置为∧cms在集合{c:1Tc=c，c上的投影≥ 0}.根据[11]，步长γm应满足以下条件：∞Xm=1（γm）<∞ 和∞Xm=1γm=∞. 因此，一个合适的选择是γm=1/m*（em，cm）-1） =wT`p- U（em，cm）-1） ，其中u（em，cm-1） =maxpwTp（39）受0约束≤ P≤“p，p≤ ∏Tp+em+cm-1.获得W的梯度*（em，cm）-1） 在第二步中，我们考虑LP（39）的对偶问题：U（em，cm-1） =最小u，νh′pTu+emTν+c（m-1） Tνi（40）受u≥ 0,ν ≥ 0,ν ≥ πν+w- u.假设（μ）*, ν*) 是（40）的解，我们有cW*（em，cm）-1) = -cU（em，cm）-1) = -ν*.在第3步中，我们使用以下二次程序来确定cm的投影：cm=arg minckc-~cmk（41）受toTc=C，C影响≥ 0.附录C给出了二次规划（41）的快速算法。因此，在该投影随机梯度下降法的每次迭代中，我们求解一个N变量LP和一个N变量二次规划，而不是求解包含MN+N变量的LP（29）。该算法的内存效率很高，因为除了c.6分布式算法的当前解决方案外，它不需要存储。对于问题I，有比例支付机制。我们在定理1中证明，没有破产成本的问题I相当于一个线性规划，因此，对于任何网络拓扑，都可以使用标准LP解算器精确求解。

然而，在某些情况下，这种方法可能不切实际或不可取，因为它要求解算器了解整个网络结构，即每个机构的外部净资产，以及每个机构欠彼此的金额。现在，我们将我们的框架调整到需要避免集中数据收集和计算的应用程序中。我们提出了一种分布式算法来求解线性规划。该算法是迭代的，基于每个节点及其邻居之间的消息传递。在算法的每次迭代中，每个节点只需要从其邻居接收少量数据，执行简单的计算，并向其邻居发送少量数据。在消息传递过程中，任何节点都不会向任何其他节点透露有关其资产价值、欠其他节点的金额或其他节点欠下的金额的任何专有信息。我们的算法既可用于监控金融网络，也可用于模拟压力测试场景。监管机构可以通过审计来强制执行流程的完整性。虽然该算法比标准的集中式LP解算器慢，但仿真结果表明，该算法适用于我们将其建模为一个包含15个核心节点和1050个外围节点的核心-外围网络的美国银行系统。6.1问题16。1.1分布式算法为了开发LP（4-6）的分布式算法，我们制定了它的对偶问题，并通过梯度下降法解决它，因为对偶问题具有更简单的约束，易于分解。

事实证明，梯度下降法的每次迭代只涉及局部计算，这使得分布式实现成为可能。为了将梯度下降法应用于对偶问题，我们需要（4）中的目标函数是严格凹的，这将保证对偶问题在任何点都是可微的[25]。然而，LP（4）的目标函数不是严格凹的，因此我们采用了近似优化算法[43,8]。基本思想是在目标函数中加入二次项。二次项将收敛到零，这样我们就可以在不改变最优解的情况下使目标函数严格凹。我们引入两个N×1向量y和z，并添加两个二次项skp- yk=NXi=1（π- yi），kc- zk=NXi=1（ci- zi）至（4）。然后我们继续如下。算法P：在第t次迭代中，P1）固定y=y（t）和z=z（t），并最大化关于P和c的目标函数：maxp，cwTp- 金伯利进程- yk- kc- zk（42）受toTc约束≤ C、 （43）C≥ 0,0 ≤ P≤“p，p≤ πTp+e+c.（44）注意，由于目标函数是严格凹的，因此存在唯一解。表示为p*c*.o P2）集y（t+1）=p*, z（t+1）=c*.[8]中的命题4.1证明了算法P将收敛到LP（4-6）的最优解。6.1.2算法P的实现步骤P1，对于固定的y和z，（42）的目标函数是严格凹的，因此对偶问题在任何点都是可微的[25]。因此，我们可以使用梯度下降法解决对偶问题，如下所示。设标量λ和N×1向量q分别为约束（43）和（44）的拉格朗日乘子。我们将拉格朗日定义如下：L（p，c，λ，q，y，z）=wTp- λ（1Tc）- C）- qT（（IN×N）- πT）p- E- c）- 金伯利进程- yk- kc- zk（45），其中λ和q是非负的，并且在N×N单位矩阵中。

我们进一步展开（45）：L（p，c，λ，q，y，z）=NXi=1wipi- λNXi=1ci+λC-NXi=1qi（π-NXj=1∏jipj- 工程安装- （ci）-NXi=1（π- （易）-NXi=1（ci- (46)-NXi=1圆周率- （wi）- qi+2yi+NXj=1qj∏ij）pi-NXi=1词- (齐)- λ+2zi）ci+NXi=1秋- 易- 子+ λC（47）为了从式（46）中获得式（47），我们使用以下等式：NXi=1NXj=1qi∏jipj=NXi=1NXj=1qj∏ijpi。然后对偶问题的目标函数是：D（λ，q，y，z）=max0≤P≤“p，c≥0L（p，c，λ，q，y，z）（48）在等式（47）中，如果节点i不是j的借贷者，则术语qj∏ij为0。因此，如果节点i从其借贷者处收到所有qj，则它可以确定计划和cit以实现拉格朗日L（p，c，λ，q，y，z）的最大值。给定y和z，则（42）的对偶问题是在拉格朗日乘子λ和q:minλ上最小化（48）≥0，q≥0D（λ，q，y，z）（49）对偶问题在任何点上都是可微的，因为原始的目标函数是严格相关的[25]。因此，梯度下降迭代可用于求解对偶问题。在迭代u时，λ=λ（u）和q=q（u）。那么在这一点上，D相对于λ和q的梯度是：Dλ=C- 1Tc（u），Dq=e+c（u）- （IN×N）- πT）p（u），其中p（u）和c（u）求解λ=λ（u）和q=q（u）：pi（u）=0如果π（u）<0如果π（u）>π（u）否则（50），其中π（u）=yi（t）+（wi- 齐（u）+Xj∈Ciqj（u）∏ij）和ci（u）=子（t）+（齐（u）- λ（u））+. （51）因此，考虑到λ和q的非负性，梯度下降方程为：λ（u+1）=“λ（u）- α（C）-NXi=1ci（u））#+，（52）图14：基于对偶的方法。齐（u+1）=齐（u）- β（ei+ci（u）- pi（u）+NXj=1∏jipj（u））+, 对于i=1，2，··，N（53），其中α和β是步长，[x]+=max{0，x}。对于固定的y和z，对偶更新将收敛到D为u的最小值→ ∞, 如果步长足够小[8]。从（52）中，我们注意到为了更新λ，所有N个节点都需要ci。

这意味着在每次操作t时，每个节点都应该向中心节点发送ci（u），以便中心节点可以更新λ并将其发送回系统中的每个节点。如果节点j不是节点i的借用者，则∏jipj（u）=0；否则，∏jipj（u）表示节点j在第u次迭代时支付给节点i的金额。因此，利用来自所有节点的∏jipj（u）信息，节点i能够基于（53）更新QI。6.1.3一种更有效的算法如图14所示，在该算法中，我们首先确定y和z，并通过迭代更新λ、q和p、c来解（42），直到它们收敛。然后我们更新y和z。这是一个两阶段迭代，可能会减慢整个算法的收敛速度，因为每个固定的y和z浪费了太多的双重更新[43]。为了避免两阶段迭代结构，我们考虑以下算法。算法A：在第t次迭代时，oA1）固定y=y（t）和z=z（t），最大化关于p和c的L，[p（t），c（t）]=arg max0≤P≤“p，c≥0L（p，c，λ（t），q（t），y（t），z（t））。B、 <=>w？@Cadefghijknjsklm OPuQRTtUpiV WiXiYijpiZ[\\] 我我T  ijk 1.易学图15：固定最大注入现金总量的分布式算法A的第t次迭代A2）用λ（t+1）=“λ（t）更新拉格朗日乘数λ（t+1）和q（t+1）- αC-NXi=1ci（t）！#+，（54）气（t+1）=齐（t）- β（ei+ci（t）- pi（t）+NXj=1∏jipj（t））+, 对于i=1,2，··，N（55）oA3）用[y（t+1），z（t+1）]=arg max0更新y和z≤P≤“p，c≥0L（p，c，λ（t+1），q（t+1），y（t），z（t））。在算法A中，我们对每个固定的y和z只更新一次拉格朗日乘子λ和q，而不是有限次的双重更新。以下定理保证了算法A的收敛性。定理5。

如果步长α和β足够小，算法A将收敛到LP（4-6）的最优解。定理5是[42]中命题4的一个扩展。6.1.4算法AAssume bian和Ciare的实现分别是节点i的借款人和债权人的集合。然后算法A的第t次迭代如下所示。1.对于每个节点i，fix yi=yi（t），zi=zi（t），λ=λ（t）和q=q（t），并计算piand ci:pi（t）=0如果π（t）<0如果π（t）>π（t），否则，其中π（t）=yi（t）+wi- 齐（t）+Xj∈Ciqj（t）πij, 安德西（t）=子（t）+（气（t）- λ（t））+.然后将∏ijpi（t）发送到每个节点j∈ Ci，并将更新后的Ci（t）发送到节点Nc。2.每个节点i从每个节点k接收∏kipk（t）∈ Biand更新气：气（t+1）=“气（t）+β（pi（t）- 工程安装- ci（t）-Xk∈Bi∏kipk（t））#+。然后每个节点i向每个节点k发送更新的qi（t+1）∈ 毕。节点n从所有节点i接收cifi并更新λ：λ（t+1）=“λ（t）+αNXi=1ci（t）- C！#+。然后节点nc将更新后的λ（t+1）发送给每个节点i.3。每个节点i从每个j接收qj（t+1）∈ Ciand从节点Nc接收λ（t+1），然后更新yi和zi:yi（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）- λ（t+1））。然后，每个节点i都会检查条件| yi（t+1）- |yi（t）|<δ和|zi（t+1）- ~zi（t）|<δ。如果两个条件都成立，节点i将bi设置为1；否则它会将bi设置为0。然后将bito发送到中心节点Nc。如果所有i的BI=1，则NCBI指示所有节点终止算法。这些步骤如图15所示。在第3步中，δ和δ是停止公差，通常根据精度要求设置为小正数。

在停止准则中，我们使用了y和z，而不是它们的投影y和z，因为y和z的收敛意味着拉格朗日乘子q和λ的收敛，而y和z的收敛并不意味着拉格朗日乘子q和λ的收敛。在算法A的实现中，我们包括一个中心节点。在每次迭代中，中心节点有两个函数。一种是在步骤2中求和ci（t）并计算λ（t+1）；另一个是测试步骤3中所有节点i的bi=1。对于这两种功能，中心节点只收集少量数据并执行简单计算。我们可以通过计算ci（t）之和并以分布式方式传递停止符号来完全排除中心节点，代价是在每次迭代中增加计算负担。,oijkNs UT伊齐比斯特 词图16：分布式算法A′的第t次迭代，其中包括优化注入的现金总量。6.2问题I的拉格朗日公式我们现在将基于对偶的分布式算法应用于问题I的拉格朗日公式LP（8）。请注意，现在λ表示注入现金金额在总体成本函数中的重要性。该算法与第6.1节类似，只是λ在每次迭代时都不会更新，因为λ是固定且给定的。

与（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的顺序相同。

在这种情况下，每次迭代的计算复杂度为O（N）[53]。与定点算法相比，实际默认算法具有更大的计算复杂度，并且如下文第a.1.4节所示，在几种网络拓扑上的运行时间更长。然而，实际默认算法的优点是，它保证在运行中终止。此外，与产生近似值的定点算法不同，实际违约算法将产生清算付款的准确值。A.1.3线性规划方法定义f（p）=NXi=1pi=1Tp，这是p的严格递增函数。通过[20]中的引理4，可以通过以下线性规划获得清算支付向量：maxptptp（57）服从0≤ P≤“p，p≤ πTp+e.求解LP的计算复杂度为O（N）[53]。A.1.4三种不同拓扑逻辑上的清算时间比较我们通过上述三种方法计算三种不同网络拓扑上的清算支付向量，并比较运行时间。第一个网络拓扑是一个具有1000个节点的完全连接的网络。所有债务金额和资产金额都是独立的随机变量，可统一分配2：使用定点算法、实际违约算法和线性规划，比较比例支付机制下清算支付向量计算的运行时间。定点算法虚拟默认算法LP methodave（s）stdev ave（s）stdev ave（s）stdev ave（s）stdev完全连接0.9128 0.1045 10.7341 0.7182 53.1725 11.8947核心-外围0.0869 0.0342 7.8213 1.2843 0.1964 0.0507线性链0.0462 0.0170 10.2574 1.0211 0.1610.0449in[0,1]。第二网络拓扑是图13所示的核心-外围网络。它包含15个完全连接的核心节点。每个核心节点有70个外围节点。

每个外围节点都有一个指向相应核心节点的链路。所有的义务量Li，jare都是独立的统一随机变量。对于每对核心节点i和j，义务量i均匀分布在[0,10]中。对于核心节点i及其外围节点k，义务量lkii均匀分布在[0,1]中。阿塞塔蒙特平均分布在[0,0.25]中。第三种网络拓扑是一个有1000个节点的长线性链网络。对于i=1，2，N- 1，债务金额Li（i+1）均匀分布在[0，10]中，对于其他i和j对，Lij=0。资产金额均匀分布在[0,1]中。对于每种类型的网络，我们生成100个样本。我们使用2.66GHz Intel Core2 Duo处理器P8800在个人计算机上运行Matlab代码。三种方法的平均运行时间和运行时间的样本标准偏差如表2所示。对于所有三种类型的网络，定点算法是最有效的。请注意，线性规划方法的计算时间是高度可变的，因为更简单的拓扑结构会导致∏成为稀疏矩阵，从而减少运行时间。A.2全有或全无支付机制A。2.1定点算法和虚拟默认算法我们现在假设“全有或全无”支付机制，节点i在有偿付能力的情况下支付“PIP”，而在违约的情况下不支付任何费用。因此，清算支付向量是映射ψ的固定点，定义如下：ψi（p）=\'piifNXj=1∏jipj+ei≥ ？pi0否则，我们通过以下算法迭代找到ψ（·）的固定点。定点算法：1。初始化：设置p←“p，k← 0.2. pk+1← ψ（pk）。

如果pk+1=pk，则停止并输出清算支付向量pk+1；否则，设置k← k+1并转至步骤2。事实上，在全有或全无支付机制下，这种定点算法可以解释为以下有效的默认算法。我们最初假设所有节点全额支付其债务，即p=`p。如果在此假设下，每个节点都有足够的资金全额支付，则算法终止。如果一些节点没有足够的资金全额支付，这意味着这些节点将默认表3：使用定点算法和混合整数线性规划，在全有或全无支付机制下计算清算支付向量的运行时间比较。定点算法/虚拟默认算法MILPave（s）stdev ave（s）Stdevf完全连接0.0092 0.0129 1.2204 0.0909核心-外围0.0242 0.0175 0.5338 0.0255线性链0.0279 0.0149 0.4700 0 0.0276，即使所有其他节点全额支付。我们将这些节点定义为一阶默认值。利用函数ψ（·），我们识别一阶违约并将其付款设置为零。在第二次迭代中，我们假设只出现一阶默认值。每个非违约节点k全额支付，即pk=`pk；每个defaultingnode i支付0，即pi=0。同样，通过函数ψ（·），我们确定了新的违约节点，它们被称为二阶违约，并将它们的支付设置为零。如果没有新的默认节点，算法终止；否则，我们继续第三次迭代。我们不断迭代，直到没有新的defaultsoccur，即pk+1=pk。由于系统中有N个节点，该算法保证在N次迭代中终止。在每次迭代中，计算复杂度由∏Tp决定，即Θ（N）。

因此，定点算法（有效默认算法）的计算复杂度为O（N）。A.2.2混合整数线性规划方法清算支付向量也可以通过求解MILP（20）得到，假设不会注入外部现金，即C=0。当C=0时，MILP（20）简化为以下MILP:maxp，C，dwTp（58）subject topi=\'pi（1- di），对于i=1，2，·N，\'pi-NXj=1∏jipj- 工程安装≤ 对于i=1,2,N,di∈ {0,1}，对于i=1,2，···，N.我们通过CVX[33,32]求解MILP（58）。A.2.3三种不同拓扑逻辑上的清算时间比较我们通过上述两种方法在第A.1.4节所述的三种网络拓扑上计算全部或无支付机制下的清算支付向量，并比较运行时间。与A.1.4节类似，我们生成了100个样本，并在带有2.66GHz Intel Core2 Duo处理器P8800的个人计算机上运行了Matlab代码。两种方法的平均运行时间和运行时间的样本标准偏差如表3所示。对于所有三种拓扑，定点算法比MILP方法更有效。表4：CVX代码中的参数。本文中CVX代码符号中的参数BAR¨pPi∏e ec cw wd dI in×NC总CB CVX代码用于求解MILP（20）。代码中出现的参数如表4所示。c v x s o l v e r mosekcv x be g inv a r i a b l e d（N）b inary%d e f a u l i a a b l e c（N）%现金终止（pbar\'* diag（w）* d）s u b j e c t图恩斯（1，N）* c<=c到t a l；c>=0；（Pi\'- （一）* 诊断（pbar）* d<=Pi\'* pbar+e+c- pbar；cvx endC二次规划（41）minckc的快速算法-~cmk（59）受试者toTc=C，（60）C≥ 0

（61）设标量κ和N×1向量ι分别为约束（60）和（61）的拉格朗日乘子。我们将拉格朗日定义如下：F（c，κ，ι）=kc-~cmk+κ（1Tc- C）- ιTc（62）然后是原始和对偶最优c*和（κ，ι）将满足以下Karush-Kuhn-Tucker（KKT）条件：cF（c，κ，ι）=0，（63）Tc=c，（64）c≥ 0, (65)ι ≥ 0，（66）ιici=0，对于i=1，2，···，N.（67）从KKT约束（63）中，我们得到了ci=~cmi- κ/2+ιi/2，对于i=1,2，·N如果cmi- κ/2>0，然后ci>0，因为ιi≥ 0.通过KKT约束（67），ιi=0。因此，ci=~cmi- κ/2.o 如果cmi- κ/2<0，ιi应为阳性，以确保ci≥ 0.由于ιici=0且ιi>0，ci=0.o如果cmi- κ/2=0，然后ci=ιi/2。既然ιici=0，我们就有了ci=ιi=0。总之，ci=max{cmi- κ/2，0}，对于i=1，2，···，N，其中κ由KKT约束确定（64）。参考文献[1]F.艾伦和D.盖尔。金融传染。政治经济学杂志，108（1）：1-332000。[2] H.阿米尼、R.康特和A.明卡。金融网络的抗传染能力。可从SSRN获得：http://ssrn.com/abstract=1865997，2010年12月1日。[3] K.阿南德、B.克雷格和G.冯·彼得。填补空白：网络结构和银行间传染。国际清算银行工作文件，4552014年8月。[4] K.阿南德、P.盖、S.卡帕迪亚、S.布伦南和M.威廉姆森。金融系统弹性的网络模型。英格兰银行第458号工作文件，2012年7月。[5] S.巴蒂斯顿、D.D.加蒂、M.加莱加蒂、B.格林沃尔德和J.E.斯蒂格利茨。联系风险：增加连通性、风险分担和系统性风险。《经济动力与控制杂志》，36（8）：1121-11412012。[6] J.F.本德斯。解决混合变量编程问题的分区程序。《数字主题》，4（1）：238-2521962年。[7] A.伯纳多、E.塔利和I.韦尔奇。一个最优政府救助的模型。

技术报告，工作论文系列，加州大学伯克利分校伯克利分校法律与经济项目，http://www.law.berkeley.edu/Files/bclbe/最佳救助模式0503。pdf，2011年5月3日。[8] D.P.Bertsekas和J.N.Tsitiklis。并行和分布式计算。新泽西州老塔潘（美国）；普伦蒂斯·霍尔公司，1989年。[9] L.布鲁姆、D.伊斯利、J.克莱因伯格、R.克莱因伯格和E.塔多斯。哪些网络对级联故障最不敏感？IEEE第52届计算机科学基础年会，第393-402页，2011年10月。[10] M.Boss、H.Elsinger、M.Summer和S.Thurner。银行间市场的网络拓扑。arXiv预印本cond mat/03095822003。[11] 博图。在线学习和随机近似。神经网络在线学习，第9-42页。剑桥大学出版社，1998年。[12] E.J.坎迪斯、M.B.沃金和S.P.博伊德。通过重新加权提高稀疏性l最小化。《傅立叶分析与应用杂志》，14（5-6）：877–9052008。[13] J.M'arquez Diez Canedo和S.Mart'nez Jaramillo。系统性风险的网络模型：银行系统压力测试。会计、财务和管理中的智能系统，16:97–1102009。[14] A.卡波尼和P-C.陈。金融网络中的系统性风险缓解。可从SSRN获得：http://ssrn.com/abstract=2293426，2013年7月13日。[15] R.Cifuntes、G.Ferrucci和H.S.Shin。流动性风险和传染。《欧洲经济协会杂志》，3（2-3）：556-5662005。[16] B.克雷格和G.冯·彼得。银行间分层和货币中心银行。《金融中介杂志》，2014年7月23:322–347。[17] H.Degryse和G.Nguyen。银行间风险敞口：比利时银行系统传染风险的实证检验。《国际中央银行杂志》，第123-171页，2007年6月。[18] G.Demange。金融网络中的传染：威胁指数。

欧洲夏季非经济理论研讨会，http://dev3.cepr.org/meets/wkcn/6/6692/papers/DemangeFinal.pdf，2011年7月4日。[19] G.Demange。金融网络中的传染：威胁指数。巴黎经济学院工作论文2012-02，2011年12月31日。[20] L.艾森伯格和T.H.诺伊。金融系统中的系统性风险。《管理科学》，47（2）：236–249，2001年2月。[21]M.Elliott、B.Golub和M.O.Jackson。金融网络和传染。可从SSRN 21750562013获得。[22]H.Elsinger、A.Lehar和M.Summer。使用市场信息进行银行系统风险评估。可从SSRN获得：http://ssrn.com/abstract=787929，2005年8月22日。[23]H.Elsinger、A.Lehar和M.Summer。银行系统的风险评估。《管理科学》，52（9）：1301-13142006。[24]M.法布迪。中介和自愿承担交易对手风险。技术报告，工作论文，芝加哥大学，2014年8月30日。[25]C.A.弗洛达斯。非线性和混合整数优化：基础和应用。牛津大学出版社，1995年。[26]V.Fourel、J.-C.H\'eam、D.Salakhova和S.Tavolaro。银行囤积流动性会产生多米诺骨牌效应：法国网络。法国银行第432号工作文件，2013年4月。[27]C.H.毛皮。银行间风险敞口：量化传染风险。《货币、信贷和银行杂志》，35（1）：111–128，2003年2月。[28]P.盖、A.霍尔丹和S.卡帕迪亚。复杂性、集中性和传染性。《货币经济学杂志》，58:453–470，2011年。[29]P.盖和S.卡帕迪亚。金融网络中的传染。皇家学会学报A：数学、物理和工程科学，466（2120）：2401–2423，2010年8月。[30]C.高蒂尔、A.莱哈尔和M.苏伊西。宏观审慎资本要求和系统性风险。《金融中介杂志》，第594-618页，2012年。[31]P.格拉斯曼和H.P.杨。

金融网络中传染的可能性有多大？《银行与金融杂志》，2014年。[32]M.格兰特和S.博伊德。非光滑凸规划的图实现。InV.Blondel、S.Boyd和H.Kimura，编辑，学习和控制的最新进展，控制和信息科学课堂讲稿，第95-110页。施普林格有限公司，2008年。http://stanford.edu/~boyd/graph_dcp。html。[33]M.格兰特和S.博伊德。CVX:Matlab严格凸规划软件，2.1版。http://cvxr.com/cvx，2014年3月。[34]G.哈哈哈。基于随机损失情景的银行系统传染效应度量。银行与信贷，波兰国家银行日记，2007年6:69–80。[35]G.Ha laj和C.Kok。使用模拟网络评估银行间传染。欧盟罗佩安中央银行工作文件系列，1506年，2013年1月。[36]A.G.霍尔丹和R.M.梅。银行生态系统中的系统性风险。《自然》，2011年1月20日，469:351–355。[37]D.in\'t Veld和I.van Lelyveld。寻找核心：银行间市场的网络结构。《银行与金融杂志》，2014年。[38]G.英芬格。随机线性规划的benders分解算法中的Monte carlo（重要性）抽样。运筹学年鉴，39（1）：69-951992。[39]Z.Li、X.Lin和I.Pollak。金融系统中系统性风险缓解的分布式算法。《IEEE全球信号与信息处理会议记录》，第1137-1137页，2013年12月。[40]Z.Li和I.Pollak。分散违约：为陷入困境的金融网络提供最佳救助政策。可从SSRN获得：http://ssrn.com/abstract=2148483，2012年9月18日。[41]Z.Li和I.Pollak。分散违约：为陷入困境的金融网络提供最佳救助政策。《IEEE声学、语音和信号处理国际会议论文集》，第6176-6180页，2013年5月。[42]X.Lin和N.B.Shro off。

具有多径路由的通信网络的效用最大化。技术报告，技术报告，普渡大学，https://engineering.purdue.edu/linx/文件。html，2004年。[43]X.Lin和N.B.Shro off。具有多路径路由的通信网络的效用最大化。IEEE自动控制学报，51（5）：766–7812006。[44]J.洛伦兹、S.巴蒂斯顿和F.施韦策。网络级联过程统一框架中的系统性风险。欧洲物理杂志B-凝聚态物质和复杂系统，71（4）：441-4602009。[45]S.Martinez Jaramillo、O.Pierez Pierez、F.Avila Embriz和F.Liopez Gallo-Dey。系统性风险、金融传染病和金融脆弱性。经济动力与控制杂志，34:2358–23742010。[46]B.G.蒙达卡。货币和金融危机期间的最优救助：一项连续博弈分析。奥弗斯洛大学经济系技术报告，http://www.sv.uio.no/econ/english/research/unpublished-works/working-papers/pdffiles/2002/Memo-27-2002。pdf，2002年9月17日。[47]M.Pr–opper、I.van Lelyveld和R.Heijmans。银行间支付流的网络描述。DNB第177号工作文件，2008年5月。[48]L.C.G.罗杰斯和L.A.M.维拉特。银行间网络的故障与救援。可从SSRN获得：http://ssrn.com/abstract=1932911，2011年9月23日。[49]L.C.G.罗杰斯和L.A.M.维拉特。银行间网络的故障与救援。《管理科学》，59（4）：882-8982013。[50]R.M.Van Slyke和R.Wets。L型线性规划及其在最优控制和随机规划中的应用。暹罗应用数学杂志，17（4）：638-663，1969年。[51]K.Soram–aki、M.L.Bech、J.Arnold、R.J.Glass和W.E.Beyeler。银行间支付流的拓扑结构。Physica A:统计力学及其应用，379（1）：317–3332007。[52]I.范·莱利维尔德和F.利多普。

荷兰银行业的银行间传染：敏感性分析。《国际中央银行杂志》，第99-133页，2006年7月。[53]Ye。线性规划的一种o（nl）势约化算法。数学规划，50（1-3）：239-2581991。