Mixing
Multiple loan repayment => Optimization problem
$begingroup$
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) Wleft( - 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) Wleft( - 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?
optimization
asked Jan 16 at 4:33
user1543042user1543042
330111
$endgroup$
|
show 1 more comment
$begingroup$
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) Wleft( - 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) Wleft( - 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?
optimization
asked Jan 16 at 4:33
user1543042user1543042
330111
$endgroup$
$begingroup$
What are your decision variables? $beta_i$ is a variable, but what else? The $W$ function is monotone over $[0,infty)$, so minimizing it can be achieved by minimizing its argument. If you know what the decision variables are, you might be able to make a similar observation about the actual objective and use it to remove the $W$ to get a linear objective.
$endgroup$
– nathan.j.mcdougall
Jan 16 at 5:03
$begingroup$
That is what I'm confused about... I control the allocation of $beta_i$
$endgroup$
– user1543042
Jan 17 at 1:51
$begingroup$
Okay, but what about $P$ and $r$, do you control those?
$endgroup$
– nathan.j.mcdougall
Jan 17 at 1:58
$begingroup$
no, they're constant
$endgroup$
– user1543042
Jan 17 at 2:15
$begingroup$
Everything is real and greater than 0
$endgroup$
– user1543042
Jan 17 at 4:14
|
show 1 more comment
$begingroup$
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) Wleft( - 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) Wleft( - 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?
optimization
asked Jan 16 at 4:33
user1543042user1543042
330111
$endgroup$
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) Wleft( - 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) Wleft( - 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?
optimization
optimization
asked Jan 16 at 4:33
user1543042user1543042
330111
asked Jan 16 at 4:33
user1543042user1543042
330111
asked Jan 16 at 4:33
user1543042user1543042
330111
asked Jan 16 at 4:33
user1543042user1543042
330111
asked Jan 16 at 4:33
user1543042user1543042
330111
330111
$begingroup$
What are your decision variables? $beta_i$ is a variable, but what else? The $W$ function is monotone over $[0,infty)$, so minimizing it can be achieved by minimizing its argument. If you know what the decision variables are, you might be able to make a similar observation about the actual objective and use it to remove the $W$ to get a linear objective.
$endgroup$
– nathan.j.mcdougall
Jan 16 at 5:03
$begingroup$
That is what I'm confused about... I control the allocation of $beta_i$
$endgroup$
– user1543042
Jan 17 at 1:51
$begingroup$
Okay, but what about $P$ and $r$, do you control those?
$endgroup$
– nathan.j.mcdougall
Jan 17 at 1:58
$begingroup$
no, they're constant
$endgroup$
– user1543042
Jan 17 at 2:15
$begingroup$
Everything is real and greater than 0
$endgroup$
– user1543042
Jan 17 at 4:14
|
show 1 more comment
$begingroup$
What are your decision variables? $beta_i$ is a variable, but what else? The $W$ function is monotone over $[0,infty)$, so minimizing it can be achieved by minimizing its argument. If you know what the decision variables are, you might be able to make a similar observation about the actual objective and use it to remove the $W$ to get a linear objective.
$endgroup$
– nathan.j.mcdougall
Jan 16 at 5:03
$begingroup$
That is what I'm confused about... I control the allocation of $beta_i$
$endgroup$
– user1543042
Jan 17 at 1:51
$begingroup$
Okay, but what about $P$ and $r$, do you control those?
$endgroup$
– nathan.j.mcdougall
Jan 17 at 1:58
$begingroup$
no, they're constant
$endgroup$
– user1543042
Jan 17 at 2:15
$begingroup$
Everything is real and greater than 0
$endgroup$
– user1543042
Jan 17 at 4:14
$begingroup$
What are your decision variables? $beta_i$ is a variable, but what else? The $W$ function is monotone over $[0,infty)$, so minimizing it can be achieved by minimizing its argument. If you know what the decision variables are, you might be able to make a similar observation about the actual objective and use it to remove the $W$ to get a linear objective.
$endgroup$
– nathan.j.mcdougall
Jan 16 at 5:03
$begingroup$
What are your decision variables? $beta_i$ is a variable, but what else? The $W$ function is monotone over $[0,infty)$, so minimizing it can be achieved by minimizing its argument. If you know what the decision variables are, you might be able to make a similar observation about the actual objective and use it to remove the $W$ to get a linear objective.
$endgroup$
– nathan.j.mcdougall
Jan 16 at 5:03
$begingroup$
That is what I'm confused about... I control the allocation of $beta_i$
$endgroup$
– user1543042
Jan 17 at 1:51
$begingroup$
That is what I'm confused about... I control the allocation of $beta_i$
$endgroup$
– user1543042
Jan 17 at 1:51
$begingroup$
Okay, but what about $P$ and $r$, do you control those?
$endgroup$
– nathan.j.mcdougall
Jan 17 at 1:58
$begingroup$
Okay, but what about $P$ and $r$, do you control those?
$endgroup$
– nathan.j.mcdougall
Jan 17 at 1:58
$begingroup$
no, they're constant
$endgroup$
– user1543042
Jan 17 at 2:15
$begingroup$
no, they're constant
$endgroup$
– user1543042
Jan 17 at 2:15
$begingroup$
Everything is real and greater than 0
$endgroup$
– user1543042
Jan 17 at 4:14
$begingroup$
Everything is real and greater than 0
$endgroup$
– user1543042
Jan 17 at 4:14
|
show 1 more comment
1 Answer
1
active
oldest
votes
$begingroup$
You can form the optimization problem as
$$begin{align*}min_{beta}quad&-sum_{i=1}^{n}left(frac{beta_i}{r_i}right)Wleft(-frac{P_i r_i}{beta_i}right)\
text{s.t.}quad&beta_igeq 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)Wleft(-frac{P_i r_i}{beta_i}right)+sum_{i=1}^{n}mu_i(eP_ir_i-beta_i)+lambdaleft(sum_{i=1}^{n}beta_i-Bright).$$
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}cdotfrac{left[Wleft(-frac{P_i r_i}{beta_i}right)right]^2}{Wleft(-frac{P_i r_i}{beta_i}right)+1}+mu_i-lambda=0$$
which is quadratic in $Wleft(-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[1pmsqrt{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
$$Wleft(-frac{P_i r_i}{beta_i}right)=frac{lambda r_i}{2}left[1pmsqrt{1+frac{4}{lambda r_i}}right]$$
which implies
$$beta_i={P_i r_i}frac{expleft(frac{lambda r_i}{2}left[-1mpsqrt{1+frac{4}{lambda r_i}}right]right)}{frac{lambda r_i}{2}left[-1mpsqrt{1+frac{4}{lambda r_i}}right]}$$
which, since $beta_igeq eP_i r_igeq 0 $ and $lambdageq 0$ forces the sign of $mp$ to be $+$. So when $mu_i=0$, we have
$$beta_i={P_i r_i}frac{expleft(frac{lambda r_i}{2}left[sqrt{1+frac{4}{lambda r_i}}-1right]right)}{frac{lambda r_i}{2}left[sqrt{1+frac{4}{lambda r_i}}-1right]}.$$
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_{iin 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_{iinmathcal{P}}{P_i r}frac{expleft(frac{lambda r}{2}left[sqrt{1+frac{4}{lambda r}}-1right]right)}{frac{lambda r}{2}left[sqrt{1+frac{4}{lambda r}}-1right]}=B$$
which can be shown to have solution
$$lambda=-frac{1}{r}cdotfrac{left[Wleft(-frac{r}{B}sum_{iinmathcal{P}}P_iright)right]^2}{Wleft(-frac{r}{B}sum_{iinmathcal{P}}P_iright)-1}$$
which then gives $beta_i=Bfrac{P_i}{sum_{iinmathcal{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_{inotinmathcal{P}}eP_i-sum_{iinmathcal{P}}left(frac{Bfrac{P_i}{sum_{iinmathcal{P}}P_i}}{r_i}right)Wleft(-frac{P_i r}{Bfrac{P_i}{sum_{iinmathcal{P}}P_i}}right)&=esum_{inotinmathcal{P}}P_i-sum_{iinmathcal{P}}frac{B}{r}frac{P_i}{sum_{iinmathcal{P}}P_i}Wleft(-frac{r}{B}sum_{iinmathcal{P}}P_iright)\
&=esum_{inotinmathcal{P}}P_i-frac{B}{r}Wleft(-frac{r}{B}sum_{iinmathcal{P}}P_iright)end{align*}$$
Now, the constraint can be written as
$$B=sum_{inotinmathcal{P}}eP_i r+sum_{iinmathcal{P}}Bfrac{P_i}{sum_{iinmathcal{P}}P_i}=sum_{inotinmathcal{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}Wleft(-frac{r}{B}sum_{i=1}^{n}P_iright)$, with minimizer $beta_i=Bfrac{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_itoinfty$ 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_itoinfty}r_ifrac{expleft(frac{lambda r_i}{2}left[sqrt{1+frac{4}{lambda r_i}}-1right]right)}{frac{lambda r_i}{2}left[sqrt{1+frac{4}{lambda r_i}}-1right]}=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.
answered Jan 17 at 8:30
nathan.j.mcdougallnathan.j.mcdougall
1,519818
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3075309%2fmultiple-loan-repayment-optimization-problem%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
You can form the optimization problem as
$$begin{align*}min_{beta}quad&-sum_{i=1}^{n}left(frac{beta_i}{r_i}right)Wleft(-frac{P_i r_i}{beta_i}right)\
text{s.t.}quad&beta_igeq 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)Wleft(-frac{P_i r_i}{beta_i}right)+sum_{i=1}^{n}mu_i(eP_ir_i-beta_i)+lambdaleft(sum_{i=1}^{n}beta_i-Bright).$$
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}cdotfrac{left[Wleft(-frac{P_i r_i}{beta_i}right)right]^2}{Wleft(-frac{P_i r_i}{beta_i}right)+1}+mu_i-lambda=0$$
which is quadratic in $Wleft(-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[1pmsqrt{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
$$Wleft(-frac{P_i r_i}{beta_i}right)=frac{lambda r_i}{2}left[1pmsqrt{1+frac{4}{lambda r_i}}right]$$
which implies
$$beta_i={P_i r_i}frac{expleft(frac{lambda r_i}{2}left[-1mpsqrt{1+frac{4}{lambda r_i}}right]right)}{frac{lambda r_i}{2}left[-1mpsqrt{1+frac{4}{lambda r_i}}right]}$$
which, since $beta_igeq eP_i r_igeq 0 $ and $lambdageq 0$ forces the sign of $mp$ to be $+$. So when $mu_i=0$, we have
$$beta_i={P_i r_i}frac{expleft(frac{lambda r_i}{2}left[sqrt{1+frac{4}{lambda r_i}}-1right]right)}{frac{lambda r_i}{2}left[sqrt{1+frac{4}{lambda r_i}}-1right]}.$$
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_{iin 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_{iinmathcal{P}}{P_i r}frac{expleft(frac{lambda r}{2}left[sqrt{1+frac{4}{lambda r}}-1right]right)}{frac{lambda r}{2}left[sqrt{1+frac{4}{lambda r}}-1right]}=B$$
which can be shown to have solution
$$lambda=-frac{1}{r}cdotfrac{left[Wleft(-frac{r}{B}sum_{iinmathcal{P}}P_iright)right]^2}{Wleft(-frac{r}{B}sum_{iinmathcal{P}}P_iright)-1}$$
which then gives $beta_i=Bfrac{P_i}{sum_{iinmathcal{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_{inotinmathcal{P}}eP_i-sum_{iinmathcal{P}}left(frac{Bfrac{P_i}{sum_{iinmathcal{P}}P_i}}{r_i}right)Wleft(-frac{P_i r}{Bfrac{P_i}{sum_{iinmathcal{P}}P_i}}right)&=esum_{inotinmathcal{P}}P_i-sum_{iinmathcal{P}}frac{B}{r}frac{P_i}{sum_{iinmathcal{P}}P_i}Wleft(-frac{r}{B}sum_{iinmathcal{P}}P_iright)\
&=esum_{inotinmathcal{P}}P_i-frac{B}{r}Wleft(-frac{r}{B}sum_{iinmathcal{P}}P_iright)end{align*}$$
Now, the constraint can be written as
$$B=sum_{inotinmathcal{P}}eP_i r+sum_{iinmathcal{P}}Bfrac{P_i}{sum_{iinmathcal{P}}P_i}=sum_{inotinmathcal{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}Wleft(-frac{r}{B}sum_{i=1}^{n}P_iright)$, with minimizer $beta_i=Bfrac{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_itoinfty$ 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_itoinfty}r_ifrac{expleft(frac{lambda r_i}{2}left[sqrt{1+frac{4}{lambda r_i}}-1right]right)}{frac{lambda r_i}{2}left[sqrt{1+frac{4}{lambda r_i}}-1right]}=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.
answered Jan 17 at 8:30
nathan.j.mcdougallnathan.j.mcdougall
1,519818
$endgroup$
add a comment |
$begingroup$
You can form the optimization problem as
$$begin{align*}min_{beta}quad&-sum_{i=1}^{n}left(frac{beta_i}{r_i}right)Wleft(-frac{P_i r_i}{beta_i}right)\
text{s.t.}quad&beta_igeq 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)Wleft(-frac{P_i r_i}{beta_i}right)+sum_{i=1}^{n}mu_i(eP_ir_i-beta_i)+lambdaleft(sum_{i=1}^{n}beta_i-Bright).$$
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}cdotfrac{left[Wleft(-frac{P_i r_i}{beta_i}right)right]^2}{Wleft(-frac{P_i r_i}{beta_i}right)+1}+mu_i-lambda=0$$
which is quadratic in $Wleft(-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[1pmsqrt{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
$$Wleft(-frac{P_i r_i}{beta_i}right)=frac{lambda r_i}{2}left[1pmsqrt{1+frac{4}{lambda r_i}}right]$$
which implies
$$beta_i={P_i r_i}frac{expleft(frac{lambda r_i}{2}left[-1mpsqrt{1+frac{4}{lambda r_i}}right]right)}{frac{lambda r_i}{2}left[-1mpsqrt{1+frac{4}{lambda r_i}}right]}$$
which, since $beta_igeq eP_i r_igeq 0 $ and $lambdageq 0$ forces the sign of $mp$ to be $+$. So when $mu_i=0$, we have
$$beta_i={P_i r_i}frac{expleft(frac{lambda r_i}{2}left[sqrt{1+frac{4}{lambda r_i}}-1right]right)}{frac{lambda r_i}{2}left[sqrt{1+frac{4}{lambda r_i}}-1right]}.$$
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_{iin 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_{iinmathcal{P}}{P_i r}frac{expleft(frac{lambda r}{2}left[sqrt{1+frac{4}{lambda r}}-1right]right)}{frac{lambda r}{2}left[sqrt{1+frac{4}{lambda r}}-1right]}=B$$
which can be shown to have solution
$$lambda=-frac{1}{r}cdotfrac{left[Wleft(-frac{r}{B}sum_{iinmathcal{P}}P_iright)right]^2}{Wleft(-frac{r}{B}sum_{iinmathcal{P}}P_iright)-1}$$
which then gives $beta_i=Bfrac{P_i}{sum_{iinmathcal{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_{inotinmathcal{P}}eP_i-sum_{iinmathcal{P}}left(frac{Bfrac{P_i}{sum_{iinmathcal{P}}P_i}}{r_i}right)Wleft(-frac{P_i r}{Bfrac{P_i}{sum_{iinmathcal{P}}P_i}}right)&=esum_{inotinmathcal{P}}P_i-sum_{iinmathcal{P}}frac{B}{r}frac{P_i}{sum_{iinmathcal{P}}P_i}Wleft(-frac{r}{B}sum_{iinmathcal{P}}P_iright)\
&=esum_{inotinmathcal{P}}P_i-frac{B}{r}Wleft(-frac{r}{B}sum_{iinmathcal{P}}P_iright)end{align*}$$
Now, the constraint can be written as
$$B=sum_{inotinmathcal{P}}eP_i r+sum_{iinmathcal{P}}Bfrac{P_i}{sum_{iinmathcal{P}}P_i}=sum_{inotinmathcal{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}Wleft(-frac{r}{B}sum_{i=1}^{n}P_iright)$, with minimizer $beta_i=Bfrac{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_itoinfty$ 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_itoinfty}r_ifrac{expleft(frac{lambda r_i}{2}left[sqrt{1+frac{4}{lambda r_i}}-1right]right)}{frac{lambda r_i}{2}left[sqrt{1+frac{4}{lambda r_i}}-1right]}=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.
answered Jan 17 at 8:30
nathan.j.mcdougallnathan.j.mcdougall
1,519818
$endgroup$
add a comment |
$begingroup$
You can form the optimization problem as
$$begin{align*}min_{beta}quad&-sum_{i=1}^{n}left(frac{beta_i}{r_i}right)Wleft(-frac{P_i r_i}{beta_i}right)\
text{s.t.}quad&beta_igeq 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)Wleft(-frac{P_i r_i}{beta_i}right)+sum_{i=1}^{n}mu_i(eP_ir_i-beta_i)+lambdaleft(sum_{i=1}^{n}beta_i-Bright).$$
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}cdotfrac{left[Wleft(-frac{P_i r_i}{beta_i}right)right]^2}{Wleft(-frac{P_i r_i}{beta_i}right)+1}+mu_i-lambda=0$$
which is quadratic in $Wleft(-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[1pmsqrt{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
$$Wleft(-frac{P_i r_i}{beta_i}right)=frac{lambda r_i}{2}left[1pmsqrt{1+frac{4}{lambda r_i}}right]$$
which implies
$$beta_i={P_i r_i}frac{expleft(frac{lambda r_i}{2}left[-1mpsqrt{1+frac{4}{lambda r_i}}right]right)}{frac{lambda r_i}{2}left[-1mpsqrt{1+frac{4}{lambda r_i}}right]}$$
which, since $beta_igeq eP_i r_igeq 0 $ and $lambdageq 0$ forces the sign of $mp$ to be $+$. So when $mu_i=0$, we have
$$beta_i={P_i r_i}frac{expleft(frac{lambda r_i}{2}left[sqrt{1+frac{4}{lambda r_i}}-1right]right)}{frac{lambda r_i}{2}left[sqrt{1+frac{4}{lambda r_i}}-1right]}.$$
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_{iin 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_{iinmathcal{P}}{P_i r}frac{expleft(frac{lambda r}{2}left[sqrt{1+frac{4}{lambda r}}-1right]right)}{frac{lambda r}{2}left[sqrt{1+frac{4}{lambda r}}-1right]}=B$$
which can be shown to have solution
$$lambda=-frac{1}{r}cdotfrac{left[Wleft(-frac{r}{B}sum_{iinmathcal{P}}P_iright)right]^2}{Wleft(-frac{r}{B}sum_{iinmathcal{P}}P_iright)-1}$$
which then gives $beta_i=Bfrac{P_i}{sum_{iinmathcal{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_{inotinmathcal{P}}eP_i-sum_{iinmathcal{P}}left(frac{Bfrac{P_i}{sum_{iinmathcal{P}}P_i}}{r_i}right)Wleft(-frac{P_i r}{Bfrac{P_i}{sum_{iinmathcal{P}}P_i}}right)&=esum_{inotinmathcal{P}}P_i-sum_{iinmathcal{P}}frac{B}{r}frac{P_i}{sum_{iinmathcal{P}}P_i}Wleft(-frac{r}{B}sum_{iinmathcal{P}}P_iright)\
&=esum_{inotinmathcal{P}}P_i-frac{B}{r}Wleft(-frac{r}{B}sum_{iinmathcal{P}}P_iright)end{align*}$$
Now, the constraint can be written as
$$B=sum_{inotinmathcal{P}}eP_i r+sum_{iinmathcal{P}}Bfrac{P_i}{sum_{iinmathcal{P}}P_i}=sum_{inotinmathcal{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}Wleft(-frac{r}{B}sum_{i=1}^{n}P_iright)$, with minimizer $beta_i=Bfrac{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_itoinfty$ 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_itoinfty}r_ifrac{expleft(frac{lambda r_i}{2}left[sqrt{1+frac{4}{lambda r_i}}-1right]right)}{frac{lambda r_i}{2}left[sqrt{1+frac{4}{lambda r_i}}-1right]}=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.
answered Jan 17 at 8:30
nathan.j.mcdougallnathan.j.mcdougall
1,519818
$endgroup$
You can form the optimization problem as
$$begin{align*}min_{beta}quad&-sum_{i=1}^{n}left(frac{beta_i}{r_i}right)Wleft(-frac{P_i r_i}{beta_i}right)\
text{s.t.}quad&beta_igeq 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)Wleft(-frac{P_i r_i}{beta_i}right)+sum_{i=1}^{n}mu_i(eP_ir_i-beta_i)+lambdaleft(sum_{i=1}^{n}beta_i-Bright).$$
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}cdotfrac{left[Wleft(-frac{P_i r_i}{beta_i}right)right]^2}{Wleft(-frac{P_i r_i}{beta_i}right)+1}+mu_i-lambda=0$$
which is quadratic in $Wleft(-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[1pmsqrt{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
$$Wleft(-frac{P_i r_i}{beta_i}right)=frac{lambda r_i}{2}left[1pmsqrt{1+frac{4}{lambda r_i}}right]$$
which implies
$$beta_i={P_i r_i}frac{expleft(frac{lambda r_i}{2}left[-1mpsqrt{1+frac{4}{lambda r_i}}right]right)}{frac{lambda r_i}{2}left[-1mpsqrt{1+frac{4}{lambda r_i}}right]}$$
which, since $beta_igeq eP_i r_igeq 0 $ and $lambdageq 0$ forces the sign of $mp$ to be $+$. So when $mu_i=0$, we have
$$beta_i={P_i r_i}frac{expleft(frac{lambda r_i}{2}left[sqrt{1+frac{4}{lambda r_i}}-1right]right)}{frac{lambda r_i}{2}left[sqrt{1+frac{4}{lambda r_i}}-1right]}.$$
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_{iin 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_{iinmathcal{P}}{P_i r}frac{expleft(frac{lambda r}{2}left[sqrt{1+frac{4}{lambda r}}-1right]right)}{frac{lambda r}{2}left[sqrt{1+frac{4}{lambda r}}-1right]}=B$$
which can be shown to have solution
$$lambda=-frac{1}{r}cdotfrac{left[Wleft(-frac{r}{B}sum_{iinmathcal{P}}P_iright)right]^2}{Wleft(-frac{r}{B}sum_{iinmathcal{P}}P_iright)-1}$$
which then gives $beta_i=Bfrac{P_i}{sum_{iinmathcal{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_{inotinmathcal{P}}eP_i-sum_{iinmathcal{P}}left(frac{Bfrac{P_i}{sum_{iinmathcal{P}}P_i}}{r_i}right)Wleft(-frac{P_i r}{Bfrac{P_i}{sum_{iinmathcal{P}}P_i}}right)&=esum_{inotinmathcal{P}}P_i-sum_{iinmathcal{P}}frac{B}{r}frac{P_i}{sum_{iinmathcal{P}}P_i}Wleft(-frac{r}{B}sum_{iinmathcal{P}}P_iright)\
&=esum_{inotinmathcal{P}}P_i-frac{B}{r}Wleft(-frac{r}{B}sum_{iinmathcal{P}}P_iright)end{align*}$$
Now, the constraint can be written as
$$B=sum_{inotinmathcal{P}}eP_i r+sum_{iinmathcal{P}}Bfrac{P_i}{sum_{iinmathcal{P}}P_i}=sum_{inotinmathcal{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}Wleft(-frac{r}{B}sum_{i=1}^{n}P_iright)$, with minimizer $beta_i=Bfrac{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_itoinfty$ 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_itoinfty}r_ifrac{expleft(frac{lambda r_i}{2}left[sqrt{1+frac{4}{lambda r_i}}-1right]right)}{frac{lambda r_i}{2}left[sqrt{1+frac{4}{lambda r_i}}-1right]}=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.
answered Jan 17 at 8:30
nathan.j.mcdougallnathan.j.mcdougall
1,519818
edited Jan 17 at 18:01
answered Jan 17 at 8:30
nathan.j.mcdougallnathan.j.mcdougall
1,519818
answered Jan 17 at 8:30
nathan.j.mcdougallnathan.j.mcdougall
1,519818
answered Jan 17 at 8:30
nathan.j.mcdougallnathan.j.mcdougall
1,519818
1,519818
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3075309%2fmultiple-loan-repayment-optimization-problem%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
What are your decision variables? $beta_i$ is a variable, but what else? The $W$ function is monotone over $[0,infty)$, so minimizing it can be achieved by minimizing its argument. If you know what the decision variables are, you might be able to make a similar observation about the actual objective and use it to remove the $W$ to get a linear objective.
$endgroup$
– nathan.j.mcdougall
Jan 16 at 5:03
$begingroup$
That is what I'm confused about... I control the allocation of $beta_i$
$endgroup$
– user1543042
Jan 17 at 1:51
$begingroup$
Okay, but what about $P$ and $r$, do you control those?
$endgroup$
– nathan.j.mcdougall
Jan 17 at 1:58
$begingroup$
no, they're constant
$endgroup$
– user1543042
Jan 17 at 2:15
$begingroup$
Everything is real and greater than 0
$endgroup$
– user1543042
Jan 17 at 4:14