Multiple loan repayment => Optimization problem What prompted this question was that I was reading advice on paying down multiple loans and it was suggested that the optimal strategy was to pay down the highest interest rate loan first, which does not seem entirely accurate. Instead it seems that for a single loan the time required to pay the loan can be approximated by the solution to the equation
$$ P \exp( r t ) = \beta  t $$
with a solution
$$ t = -\left(\frac{1}{r}\right) W\left( - \frac{P r}{\beta} \right) $$
(where $W$ is the Lambert W function). The total cost of repaying the loan being
$$ c_i = \beta_i t = -\left(\frac{\beta_i}{r_i}\right) W\left( - \frac{P_i r_i}{\beta_i} \right) $$
However, for $n$ loans with unique $\beta_i$, $r_i$, and $P_i$, I can't figure out how to structure the optimization expression if I want to minimize
$$ C = \sum_{i}^{n} c_i $$
subject to the constraints that $\beta_i >= 0$ and $B = \sum_{i}^{n} \beta_i$
Any suggestions?
 A: You can form the optimization problem as
$$\begin{align*}\min_{\beta}\quad&-\sum_{i=1}^{n}\left(\frac{\beta_i}{r_i}\right)W\left(-\frac{P_i r_i}{\beta_i}\right)\\
\text{s.t.}\quad&\beta_i\geq eP_ir_i\\
&\sum_{i=1}^{n}\beta_i=B.\end{align*}$$
This has Lagrangian
$$\mathcal{L}(\beta,\mu,\lambda)=-\sum_{i=1}^{n}\left(\frac{\beta_i}{r_i}\right)W\left(-\frac{P_i r_i}{\beta_i}\right)+\sum_{i=1}^{n}\mu_i(eP_ir_i-\beta_i)+\lambda\left(\sum_{i=1}^{n}\beta_i-B\right).$$
The constraints are linear, so the linear constrain qualification is satisfied, and so the Karush-Kuhn-Tucker necessary conditions must hold. These are
$$\begin{align*}
\nabla_{\!\beta}\,\mathcal{L}(\beta,\mu,\lambda)&=0\\
\mu_i(\beta_i-eP_ir_i)&=0\\
\mu&\geq 0\\
\beta_i&\geq eP_ir_i.
\end{align*}$$
If one performs the differentiation, it can be shown that the first constraint is equivalent to
$$\frac{1}{r_i}\cdot\frac{\left[W\left(-\frac{P_i r_i}{\beta_i}\right)\right]^2}{W\left(-\frac{P_i r_i}{\beta_i}\right)+1}+\mu_i-\lambda=0$$
which is quadratic in $W\left(-\frac{P_i r_i}{\beta_i}\right)$, which we set to $x_i$. We have $x_i^2=(\lambda-\mu_i)r_i(1+x_i)$, from which we obtain
$$x_i=\frac{(\lambda-\mu_i)r_i}{2}\left[1\pm\sqrt{1+\frac{4}{(\lambda-\mu_i)r_i}}\right]$$
Now, either $\mu_i=0$, or else $\beta_i=eP_i r_i$, based on the second KKT condition (the complementary slackness condition). In the first case, we have
$$W\left(-\frac{P_i r_i}{\beta_i}\right)=\frac{\lambda r_i}{2}\left[1\pm\sqrt{1+\frac{4}{\lambda r_i}}\right]$$
which implies
$$\beta_i={P_i r_i}\frac{\exp\left(\frac{\lambda r_i}{2}\left[-1\mp\sqrt{1+\frac{4}{\lambda r_i}}\right]\right)}{\frac{\lambda r_i}{2}\left[-1\mp\sqrt{1+\frac{4}{\lambda r_i}}\right]}$$
which, since $\beta_i\geq eP_i r_i\geq 0 $ and $\lambda\geq 0$ forces the sign of $\mp$ to be $+$. So when $\mu_i=0$, we have
$$\beta_i={P_i r_i}\frac{\exp\left(\frac{\lambda r_i}{2}\left[\sqrt{1+\frac{4}{\lambda r_i}}-1\right]\right)}{\frac{\lambda r_i}{2}\left[\sqrt{1+\frac{4}{\lambda r_i}}-1\right]}.$$
and when $\mu_i>0$, we have $\beta_i = eP_i r_i$.
When $\beta_i = eP_i r_i$, this gives $c_i=\frac{\beta_i}{r_i}$, which is the cost when the loan is paid off at the minimum rate that can be paid off ($eP_i r_i $) without it growing too large to pay off at all. Then we have to choose for each loan whether to pay the minimum rate ($\mu_i=0$) or else pay at a rate roughly proportional to the principal $P_i$, except scaled by a factor which is a function of $r_i$, to account for different interest rates.
Now, to get an actual solution you would need to solve the equation
$\sum_{i\in \mathcal{P}}\beta_i=B$ for $\lambda$, where $\mathcal{P}=\{i:\mu_i=0\}$ is the set of loans we are paying off more frequently than the minimum rate. This would have to be solved numerically for each possible choice of $\mathcal{P}$.
But there is a special case where $r_i=r$ for all $i$. In that case this equation is
$$\sum_{i\in\mathcal{P}}{P_i r}\frac{\exp\left(\frac{\lambda r}{2}\left[\sqrt{1+\frac{4}{\lambda r}}-1\right]\right)}{\frac{\lambda r}{2}\left[\sqrt{1+\frac{4}{\lambda r}}-1\right]}=B$$
which can be shown to have solution
$$\lambda=-\frac{1}{r}\cdot\frac{\left[W\left(-\frac{r}{B}\sum_{i\in\mathcal{P}}P_i\right)\right]^2}{W\left(-\frac{r}{B}\sum_{i\in\mathcal{P}}P_i\right)-1}$$
which then gives $\beta_i=B\frac{P_i}{\sum_{i\in\mathcal{P}}P_i}$, i.e. the loan is repaid at a rate out of the rate of income $B$, but proportional to the current principal $P_i$ for the loan.
This gives quite a neat expression for the objective explicitly:
$$\begin{align*}\sum_{i\not\in\mathcal{P}}eP_i-\sum_{i\in\mathcal{P}}\left(\frac{B\frac{P_i}{\sum_{i\in\mathcal{P}}P_i}}{r_i}\right)W\left(-\frac{P_i r}{B\frac{P_i}{\sum_{i\in\mathcal{P}}P_i}}\right)&=e\sum_{i\not\in\mathcal{P}}P_i-\sum_{i\in\mathcal{P}}\frac{B}{r}\frac{P_i}{\sum_{i\in\mathcal{P}}P_i}W\left(-\frac{r}{B}\sum_{i\in\mathcal{P}}P_i\right)\\
&=e\sum_{i\not\in\mathcal{P}}P_i-\frac{B}{r}W\left(-\frac{r}{B}\sum_{i\in\mathcal{P}}P_i\right)\end{align*}$$
Now, the constraint can be written as
$$B=\sum_{i\not\in\mathcal{P}}eP_i r+\sum_{i\in\mathcal{P}}B\frac{P_i}{\sum_{i\in\mathcal{P}}P_i}=\sum_{i\not\in\mathcal{P}}eP_i r+B$$
from which it is clear that we must set $\mathcal{P}$ to be all of the loans.
Thereby, the minimum cost is $-\frac{B}{r}W\left(-\frac{r}{B}\sum_{i=1}^{n}P_i\right)$, with minimizer $\beta_i=B\frac{P_i}{\sum_{i=1}^{n}P_i}$.
So, the advice isn't true. It's actually a good idea to evenly divide the paying-off between the loans proportional to the principal that remains in each.
It's also quite easy to think about the case where $r_i$ is not the same for every loan. Although the solution to the equation for $\lambda$ is difficult, we can still think of a counter-example: if a loan has an extraordinary rate $r_i\to\infty$ then you'd want to pay it off as quickly as possible if you could, regardless of the principal. In that case, you can see how the interest rate factor in the expression for $\beta_i$ dominates over the $P_i$ since
$$\lim_{r_i\to\infty}r_i\frac{\exp\left(\frac{\lambda r_i}{2}\left[\sqrt{1+\frac{4}{\lambda r_i}}-1\right]\right)}{\frac{\lambda r_i}{2}\left[\sqrt{1+\frac{4}{\lambda r_i}}-1\right]}=\infty.$$ But we'd expect that for similar interest rates, the solution will still be similar to the equal rates case, in the sense that we'd want to be paying off all loans at once.
So, to conclude, the advice is not always correct: you are right.
