Optimisation

Question 1

What is the Weierstrass or Extreme Value Theorem?

Answer 1

Let f(x) be continuous on a bounded closed interval [a, b]
then
i) f is bounded on [a, b], i.e. there exists 0 < B < ∞ such that |f(x)|≤B for all x in [a, b]
ii) f attains its minimum and maximum values over [a, b]

Question 1

What are some important limits to the Weierstrass Theorem?

Answer 1

It cannot be used when the domain is not closed, the domain is unbounded, or the function is discontinuous

Question 2

What are the supremum and infinum and how do they relate to the Extreme Value Theorem?

Answer 2

sup_x∈Df(x) is the lowest upper bound
inf_x∈Df(x) is the larger lower bound
Extreme Value Theorem says that if D is a bounded and closed interval and f is continuous on D then the supremum of f is the function’s maximum and the infinum is the minimum

Question 3

What is the Intermediate Value Theorem?

Answer 3

Let f(x) be continuous on a bounded closed interval [a, b] and let A be the minimum of f in this interval and B the maximum
Then f(x) takes on all values between A and B

Question 4

What is the definition of a local maximum?

Answer 4

A point d ∈ D is a local maximum of a function f with domain D if there exists some δ > 0 such that f(x) ≤ f(d) for all x in D such that |x - d| < δ, i.e. there is a neighbourhood of d within which f achieves it’s maximum value at d

Question 5

What is the Mean Value Theorem?

Answer 5

Let f be continuous over [a, b] and differentiable over (a, b)
Then there exists c ∈ (a, b) such that f’(c) = (f(b) - f(a))/(b - a)
i.e. there will be a point whose tangent has the same slope as the slope between the endpoints

Question 6

What is the Sufficient Second Order Condition Theorem?

Answer 6

Let f be twice differentiable around a critical point c
If f’‘(c) < 0 then c is a local maximum

Question 7

What is the Extreme Value (Weierstrass) Theorem for multivariate functions?

Answer 7

Let f(x) be continuous on a compact domain D
Then
i) f is bounded on D, i.e. there exists B such that |f(x)| ≤ B for any x in D
ii) f attains its minimum and maximum values over D

Question 8

What is the FOC for a local extreme point of a multivariate function?

Answer 8

f_i(x) = 0 for all i = 1, …, n

Question 9

What is the sufficient SOC for a local maximum of a bivariate function?

Answer 9

f₁₁(x) < 0 and f₁₁(x)f₂₂(x) - f₁₂²(x) > 0

Question 10

What is the sufficient SOC for a local minimum of a bivariate function?

Answer 10

f₁₁(x) > 0 and f₁₁(x)f₂₂(x) - f₁₂²(x) > 0

Question 11

What is the sufficient SOC for a global maximum of a bivariate function?

Answer 11

The interior critical point x* of the function f defined on a convex domain is a global maximum if for all x in int(D), f₁₁(x) ≤ 0 and f₁₁(x)f₂₂(x) - f₁₂²(x) ≥ 0
This function is called concave

Question 12

How do you use the Lagrangian multiplier method of optimisation?

Answer 12

1) Introduce the Lagrange multiplier and form the Lagrangian L(x, y) = f(x, y) - λ[g(x, y) - c] where g(x, y) = c is the constraint equation
2) Differentiate the Lagrangian wrt x, y, and λ and equate the partial derivatives to 0 to get the FOC
3) Solve the 3 equations for the 3 unknowns to get candidate solutions
4) Check whether the Lagrangian is concave or convex by checking whether L₁₁ is less than or greater than 0 and that L₁₁L_{22/sub> - L12² ≥ 0}

Question 13

How do you use the Hessian matrix to check a candidate solution for Lagrangian optimisation

Answer 13

The candidate is a local minimum if the Hessian is positive definite, meaning the first entry and the determinant are both greater than zero
The candidate is a local maximum if the Hessian is negative definite, meaning the first entry is less than zero and the determinant is greater than zero

Question 14

What is a critical point?

Answer 14

A point with ∂f(x)/∂x_i = 0 for all i = 1, …, n
Every critical point is either a minimum, a maximum, or a saddle point

Question 15

What is a saddle point?

Answer 15

