  This paper studies the problem of optimally allocating a cash injection into
a financial system in distress. Given a one-period borrower-lender network in
which all debts are due at the same time and have the same seniority, we
address the problem of allocating a fixed amount of cash among the nodes to
minimize the weighted sum of unpaid liabilities. Assuming all the loan amounts
and asset values are fixed and that there are no bankruptcy costs, we show that
this problem is equivalent to a linear program. We develop a duality-based
distributed algorithm to solve it which is useful for applications where it is
desirable to avoid centralized data gathering and computation. We also consider
the problem of minimizing the expectation of the weighted sum of unpaid
liabilities under the assumption that the net external asset holdings of all
institutions are stochastic. We show that this problem is a two-stage
stochastic linear program. To solve it, we develop two algorithms based on:
Benders decomposition algorithm and projected stochastic gradient descent. We
show that if the defaulting nodes never pay anything, the deterministic optimal
cash injection allocation problem is an NP-hard mixed-integer linear program.
However, modern optimization software enables the computation of very accurate
solutions to this problem on a personal computer in a few seconds for network
sizes comparable with the size of the US banking system. In addition, we
address the problem of allocating the cash injection amount so as to minimize
the number of nodes in default. For this problem, we develop two heuristic
algorithms: a reweighted l1 minimization algorithm and a greedy algorithm. We
illustrate these two algorithms using three synthetic network structures for
which the optimal solution can be calculated exactly. We also compare these two
algorithms on three types random networks which are more complex.
