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

我们使用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节类似，只是λ在每次迭代时都不会更新，因为λ是固定且给定的。