20. Constrained Optimization

20.1. The Cake Eating Problem

Once upon a time there was a little girl who got a cake. The girl decided to eat the cake all alone. But she was not sure when she wanted to eat the cake. First, she thought of eating the whole cake right away. But then, nothing would be left for tomorrow and the day after tomorrow.

Well, on the one hand, eating cake today is better than eating it tomorrow. But then, eating too much at the same time might not be the best either. She imagined that the first mouthful of cake is a real treat, the second is great, the third is also nice. But the more you eat, the less you enjoy it.

So, she decided to eat only a bit of the cake everyday. Then, she could eat everyday another first mouthful of cake. The girl knew that the cake would be spoiled if she kept it more than nine days. Therefore, she would eat the cake in the first ten days. Yet, how much should she eat everyday?

20.2. Solution

  • She thought of eating everyday a piece of the same size.

  • But if eating cake today is better than waiting for tomorrow, how can it possibly be the best to do the same today as tomorrow?

  • If I ate just a little bit less tomorrow and a little bit more today I would be better off, she concluded.

  • And she would eat everyday a bit less than the previous day and the cake would last ten days long and nothing would be left in the end

20.3. Formally

  • Assume preferences in every period \(t\) follow: \(u(c_t) = ln(c_t)\)

  • \(c_t\) is the amount of cake consumed in period \(t\)

  • Future consumption is discounted with the time-preference factor \(\beta< 1\).

  • The present value in period 0 of the whole consumption path is:

\[V(c_0, c_1 ,c_2 ,...,c_T ) = \sum_{t=0}^{T} \beta^{t} U(c_t)\]

  • The person tries to maximize this by choosing her consumption in every period \(t=0,..,T\)

  • The cake size in the next period \(t+1\) is the size today less the consumption today

\[k_{t+1} = k_{t} - c_{t}\]

  • Therefore, the cake size must be non-negative in any period, so that

\[k_t \ge 0\]

20.4. Analytical Solution

  • Substituting the constraint into the life-time consumption path we get:

\[\beta^t U(k_{t-1} - k_{t})+ \beta^{t+1} U(k_{t} - k_{t+1})\]

  • Deriving this objective function w.r.t. \(k_t\) we get:

\[U'(c_{t-1}) = \beta U'(c_{t})\]

  • This is the so called ‘Euler Equation’. It relates the marginal utility of consumption today to the marginal utility of consumption tomorrow.

  • The Euler equation links two periods together. It has to hold in every period.

\[U'(c_{t}) = \beta U'(c_{t+1})\]

Note