A critical point x* such that there exists x arbitrarily close to x* where f(x) > f(x) and there exists x arbitrarily close to x where f(x) < f(x*)

Question 16

How can the Hessian be used to classify critical points?

Answer 16

Suppose f : R² –> R is twice continuously differentiable in a neighbourhood of a critical point x*
H(x) positive definite => x is a local minimum
H(x) negative definite => x is a local maximum
det(H(x)) < 0 => x is a saddle point
det(H(x)) = 0 => x could be min, max, or saddle (requires examination)

Question 17

How can you find the definiteness of the Hessian?

Answer 17

det(H) should be greater than zero, then if the top left element is positive the Hessian is positive definite, if the top left element is negative the Hessian is negative definite

Question 18

What is the general (multivariate) definition of convexity?

Answer 18

Given convex domain D ⊆ Rⁿ, f : D –> R is convex iff f(λx + (1-λ)y) ≤ λf(x) + (1-λ)f(y) for all x, y ∈ D for all λ ∈ (0, 1)

Question 19

How can the Hessian be used to classify a function?

Answer 19

Let f have continuous partial derivatives on an open, convex set K ⊆ R²
f convex on K <=> Hessian positive semidefinite for all x ∈ K
f concave on K <=> Hessian negative semidefinite for all x ∈ K
Hessian positive definite for all x ∈ K => f strictly convex on K
Hessian negative definite for all x ∈ K => f strictly concave on K

Question 20

Qualitatively, what is the Envelope Theorem?

Answer 20

The rate of change of the optimal value wrt an exogenous parameter = the rate of change of the objective function wrt the parameter evaluated at the optimal solution

Question 21

Quantitatively, what is the Envelope Theorem?

Answer 21

For the problem max_xf(x; a), if the maximiser x(a) is differentiable then dv/da = ∂f/∂a |_{x = x*(a)} where v(a) = f(x(a); a)
More generally, for the problem max f(x₁, …, x_n; a, b, c), let x(a, b, c) be a solution for some given (a, b, c) and let v(a, b, c) = f(x(a, b, c); a, b, c), if x*(a, b, c) is differentiable in b then ∂v/∂b = ∂f/∂b|_{x = x*}

Question 22

What is an example of how to use the Envelope Theorem?

Answer 22

If a company sells x units of a good at price p facing cost c(x), the Envelope theorem allows us to work out how their profit changes for small changes in p
Instead of working out separately the optimal quantity and resulting profit at the two prices, the envelope theorem means the change in profit is approximately equal to the change in price times the partial derivative of optimal profit wrt price evaluated for the optimal quantity at the original price

Question 23

How can you prove the Envelope Theorem?

Answer 23

Given a parameter a, the optimal value of the objective function is v(a) = f(x(a); a) where x(a) solves max_x f(x; a)
Using the chain rule dv/da = ∂f/∂x|_{x = x} dx/da + ∂f/∂a|x = x</sub> ∂a/∂a but at x ∂f/∂x = 0 and ∂a/∂a = 1 so we get the envelope theorem</sub>

Question 24

What is the Envelope Theorem for constrained optimisation?

Answer 24

For the problem max_x f(x; a) s.t. g(x; a) = 0 the objective function is v(a) = f(x(a); a)
As a changes both the objective function and the constraint change
If the maximiser x(a) is differentiable then dv/da = ∂L/∂a|_{x = x, λ = λ} where L(x, λ, a) = f(x; a) + λg(x; a)
In words, the roc of the optimal value wrt the exogenous parameter = the roc of the Lagrangian function wrt the parameter evaluated at the optimum solution

Question 25

How do you prove the Envelope Theorem for constrained optimisation?

Answer 25

Since x(a) solves the problem it should satisfy a Lagrangian FOC so there must be a λ(a) s.t. L_x = L_y = 0 at the optimal solution (x(a), λ(a)) which also satisfies the constraint g(x(a); a) = 0
Evaluating the Lagrangian at the optimal solution (x, λ*, a) gives the value function plus the optimal Lagrangian multiplier times the constraint at the optimal value which equals zero
Differentiating the value function wrt a is therefore the same as differentiating the Lagrangian at the optimal solution which by the chain rule and using the FOCs gives the envelope theorem result