MIE 37 - Final Exam 2024

Name:

Surname:

After completing the following questions, send the edited notebook to pablo.winant@ensae.fr.

You are allowed to use any online available resource, even to install Julia packages, but not to copy/paste any code.

Also, don’t forget to comment your code and take any initiative you find relevant.

Part I - Linear Regression and Stochastic Gradient Descent

We consider the following data generation process:

\[y=0.4+2.5 x + \epsilon\]

where $x_i$ is uniformly distributed between 0 and 1 and $\epsilon$ is drawn from a normal distribution with standard deviation $\sigma=0.5$.

Write a function draw(a::Number, b::Number)::Tuple{Float64, Float64} which generates one random draw for a pair $(x,y)$.

# you code here

Generate a sample $d=(x_i, y_i)_{i=[1,N]}$ of $N=100000$ different observations. Justify your choice for how to represent this data.

# you code here

Write the loss function $L(d,a,b)=\frac{1}{N}\sum_{i=1}^N ( a x_i + b-y_i)^2$. Find the values of $a$ and $b$ minimizing this function by implementing the gradient descent algorithm (do not use any library). What is the best learning rate?

# you code here

Write another function ξ(a::Number, b::Number)::Tuple{Float64, Float64, Float64} which returns a random realization of $( a x + b - y)^2$ as well as its derivatives w.r.t. a and b (make sure the derivatives are computed for the same realization of $\epsilon$). We call ξ the empirical loss.

(hint: here you can either compute the derivatives by hand, or use an automatic differentiation library)

# you code here

5. Stochastic gradient algorithm.

The stochastic gradient algorithm minimizes \[E\xi(a,b)\] with the following steps:

start with an initial guess $a_0,b_0$
given a guess $a_k, b_k$
- compute $\xi, \xi^{prime}_a, \xi^{prime}_b$ using the function from the last function
- make a new guess $(a_{k+1}, b_{k+1}) = (1-\lambda) (a_{k}, b_{k}) - \lambda (\xi^{\prime}_a, \xi^{\prime}_b)$

Implement the SGD algorithm. How many iterations does one needs to get a good approximation of $a,b$? What value of $ $ works better? Compare with question 3.

# you code here

6. (bonus) Illustrate the convergence by plotting the empirical loss for each step $k$ in the above alogorithm, as well as the validation loss in the same step. (Given $a,b$, the validation loss is the empirical mean of $\xi(a,b)$ computed using $N=1000$ observations.)

# you code here

Part II - Endogenous Exit

Discretization of an AR1

The following code, taken from Quantecon.jl approximates an AR1 process \[y_t = \mu + \rho (y_{t-1}-\mu) + \epsilon_t\] (where $\nu$ is the standard deviation of normal process $\epsilon$), using a finite markov chain with $N$ different values.

The output is a transition matrix and a vector containing discretized values $y_1, y_2, ... y_p$

# uncomment the following line if "SpecialFunctions" is not on your system
# import Pkg; Pkg.add("SpecialFunctions")

using SpecialFunctions: erfc

std_norm_cdf(x::T) where {T <: Real} = 0.5 * erfc(-x/sqrt(2))
std_norm_cdf(x::Array{T}) where {T <: Real} = 0.5 .* erfc(-x./sqrt(2))

function tauchen(N::Integer, ρ::T1, σ::T2, μ=zero(promote_type(T1, T2)), n_std::T3=3) where {T1 <: Real, T2 <: Real, T3 <: Real}
    # Get discretized space
    a_bar = n_std * sqrt(σ^2 / (1 - ρ^2))
    y = range(-a_bar, stop=a_bar, length=N)
    d = y[2] - y[1]

    # Get transition probabilities
    Π = zeros(promote_type(T1, T2), N, N)
    for row = 1:N
        # Do end points first
        Π[row, 1] = std_norm_cdf((y[1] - ρ*y[row] + d/2) / σ)
        Π[row, N] = 1 - std_norm_cdf((y[N] - ρ*y[row] - d/2) / σ)

        # fill in the middle columns
        for col = 2:N-1
            Π[row, col] = (std_norm_cdf((y[col] - ρ*y[row] + d/2) / σ) -
                           std_norm_cdf((y[col] - ρ*y[row] - d/2) / σ))
        end
    end

    yy = y .+ μ / (1 - ρ) # center process around its mean (wbar / (1 - rho)) in new variable

    (;transitions=Π, values=yy)

end

tauchen (generic function with 3 methods)

1. Take $\rho=0.95, \mu=0.1, \nu=0.1$. Approximate the AR1 with 200 discrete states, using the tauchen function above. Check that all rows sum to 1. Compute and plot the steady-state distribution.

# you code here

Consider a firm whose productivity $y_t$ is exogenous and evolves according to the markov chain above.

Profits are given by $\pi(y_t) = y_t$.

At the start of each period, the firm decides whether to remain in operation and receive current profit $\pi_t$ or to exit and receive scrap value $s>0$ for the sale of physical assets.

Time is discounted using interest rate, that is $\beta=\frac{1}{1+r} \in [0,1[$.

The following code creates a parameterization of the firm’s problem:

"Creates an instance of the firm exit model."
function create_exit_model(;
    n=200, # productivity grid size
    ρ=0.95, μ=0.1, ν=0.1, # persistence, mean and volatility
    β=0.98, s=100.0 # discount factor and scrap value
    )
    mc = tauchen(n, ρ, ν, μ)
    z_vals, Q = mc.state_values, mc.p
    return (; n, z_vals, Q, β, s)
end

create_exit_model

2. What are the states of the problem? The controls? The rewards? What equation defines the value of the firm? How would you represent numerically the value function and the decision rule?

# you code here

3. Solve for the optimal exit decision using value function iteration. Plot the results.

# you code here

4. (bonus) Taking into account the specific nature of this problem, propose a more efficient algorithm.

# you code here