The Euler equation has an intuitive interpretation

  • At a utility maximum, the consumer cannot gain from feasible shifts of consumption between periods

  • A one-unit reduction in period \(t\) consumption lowers \(U_t\) by \(U'_t\).

  • This unit saved can be shifted to period \(t+1\) where it raises

  • utility by \(U'_{t+1}\) discounted to period \(t\), that is: \(\beta \times U'_{t+1}\)

  • In the optimum these two quantities must be equal!

20.5. Solving the Problem

  • Plugging the functional form for the utility function into the Euler equation we get:

\[c_{t+1} = \beta c_{t}\]

or reformulated

\[c_{t} = \frac{1}{\beta}\times c_{t+1}\]

  • In the optimum we know that: \(k_{T+1} = 0\)

  • Recursively plugging the budget constraint into the Euler equation we get:

\[\boxed{c_0=\frac{1-\beta}{(1-\beta)^{T+1}}k_0}\]

  • We can now map out the optimal consumption for any size cake: \(k_0\)

Note

The solution was found by solving the problem backwards, starting in the last period \(T\):

  • \(c_T = k_T\) in the last period, eat entire cake

  • \(c_{T-1}\) we get by:

    1. Substituting the Euler equation we have: \(c_{T-1}=\frac{1}{\beta} c_T=\frac{1}{\beta} k_T\)

    2. Substituting the budget constraint: \(c_{T-1}=\frac{1}{\beta} (k_{T-1} - c_{T-1})\)

    3. Which can be solved for: \(c_{T-1}=\frac{1}{1+\beta} k_{T-1}\)

  • We next solve for: \(c_{T-2}=\frac{1}{\beta} c_{T-1}\), which after substituting for \(c_{T-1}=\frac{1}{1+\beta} k_{T-1}\) we get

    \(c_{T-2}=\frac{1}{\beta +\beta^{2}} k_{T-1}\). We again substitute the budget constraint \(k_{T-1} = k_{T-2} - c_{T-2}\) and get \(c_{T-2}=\frac{1}{\beta +\beta^{2}} (k_{T-2} - c_{T-2})\) which we can solve for \(c_{T-2}\) which becomes: \(c_{T-2}=\frac{1}{1 + \beta +\beta^{2}} k_{T-2}\)

  • Continue with this and find: \(c_{T-T} = \frac{1}{1+\beta + \beta^2 +...+\beta^T} k_{T-T}\)

  • Using: \(\sum_{t=0}^{T}\beta^t = \frac{1-\beta^{T+1}}{1-\beta}\), we get

  • \(\boxed{c_0=\frac{1-\beta}{(1-\beta)^{T+1}}k_0}\)

20.6. Plotting the Solution

  • For any size \(k+0\) and time horizon \(T\) we can now calculate the optimal consumption in each period

  • Example: \(k_0 = 50\), \(T=10\), and \(\beta = 0.96\)

import numpy as np
import matplotlib.pyplot as plt
import math as m
from scipy import stats as st
from scipy import optimize
import time            # Imports system time module to time your
script

plt.close('all')  # close all open figures

We next calculate the solutions following the analytical procedure introduced above and plot the optimal consumption path over time.

T = 9
beta = 0.9
kv = np.zeros(T+1,float)
cv = np.zeros(T+1,float)
uv = np.zeros(T+1,float)
kv[0] = 100  # k0
cv[0] = (1.0-beta)/(1.0-beta**(T+1)) * kv[0]  # c0
uv[0] = np.log(cv[0])

for i in range(1,T+1):
    #print "i=" + str(i)
    cv[i] = beta * cv[i-1]
    kv[i] = kv[i-1] - cv[i-1]

    # Period utility with discounting
    uv[i] = beta**(i-1)*np.log(cv[i])

np.sum(uv)  # total utility

print("cv = " + str(cv))
print("kv = " + str(kv))

cv = [ 15.35339933  13.8180594   12.43625346  11.19262811  10.0733653
   9.06602877   8.15942589   7.3434833    6.60913497   5.94822148]
kv = [ 100.           84.64660067   70.82854128   58.39228782
47.19965971
   37.12629441   28.06026564   19.90083975   12.55735645
5.94822148]

Plotting the function is achieved via:

fig, ax = plt.subplots(2,1)
plt.subplots_adjust(wspace=0.4, hspace=0.3)
#
ax[0].plot(cv, '-o')
ax[0].set_ylabel(r'$c^*_t$')
ax[0].set_xlabel('Period t')
ax[0].set_title('Optimal Consumption')
#
ax[1].plot(kv, '-o')
ax[1].set_ylabel(r'$k_t$')
ax[1].set_xlabel('Period t')
ax[1].set_title('Cake size')
#
plt.show()
_images/Slides_Cake_Cake_1.png

20.7. Numerical Solution in Python

  • For a numerical solution we use the optimize package

  • The routine fmin_slsqp minimizes constrained non-linear functions

Todo

  • I recommend getting into the habit of reading the documentation for functions of libraries so that you learn how to use them correctly as well as the different ways of their application.

  • Here is the link: Scipy Documentation for fmin_slsqp

  • The constraints can be equality or inequality constraints

  • Our problem has one equality constraint:

  • We start by defining the functions that we would like to optimize, which is basically present value welfare, or the present value of all future utilities added up. We define this welfare stream from consumption as func1.

\[\sum_{t=0}^{T}\beta^{t} U(c_t)\]
def func1(cv):
    T = len(cv)
    uv= np.zeros(T,float)
    for i in range(T):
        beta = 0.9
        # Period utility with discounting
        uv[i] = (beta**i) * np.log(cv[i])

    # We want to maximize this welfare,
    # so we need to 'negate' the result
    return (-np.sum(uv))

  • The constraint is defined as function eqn1. This basically states that you cannot eat more than the cake itself.

\[c_0+c_1+...+c_T=k_0\]
# The constraint
def constr1(cv):
    k0 = 100
    z1 = np.sum(cv) - k0
    return np.array([z1])

We finally call the optimizer routine fmin_slsqp handing in the function we want to maximize func1, the starting values for consumption in each period c0v and the constraints vector for each period constr1.

T = 10

# Starting guesses for the optimal consumption vector
c0v = np.ones(T,float)*0.1

coptv = optimize.fmin_slsqp(func1, c0v, f_eqcons = constr1)

print(coptv)

Optimization terminated successfully.    (Exit mode 0)
            Current function value: -15.2873553632
            Iterations: 22
            Function evaluations: 264
            Gradient evaluations: 22
[ 15.33727223  13.82825036  12.45005498  11.19821343  10.06848065
   9.05581662   8.15286629   7.34763605   6.62044636   5.94096304]

And finally we plot the optimal consumption path coptv that we just solved for.

fig, ax = plt.subplots()
# Plot analytical and numerical solution
ax.plot(np.arange(0,T), cv, 'b-o', np.arange(0,T), coptv, 'r--o')
ax.set_title("Optimal consumption")
ax.set_xlabel("Period t")
ax.set_ylabel("c_t")
# Create a legend
ax.legend(['analytical', 'numerical'], loc='best', shadow=True)
print('-----------------------------')
print('Analytic solution')
print('cv = {}'.format(cv))
print('-----------------------------')
print(' ')
print('-----------------------------')
print('Numeric solution')
print('cv = {}'.format(coptv))
print('-----------------------------')

-----------------------------
Analytic solution
cv = [ 15.35339933  13.8180594   12.43625346  11.19262811  10.0733653
   9.06602877   8.15942589   7.3434833    6.60913497   5.94822148]
-----------------------------

-----------------------------
Numeric solution
cv = [ 15.33727223  13.82825036  12.45005498  11.19821343  10.06848065
   9.05581662   8.15286629   7.34763605   6.62044636   5.94096304]
-----------------------------
_images/Slides_Cake_Optimal_Consumption_1.png

We can now see that the numerical solution is very close to the analytical solution we derived ‘by hand’ above. The optimal consumption path is decreasing. You start out eating a lot of cake and then gradually decrease your consumption. Still, you want to eat a bit of cake every period.