Chapter 4 – Exercises

Exercise 1: Basics

a. Concepts

(i) Verbally explain the difference and relationship between a maximum and a maximizer.

Unlike the maximum, the maximizer concept always refers to a certain function. The maximum is the largest value in a given set, whereas the maximizer is the value domain (set) of the function that yields the largest value, i.e. the maximum of the range, when evaluating the function at this point.
Therefore, a maximum can exist for any set X\subseteq\mathbb R, whereas the maximizer x^*\in X of a function f:X\mapsto\mathbb R (where X is any set of objects) always satisfies f(x^*) = \max_{x\in X}f(x), so that the maximizer concept can not be viewed in isolation of the maximum.
The key distinction that you should be aware of especially for applications in the optimization context is that the maximizer is an argument of the function whereas the maximum is a value in a set, in optimization problems typically the codomain of the objective.


(ii) Relate the arg max to the maximum using a mathematical statement (refer to a function f:X\mapsto\mathbb R).

    \[ \forall x^*\in \arg\max_{x\in X}f(x) : (f(x^*) = \max_{x\in X} f(x)) \]


(iii) Let x^*_1, x^*_2\in X such that x^*_1\in \arg\max_{x\in X} f(x) and x^*_2 \arg\max_{x\in C} f|_C(x) where C\subseteq X is a constraint set. Can you have f(x_2^*)>f(x_1^*)? Explain why (not).
Hint: Less formally, this question asks whether you can have a strictly larger value in a constrained optimization problem than in an unconstrained problem with the same objective.

It will always be the case that f(x_2^*)\leq f(x_1^*). The simple reason is that x^*_1 is a global maximizer of f, which, by definition, means that

    \[ \forall x\in X: f(x_1^*)\geq f(x) \]

and because x_2^*\in X, it especially also holds that f(x_2^*)\leq f(x_1^*).
Therefore, by restricting the domain, i.e. by imposing conditions on optimization, we always weakly lower the maximum value.


(iv) Can be \arg\max_{x\in X}f(x) empty? Can it have more than one argument if there is a strict global maximizer?

\arg\max_{x\in X}f(x) can be empty. This is the case whenever f does not have maximizers. Examples of this include f:\mathbb R\mapsto\mathbb R, x\mapsto x or f:\mathbb R_+\mapsto\mathbb R_+, x\mapsto \log(x).
If there is a strict global maximizer, \arg\max_{x\in X}f(x) is not empty. On the other hand, the set can not have more than one value, because by the definition of the strict global maximizer,

    \[ x^*\in X: f(x^*)>f(x) \]

other global maximizers, strict or not, are ruled out.


b. Existence of Solutions: Weierstrass

A first step to solving an optimization problem is forming an expectation of whether one will find a solution. Our common tool to approach this issue is the Weierstrass Extreme Value Theorem. A number of practice problems for this theorem can be found on Problem Set 4. Here, we again focus on the role of continuity in the requirements of the theorem.

(i) Give an example of a discontinuous function on a compact domain that does not have a global maximum.
Hint: Think about the intuition that Chapter 4 has discussed. You may want to define a “split function”, i.e. f(x) = \begin{cases} f_1(x) & \text{if \ldots}\\ f_2(x) & \text{else} \end{cases}, either explicitly or using an indicator term.

There are an infinite variety of functions that one could give here. Their common ground is that they have a discontinuous “jump” that splits the domain in (at least) two parts, at least one of which is not compact. On this part of the domain, the function will become ever larger with proximity to the boundary, which is not included in it, breaking the maximum. So long as your example satisfies this logic, it is valid.
One such example is f:[0,2]\mapsto\mathbb R x\mapsto \mathds{1}[x<1]\cdot x + 1. We know that closed intervals of \mathbb R are closed and bounded and thus, by Heine-Borel, compact. However, the discontinuous jump at x=1 splits the domain into [0,1) and [1,2]. On [0,1), as x approaches 1, f(x) increases steadily towards 2, but this maximum value is never attained as 1\notin [0,1).


(ii) Show that the Weierstrass Extreme Value Theorem is sufficient but not necessary by giving an example of a discontinuous function that attains both a global maximum and minimum.

Again, there are an infinite variety of functions that one could give here. Actually, when you think about it, the Weierstrass Extreme Value Theorem is quite strong in its requirements, as you can indeed find simple functions that violate all of them simultaneously and still attain maximum and minimum.
To continue the example of (i), we can look at f:[0,2]\mapsto\mathbb R x\mapsto \mathds{1}[x\leq 1]\cdot x + 1. Now, 1\in [0,1], so that f(1) = 2 constitutes the maximum. The minimum f(x)=1 is attained for every value x\in\{0\}\cup(1,2].
Even violation of continuity of both aspects of compactness (closedness and boundedness) alongside continuity still allows for maxima and minima to exist; a simple example is f:(0,\infty)\mapsto\mathbb R, x\mapsto \mathds{1}[x\in\mathbb N].


(iii) If there are no “border solutions” that we need to consider, meaning that we use only the Lagrangian method to identify potential solutions, do you need to worry about continuity?

If the Lagrangian method applies everywhere, the function is at least once continuously differentiable. This implies that it is also continuous, hence, continuity must not be investigated in isolation.


c. Existence of Solutions: Exploiting the Shape of the Function

In practical applications, a common issue with the Weierstrass Extreme Value Theorem is that the support is not compact. For example, this is the case whenever we optimize over the whole \mathbb R or \mathbb R^n in unconstrained optimization or non-compact constraint sets, such as open intervals/balls. Fortunately, in many cases, we can “compactify” the domain and avoid issues with solution existence in an elegant way. In this exercise, you will establish a corollary of Weierstrass that is a concrete example of this method.

Corollary: Optimizing a Univariate Function with Non-vanishing Limits.
Consider a function f\in C^2(\mathbb R), i.e. a function f:\mathbb R\mapsto\mathbb R that is twice continuously differentiable. Assume that

    1. There exist a,b\in\mathbb R with \lim_{x\to -\infty} f(x) = a and \lim_{x\to \infty} f(x) = b, that is, f does not diverge as x\to \pm\infty but rather approaches fixed, real limits.
    2. There exist c_1, c_2 > 0 such that either f'(x) > 0 for all x \in \mathbb R\backslash [-c_1, c_2] (Case 1) or f'(x) < 0 for all x \in \mathbb R\backslash [-c_1, c_2] (Case 2), that is, the sign of the derivative coincides for the limits x\to \pm\infty.
    3. In Case 1, b \leq a, and in Case 2, a\leq b.

Then, f assumes both a global maximum and minimum, and the global extremizers are critical points of f.


(i) Assume that f has exactly two critical points (i.e. points with f'(x) = 0). Can you illustrate the intuition of this corollary graphically for Case 1?

When f'(x) > 0 for all x \in \mathbb R\backslash [-c_1, c_2], b\leq a, and f has exactly two critical points, the function will look something like this:


This is the case as when f'(x) > 0 for all x \in \mathbb R\backslash [-c_1, c_2], then f approaches the left limit \lim_{x\to -\infty} f(x) = a from above and the right limit \lim_{x\to \infty} f(x) = b from below. Because b \leq a, the function must be decreasing somewhere on [-c_1, c_2]. Because it is twice continuously differentiable, the derivative does not jump, and every change of its sign (i.e., f going from increasing to decreasing or vice versa) produces a critical point with f'(x)=0. Because there are only two critical points, there will be one turn from positive to negative and a second one from negative to positive, as illustrated in the graph.
According to the intuition of the second derivative, a shift of f' from positive to negative constitutes a local maximum, whereas the converse shift constitutes a local minimum. It remains to argue that these local extrema are also global ones by ruling out that the local maximum is exceeded (the local minimum is subceeded) in the limits.
The local maximum x^{lmax} strictly exceeds the left limit as the function strictly increases everywhere to the left of x^{lmax}. For x>x^{lmax}, the function either decreases or approaches b\leq a < f(x^{lmax}) from below. Conversely, the local minimum x^{lmin} strictly subceeds the right limit as the function strictly increases everywhere to the right of x^{lmin}. For x<x^{lmin}, the function either increases or approaches a\geq b > f(x^{lmin}) from above. Hence, the local extrema are indeed global ones.
If you feel like testing your understanding of this intuition, graphically illustrate Case 2 and intuitively argue why the corollary holds in this case as well.


(ii) When f has exactly two critical points, can you say one is the global maximum/minimum of f depending on which case (Case 1 or Case 2) you are in?

With exactly two critical points, in Case 1, f' goes from (strictly) positive to negative to positive, whereas in Case 2, it goes from (strictly) negative to positive to negative (cf. also the elaborations in the Answer to Ex. 1.c.i.). Hence, in Case 1, the first local extremum is the global maximum whereas the second is the global minimum. In Case 2, it is the other way around.


(iii) Why do we need b\leq a in Case 1 and a\leq b in Case 2 to ensure existence of the global extrema?

In Case 1, if b > a, one might have f'(x) > 0 globally and there might be no critical point, as there is no “need” for the function to become decreasing anywhere to comply with the setup (cf. the elaborations in the Answer to Ex. 1.c.i.). Conversely, if we do not impose a\leq b in Case 2, we allow for globally strictly decreasing functions that assume no global extrema.


(iv) Give a formal argument why the corollary holds, i.e. put the graphical intuition in a mathematical argument. You may restrict attention to Case 1.
Comment: An analogous argument can be made for Case 2. Because this case does not add an interesting particularity, we do not investigate the argument establishing it here.
Hint 1: Recall the definition of the limit \lim_{x\to\infty} f(x): If \lim_{x\to\infty} f(x) = c, then

    \[ \forall \varepsilon > 0 \exists x^*\in \mathbb R: (\forall x > x^*: |f(x) - c| < \varepsilon) \]

Use this definition to restrict the investigation to a compact domain and apply Weierstrass.
Hint 2: It may be easier to investigate existence of the global maximum and minimum in isolation.

We first argue that there are compact subsets of the domain which, if f attains global extrema on these subsets, will constitute global extrema of f. Secondly, we argue that these extrema exist by the Weierstrass theorem.

Because f'(x) > 0 for x < -c_1, we know that

    \[ f(-c_1) \geq \lim_{x\to\infty}f(x) = a \geq b = \lim_{x\to -\infty}f(x) \]

Moreover, f'(x) > 0 for x < -c_1 implies f(x) < f(-c_1) for any x < -c_1. Furthermore, by the definition of \lim_{x\to \infty} f(x) (set \varepsilon = f(-c_1) - b > 0), there exists \gamma_1\in\mathbb R such that

    \[ \forall x> \gamma_1: (|f(x) - b| < f(-c_1) - b) \]

which, with f(x) - b \leq |f(x) - b|, implies

    \[ \forall x>\gamma_1: (f(x) - b \leq f(-c_1) - b) \hspace{0.5cm}\Leftrightarrow\hspace{0.5cm}\forall x>\gamma_1: (f(x) \leq f(-c_1)) \]

Combining these results, f(-c_1) \geq \lim_{x\to\infty}f(x) and f(-c_1) \geq \lim_{x\to -\infty}f(x), and moreover f(-c_1) \geq f(x) for any x\in (-\infty, -c_1]\cup[\gamma_1, \infty). Hence, any global maximum of f|_{[-c_1,\gamma_1]} is also a global maximum of f. Because [-c_1,\gamma_1] (as a closed interval) is compact and f|_{[-c_1,\gamma_1]} is continuous, f|_{[-c_1,\gamma_1]} meets the criteria of the Weierstrass Extreme Value Theorem, which implies that f|_{[x_L,\gamma_1]}, and therefore f, has a global maximum.

Similar reasoning can be applied to restrict the search for the global minimum: because f'(x) > 0 for x > c_2, we know that

    \[ f(c_2) < b = \lim_{x\to \infty} f(x) \leq a = \lim_{x\to -\infty} f(x) \]

Moreover, f'(x) > 0 for x > c_2 implies f(x) > f(c_2) for any x > c_2. Furthermore, by the definition of \lim_{x\to -\infty} f(x) (set \varepsilon = a - f(x_H)> 0), there exists \gamma_2\in\mathbb R for which

    \[ \forall x<\gamma_2: (|f(x) - a| < a - f(x_H)) \]

which, with a - f(x) \leq |f(x) - a|, implies

    \[ \forall x>\gamma_2: (a - f(x) \leq a - f(x_H)) \hspace{0.5cm}\Leftrightarrow\hspace{0.5cm}\forall x>\gamma_2: (f(x_H) \leq f(x)) \]

In analogy to above, any global minimum of f|_{[\gamma_2, c_2]} is also a global minimum of f. Because [\gamma_2, c_2] is compact and f|_{[\gamma_2, c_2]} is continuous, f|_{[x_L,\gamma_1]} meets the criteria of the Weierstrass Extreme Value Theorem, which implies that f|_{[\gamma_2, c_2]}, and therefore f, has a global minimum.

Comment 1: If you wanted to use the Weierstrass theorem only once, you could consider the interval I:=[\min\{\gamma_2, -c_1\}, \max \{\gamma_1, c_2\}]. The reasoning above yields that f_H:=f(\min\{\gamma_2, -c_1\}) strictly exceeds (f_L:=f(\max \{\gamma_1, c_2\}) strictly subceeds) the limits and that f_H \geq f(x) for any x\in \mathbb R\backslash I and f_L \leq f(x) for any x\in \mathbb R\backslash I. Accordingly, global extrema of f|_I will be global extrema of f, and the global extrema of f|_I exist by the Weierstrass theorem.

Comment 2: If you have trouble understanding this argument, try illustrating graphically where the points c_1, c_2, \gamma_1 and \gamma_2 lie and how the intervals we considered look like using a sketch similar to the one in Ex. 1.c.i.

Finally, it remains to establish that the global extremizers are critical points of f. The support of f, \mathbb R, has no boundary, and any interior point with f'(x_0)\neq 0 is not a local and therefore especially not a global extremizer. If you have looked at the proof of the first order necessary condition, you know this already. Otherwise, this is established as follows: because f is continuously differentiable everywhere, if f'(x_0)\neq 0, then by continuity, f' does not change sign in a small neighborhood around x_0, so that in any B_\varepsilon(x_0), \varepsilon > 0, there exist points x_L,x_H\in B_\varepsilon(x_0) with f(x_L) < f(x_0) < f(x_H) (if f'(x_0)>0, we have x_L < x_0 < x_H, and otherwise x_L > x_0 > x_H). Hence, x_0 is not a local and therefore especially not a global extremizer. Therefore, for any global extremizer x^*\in\mathbb R, it holds that f'(x^*) = 0.


Exercise 2: Unconstrained Optimization

a. A Simple Problem


    \[ \max_{x\in\mathbb R_+} \frac{3}{2}\cdot x^2 - \frac{1}{3}\cdot x^3 \]

and, if there are global maximizers, compute the maximum value.
Hint: Explicitly think about the limit behavior.

Non-differentiability: The function, as a polynomial of finite order, is infinitely many times continuously differentiable, and points of non-differentiability are not an issue.
Boundary Points: The support [0,\infty) has a boundary point: x=0 with f(0) = 0. This value needs to be compared against the interior solution(s) we derive.
Limit behavior: Because the support is only the positive real line, we need to consider only one asymptote. As x\to \infty, the x^3-term dominates, such that \lim_{x\to\infty}f(x) = -\infty, and limit behavior is not an issue in maximization (it would be in minimization, as this fact rules out global minima). Indeed, this aspect ensures that there will be at least one global maximum: for continuous functions, existence of global maxima breaks down only if the function can indefinitely increase into one direction, which is not the case here. Hence, we can proceed with the standard methods.
Interior Solutions: The first order necessary condition requires f'(x) = 0 for any local maximizer. The first derivative of the objective is

    \[\frac{\partial}{\partial x}\left (\frac{9}{2}\cdot x^2 - \frac{1}{3}\cdot x^3\right ) = 3x - x^2\]

Any candidate of the first order condition satisfies

    \[ 3x - x^2 = 0 \]

a first solution is x=0 which is the boundary point we already considered. To find other solutions, assume that x\neq 0 and divide both sides by x. Then, we obtain

    \[ 3 - x = 0\hspace{0.5cm}\Leftrightarrow\hspace{0.5cm} x = 3 \]

Accordingly, the first order condition yields the candidate set

    \[ C_{FOC} = \{0, 3\} \]

The second order necessary condition is concerned with the second derivative,

    \[\frac{\partial^2}{\partial x^2}\left (\frac{9}{2}\cdot x^2 - \frac{1}{3}\cdot x^3\right ) = \frac{\partial}{\partial x}(3x - x^2) = 3 - 2x\]

It is equal to -3<0 at x=3. Hence, x=3 is a local maximizer. At this argument, the objective attains the value

    \[ \frac{3}{2}\cdot 3^2 - \frac{1}{3}\cdot 3^3 = \frac{27}{2} - 9 = \frac{9}{2} \]

Thus, the interior local maximum strictly exceeds the border value f(0) = 0. As we have argued, the global maximum exists, and we can thus conclude that the global maximizer is x=3 with global maximum f(x) = \frac{9}{2}.


b. Border Solutions?


    \[ \max_{x\in \mathbb R} \frac{5x^2 - 2x}{6x^2 + 1} \hspace{0.5cm}\text{and}\hspace{0.5cm} \min_{x\in \mathbb R} \frac{5x^2 - 2x}{6x^2 + 1} \]

and, if there are global extremizers, compute the extreme values.
Hint: The function may have a particular shape that we investigated in an earlier exercise; an argument exploiting this shape may be used to elegantly circumvent the computation-intensive second order condition.

Non-differentiability: Both the numerator and denominator function, as a polynomial of finite order, are infinitely many times continuously differentiable. Moreover, by the quotient rule, you know that the denominator of the k-th derivative is (x^2 + 4)^{2k}, which is strictly positive, so that the derivative is always defined. Hence, the function itself is infinitely many times differentiable, and points of non-differentiability are not an issue.
Boundary Points: The support has no boundary points.
Limit behavior: For the limit behavior, as the x^2-terms dominate asymptotically,

    \[ \lim_{x\to\infty} \frac{5x^2 - 2x}{6x^2 + 1} = \lim_{x\to -\infty} \frac{5x^2 - 2x}{6x^2 + 1} = \frac{5}{6} \]

so that the function does not vanish to -\infty as was the case in Ex. 2.a. Moreover, looking at the first derivative,

    \[\begin{split} \frac{\partial}{\partial x}\left (\frac{5x^2 - 2x}{6x^2 + 1} \right ) &= \frac{(10x - 2)(6x^2 + 1) - 12x(5x^2 - 2x)}{(6x^2 + 1)^2} \\&= \frac{60x^3 - 12x^2 + 10x - 2 - 60x^3 + 24x^2}{(6x^2 + 1)^2} \\&= \frac{12x^2 + 10x - 2}{(6x^2 + 1)^2} \end{split}\]

This expression is strictly positive for |x| sufficiently large, so that the value \frac{5}{6} is approached from below (above) as x\to +\infty (x\to -\infty). Therefore, this function meets the shape requirements of Ex. 1.c. (you have a = b = 5/6 and f'(x)>0 for x\notin [-2, 2] and therefore, Case 1 applies). Accordingly, you can expect solutions to exist and restrict attention to the candidates identified by the first order condition even though the domain is not compact!
Interior Solutions: Setting the first derivative equal to zero gives

    \[ 12x^2 + 10x - 2 = 0 \hspace{0.5cm}\Leftrightarrow\hspace{0.5cm} x^2 + \frac{5}{6}x - \frac{1}{6} = 0 \]

Using the quadratic polynomial formula, we know that solutions x^* satisfy

    \[ x^* \in \left \{-\frac{5}{12} \pm \sqrt{\frac{25}{144} + \frac{1}{6}} \right \} = \left \{\frac{-5 \pm \sqrt{25 + 24}}{12}\right \} \]

Accordingly, the first order condition yields the candidate set

    \[ C_{FOC} = \left \{-1, \frac{1}{6}\right \} \]

This function meets the case of exactly two critical points we investigated in Ex. 1.c.ii and 1.c.iii. By the shape of the function, we already know that the smaller candidate will constitute the global maximum and the latter the global minimum without looking at the second derivative! Hence, the maximizer is x^* = -1 with value

    \[ \frac{5(-1)^2 - 2(-1)}{6(-1)^2 + 1} = \frac{7}{7} = 1 \]

and the global minimizer is x^* = \frac{1}{6} with value

    \[ \frac{5(\frac{1}{6})^2 - 2(\frac{1}{6})}{6(\frac{1}{6})^2 + 1} = \frac{\frac{5}{36} - \frac{12}{36}}{\frac{6}{36} + \frac{36}{36}} = \frac{-7}{42} = -\frac{1}{6} \]

Comment: If you didn’t know that the smaller candidate were the maximum and the latter the minimum, the information that both critical points will constitute one extreme value each would have also been sufficient as you could have simply compared values to judge which is maximizer and which is minimizer.


c. Compact Optimization

Determine the global extrema of f:[-4,2]\mapsto\mathbb R, x\mapsto x^3 + 4x^2 - 3x + 9.

Non-differentiability: The function, as a polynomial of finite order, is infinitely many times continuously differentiable, and points of non-differentiability are not an issue.
Boundary Points: The support has two boundary points that need to be considered as candidates in isolation.
Interior Solutions: The first order necessary condition requires f'(x) = 0 for any local maximizer. The first derivative of the objective is

    \[\frac{\partial}{\partial x}\left (x^3 + 4x^2 - 3x + 9\right ) = 3x^2 + 8x - 3\]

Any candidate of the first order condition satisfies

    \[ 3x^2 + 8x - 3 = 0 \hspace{0.5cm}\Leftrightarrow\hspace{0.5cm} x^2 + \frac{8}{3} x - 1 = 0 \]

Using the quadratic polynomial formula, we know that solutions x^* satisfy

    \[ x^* \in \left \{-\frac{4}{3} \pm \sqrt{\frac{16}{9} + \frac{9}{9}} \right \} = \left \{\frac{-2 \pm 5}{3}\right \} \]

The second derivative of the objective is 6x + 4, so that

    \[ f"\left (\frac{-2 \pm 5}{3}\right ) = 6 \left (\frac{-2 \pm 5}{3}\right ) + 4 = 6\cdot \frac{ \pm 5}{3} \]

which identifies x_1 = \frac{-7}{3} as a local maximum and x_2 = 1 as a global minimum. Note that both values indeed lie within the domain [-4, 2]
Global Extremizers: By the Weierstrass theorem, we know that the global extremizers exist. We identify them by comparing the interior solutions against the boundary points. We have

    \[ f(-4) = (-4)^3 + 4(-4)^2 - 3(-4) + 9 = -64 + 64 + 12 + 9 = 21 \]

    \[\begin{split} f\left (\frac{-7}{3}\right ) &= \left (\frac{-7}{3}\right )^3 + 4\left (\frac{-7}{3}\right )^2 - 3\left (\frac{-7}{3}\right ) + 9 = -\frac{343}{27} + \frac{588}{27} + 7 + 9 \\&= \frac{-343 + 588 + 432}{27} = \frac{677}{27} \approx 25.07 \end{split}\]

    \[ f(1) = (1)^3 + 4(1)^2 - 3(1) + 9 = 1 + 4 - 3 + 9 = 11 \]

    \[ f(2) = (2)^3 + 4(2)^2 - 3(2) + 9 = 8 + 16 - 6 + 9 = 27 \]

Therefore, the interior local minimum constitutes the global minimum, but the interior local maximum is surpassed at the boundary, such that x=2 is the global maximizer.


d. A Multivariate Objective

Determine the global extrema of f:\mathbb R^2\mapsto\mathbb R, x = (x_1,x_2)'\mapsto 4x_1x_2 - x_1^2 - 4x_2^2.
Hint: Recall that for unconstrained multivariate optimization, a different approach to limit behavior analysis is required.

This solution shows the “standard approach” to optimization as this exercise is the first on multivariate unconstrained optimization in the online exercises. Comment 2 below gives a quicker and more elegant solution that exploits a particularity of this problem.
Non-differentiability: The function, as a polynomial of finite order, is infinitely many times continuously differentiable, and points of non-differentiability are not an issue.
Boundary Points: The support has no boundary points.
Limit Behavior: We can neglect the limit for one of the extrema only if \lim_{\|x\|\to \infty}f(x) = \pm\infty. It is not straightforward to verify that this is the case, and we need to investigate this issue formally.

For expansion of f into any arbitrary direction v = (v_1,v_2)'\in\mathbb R^2 of the \mathbb R^2, we consider

    \[\begin{split} f(\lambda v) &= 4(\lambda v_1)(\lambda v_2) - (\lambda v_1)^2 - 4(\lambda v_2)^2 \\&= -(4v_1v_2 - v_1^2 - 2v_2^2)\lambda^2 \\&= - (v_1 - 2v_2)^2\lambda^2 \end{split}\]

for \lambda\in\mathbb R. For this expression,

    \[ \lim_{\lambda\to \pm\infty} f(\lambda v) = \begin{cases} 0 & \text{if } v_1 = 2v_2\\ -\infty & \text{else} \end{cases} \]

Hence, there are no global minima of f. For the global maximum, note that

    \[ V(\lambda):= \max_{v\in\{x\in\mathbb R^n: \|x\| = 1\}}f(\lambda v) = \max_{v\in\{x\in\mathbb R^n: \|x\| = 1\}} [- (v_1 - 2v_2)^2\lambda^2] = 0 \]

for all \lambda \in\mathbb R. Therefore, \lim_{\lambda\to -\infty} V(\lambda) = \lim_{\lambda\to \infty} V(\lambda) = 0, and a solution exists if for \lambda^*\in\arg\max_{\lambda\in\mathbb R}V(\lambda), we have V(\lambda) = f(\lambda^* v(\lambda^*)) \geq 0 for the v(\lambda)\in\{x\in\mathbb R^n: \|x\| = 1\} that was used to determine V(\lambda). Because any v(\lambda)\in\arg\max_{v\in\{x\in\mathbb R^n: \|x\| = 1\}}f(\lambda v) yields the same function V(\lambda), we can simply pick v(\lambda) = (2,1)'. Then, because V(\lambda) is a constant function that does not vary with \lambda, any \lambda\in\mathbb R is a critical point of V(\lambda) = f(\lambda v(\lambda)) and yields V(\lambda) = 0, such that for any \lambda\in\mathbb R, v = \lambda (2,1)' is a local and thus a global maximizer of f.
Accordingly, the set of global maximizers is \arg\max_x f(x) = \{ (2\lambda , \lambda)': \lambda\in\mathbb R\}, and the global maximum is f(x) = 0.
Comment 1: This function is an example of an optimization problem with infinitely many maximizers, i.e. |\arg\max_x f(x)| = \infty. Still, the global maximum is unique; there is just one maximal value attained at all maximizers.
Comment 2: You could have avoided the standard optimization procedure altogether by noting that \forall x\in\mathbb R^2: f(x)\leq 0 using the binomial formula:

    \[ f(x) = 4x_1x_2 - x_1^2 - 4x_2^2 = -(x_1 - 2x_2)^2 \leq 0 \]

and that there exist x^*\in\mathbb R^2 (namely x^*\in \{ (2z, z)': z\in\mathbb R\}) with f(x^*) = 0 \geq f(x) \forall x\in \mathbb R^2, which is exactly the definition of a global maximizer. Together with the limit consideration that rules out global minima, this would also be a perfectly fine investigation of global extrema for the specific function f given.


e. Positive Definiteness cont’d

In the exercises of Chapter 3, we investigated definiteness of the second derivative of x'Ax for A = \begin{pmatrix} 1 & \alpha\\ \beta & 4\end{pmatrix}. Recall that the second derivative was A + A' and that for v\in\mathbb R^2,

    \[ v'(A + A')v = 2 (v_1^2 + (\alpha + \beta)v_1v_2 + 4v_2^2) \]

(i) Can you use an optimization problem approach to find the values for \alpha and \beta where A + A' is not positive semi-definite, i.e. where there exist v\in\mathbb R^2 for which v'(A + A')v < 0?

To help you with the solution, note that if we write v = \lambda v_0, we have

    \[v' (A + A')v = 2\lambda^2 (v_{0,1}^2 + (\alpha + \beta)v_{0,1}v_{0,2} + 4v_{0,2}^2) \]

Hence, the magnitude does not matter for the property of being strictly negative, and you can reduce the search for v with v'(A + A')v < 0 to a direction vector. Because the magnitude of the direction vector does not matter and as if v_1 = 0, then the expression is weakly positive, there is no loss in setting v_{0,1} = 1 and restricting the search to the value v_{0,2} that yields v'(A + A')v < 0.

To find v\in\mathbb R^2 with v'(A + A')v < 0, we can solve

    \[ \min_{z\in\mathbb R} 1 + (\alpha + \beta)z + 4z^2 \]

and investigate which combinations of \alpha and \beta yield either a local minimum with 1 + (\alpha + \beta)z + 4z^2 < 0 or a left/right limit -\infty as then, for v = (1,z)', it holds that v'(A + A')v < 0.
Limit: Regardless of \alpha + \beta, the square term dominates in the limit, so that as v_2 increases indefinitely in absolute value, the objective becomes strictly positive. Hence, there are no limit solutions.
Interior Minimum: The first order condition is

    \[ 8z + (\alpha + \beta) = 0 \hspace{0.5cm}\Leftrightarrow\hspace{0.5cm} z = -\frac{\alpha + \beta}{8} \]

The second derivative of the objective is equal to 8>0, so that this is indeed a local minimizer (and in fact, the global minimizer, as the left and right limit are +\infty and the function is continuously differentiable everywhere). This solution yields the objective value

    \[\begin{split} 1 + (\alpha + \beta)\left (-\frac{\alpha + \beta}{8}\right ) + 4\left (-\frac{\alpha + \beta}{8}\right )^2 &= 1 - \frac{(\alpha + \beta)^2}{8} + \frac{(\alpha + \beta)^2}{16} \\& = 1 - \frac{(\alpha + \beta)^2}{16} \end{split}\]

This is strictly smaller than zero whenever (\alpha + \beta)^2 > 16, i.e. |\alpha + \beta| > 4.
Consequently, A + A' is indefinite for arbitrary \alpha \in \mathbb R and \beta\in\mathbb R such that \beta > 4 - \alpha or \beta < -\alpha - 4.


(ii) Can you find the range of \alpha + \beta where A + A' is positive definite? (Solve (i) first.)

According to the solution of (i), the global minimum of v' (A + A')v is 1 - \frac{(\alpha + \beta)^2}{16}. Therefore, A + A' is positive definite whenever

    \[ 1 > \frac{(\alpha + \beta)^2}{16} \hspace{0.5cm}\Leftrightarrow\hspace{0.5cm} (\alpha + \beta)^2 < 16 \hspace{0.5cm}\Leftrightarrow\hspace{0.5cm} \alpha + \beta \in (-4, 4) \]

Comment 1: As we have also seen in the exercises of Chapter 3, there is a “border” \alpha + \beta \in \{-4, 4\} for which A + A' is positive semi-definite but not positive definite. Here, we have argued that for \alpha + \beta \in (-4, 4), we have “strict” positive definiteness, whereas outside [-4, 4], A + A' is indefinite. Hence, we can classify definiteness of A + A' by splitting the real line for \alpha + \beta.
Comment 2: You should take away from this exercise that optimization problems are useful in determining definiteness of a matrix, and that this approach is more conclusive/comprehensive as the “direct” approach we usually take when checking whether v'Av consists only of square expressions or can be reduced to a binomial formula (cf. the exercise for Chapter 3).


Exercise 3: Constrained Optimization

a. Finding the Optimal Direction

Consider the function f:\mathbb R^2\mapsto\mathbb R, x=(x_1,x_2)'\mapsto x_1^2x_2 - x_2^2 x_1.

(i) For a given \lambda\in\mathbb R, which direction v\in D(2) of the \mathbb R^2 yields the largest and smallest value of f(\lambda v), when the set of directions is defined to have normalized length, i.e. D(2) = \{v\in\mathbb R^2: \|v\| = 1\}? You may consider the Euclidean norm.
Hint 1: For v\in\mathbb R^2, \|v\|_2 = 1 is equivalent to v_1^2 + v_2^2 = 1, which may be an easier constraint to work with.
Hint 2: D(2) is closed and bounded and thus compact, so you need not worry about solution existence.
Hint 3: By hint 2, it is not necessary to consult the second order condition, you can simply compare the values for each candidate.
Hint 4: There will be 6 candidates in total, resulting from two cases. To determine which is the largest and smallest, you can exploit that once you solved for v_2(v_1) in either case, you should obtain a function f(v_1, v_2(v_1)) that is is strictly monotonic in v_1.

As you may guess from the fact that there are 4 hints, the problem is not particularly easy. Don’t feel bad peaking into the solution if you get stuck.

For v\in\mathbb R^2 and \lambda \in \mathbb R,

    \[ f(\lambda v) = (\lambda v_1)^2(\lambda v_2) - (\lambda v_2)^2 (\lambda v_1) = \lambda^3 (v_1^2v_2 - v_2^2 v_1) \]

With \lambda \in\mathbb R fixed, optimization of this function is equivalent (in terms of the extremizers) to optimization of the objective o(v) = v_1^2 v_2 - v_2^2 v_1 on \mathbb R^2. Define g(v) = v_1^2 + v_2^2 - 1 as the constraint function on \mathbb R^2. Then, we are concerned with solving

    \[ \max_{v\in\mathbb R^2} o(v) \hspace{0.5cm}\text{subject to}\hspace{0.5cm}g(v) = 0 \]

which is the standard optimization setup when we have one equality constraint.
To determine the candidates according to Lagrange’s first order condition, we look for v\in\mathbb R^2 for which there exists \mu\in\mathbb R such that \nabla o(v) = \mu \nabla g(v) (the variable \lambda is already occupied here, that’s why we choose \mu as the multiplier).
We have

    \[ \nabla o(v) = (2v_1v_2 - v_2^2, v_1^2 - 2v_1v_2) \hspace{0.5cm}\text{and}\hspace{0.5cm} \nabla g(v) = (2v_1, 2v_2) \]

Setting \nabla o(v) = \mu \nabla g(v) gives the system of equations

    \[ \begin{split} I. \hspace{0.5cm}& 2v_1v_2 - v_2^2 = 2\mu v_1\\ II. \hspace{0.5cm}& v_1^2 - 2v_1v_2 = 2\mu v_2\\ III. \hspace{0.5cm}& v_1^2 + v_2^2 = 1 \end{split} \]

Adding I. and II., we obtain

    \[ v_1^2 - v_2^2 = 2\mu (v_1 + v_2) \hspace{0.5cm}\Leftrightarrow\hspace{0.5cm} (v_1 - v_2)(v_1 + v_2) = 2\mu (v_1 + v_2) \]

This is solved by either v_1 + v_2 = 0 (i.e. v_2 = -v_1) or by 2\mu = v_1 - v_2, which gives two cases.
Case 1: If v_2 = -v_1, then from III., we obtain that 2v_1^2 = 1 and thus v_1^2 = \frac{1}{2}. This gives the candidates

    \[ v^* = (\pm 1) \cdot \left (\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}\right ) \]

v_2 = v_1 yields

    \[ o(v) = v_1^2 (-v_1) - (-v_1)^2v_1 = -2v_1^3 = \begin{cases} -\frac{1}{\sqrt{2}} &\text{for }v_1 = \frac{1}{\sqrt{2}}\\\frac{1}{\sqrt{2}} &\text{for }v_1 =- \frac{1}{\sqrt{2}}\end{cases} \]

Case 2: If 2\mu = v_1 - v_2, plugging this into either I. or II. gives

    \[ v_1(v_1 - v_2) = 2v_1v_2 - v_2^2 \hspace{0.5cm}\Leftrightarrow\hspace{0.5cm} v_1^2 + v_2^2 = 3 v_1v_2 \]

with III., one obtains

    \[ 3 v_1v_2 = 1 \hspace{0.5cm}\Leftrightarrow\hspace{0.5cm} v_2 = \frac{1}{3v_1} \]

Plugging this into III.,

    \[ v_1^2 + \frac{1}{9v_1^2} = 1 \]

This can be used to solve for the value of v_1^2. Unfortunately, this gives a variety of solutions for v_1; however, as we will see, they have a manageable structure that keeps the problem tractable.
The equation above is equivalent to (as v_1\neq 0 by 3 v_1v_2 = 1)

    \[ v_1^4 - v_1^2 + \frac{1}{9} = 0 \]

and thus

    \[ v_1^2 = \frac{1}{2}\pm \sqrt{\frac{1}{4} - \frac{1}{9}} = \frac{3}{6}\pm \sqrt{\frac{9}{36} - \frac{4}{36}}= \frac{3 \pm \sqrt{5}}{6} \]

Accordingly, we get candidates

    \[ v_1\in\left \{-\sqrt{\frac{3 + \sqrt{5}}{6}}, -\sqrt{\frac{3 - \sqrt{5}}{6}}, \sqrt{\frac{3 - \sqrt{5}}{6}}, \sqrt{\frac{3 + \sqrt{5}}{6}}\right \} \]

As Hint 4 suggests, we can investigate the implicit value for v_1 to get some structure on these candidates:

    \[ o(v_1, v_2(v_1)) = v_1^2 v_2(v_1) - (v_2(v_1))^2 v_1 = \frac{v_1}{3} - \frac{1}{9v_1} \]

which is strictly monotonically increasing in v_1. Thus, in Case 2 the minimal value is attained for v_1 = -\sqrt{\frac{3 + \sqrt{5}}{6}} whereas the largest value is for v_1 = \sqrt{\frac{3 + \sqrt{5}}{6}}.
To compare the cases, note that \sqrt{\frac{3 + \sqrt{5}}{6}} < \sqrt{\frac{3 + \sqrt{9}}{6}} = 1 so that in the second case,

    \[ o(v_1, v_2(v_1)) < \frac{1}{3} - \frac{1}{9} = \frac{2}{9} < \frac{1}{2} < \frac{1}{\sqrt{2}} \]


    \[ o(v_1, v_2(v_1)) > \frac{-1}{3} - \frac{-1}{9} = -\frac{2}{9} > -\frac{1}{2} > -\frac{1}{\sqrt{2}} \]

such that Case 1 yields the global extrema. Accordingly, the constrained global maximum is \frac{1}{\sqrt{2}}, which is attained at v = \left (-\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}\right ), and the constrained global minimum is -\frac{1}{\sqrt{2}}, which is attained at v = \left (\frac{1}{\sqrt{2}}, -\frac{1}{\sqrt{2}}\right ).


(ii) Can you use the result of (i) to say something about the unconstrained optimization problems

    \[ \max_{x\in\mathbb R^2} x_1^2 x_2 - x_2^2 x_1 \hspace{0.5cm}\text{and}\hspace{0.5cm} \min_{x\in\mathbb R^2} x_1^2 x_2 - x_2^2 x_1? \]

Recall from (i) that \max_{v\in\mathbb R^2:\|v\|=1}f(\lambda v) = \frac{\lambda^3}{\sqrt{2}}. Accordingly, for \lambda\to\infty, f(\lambda v)\to\infty. This rules out existence of a global maximum. Similarly, for \lambda\to-\infty, f(\lambda v)\to-\infty, which rules out the global minimum. Hence, neither of the given problems have solutions.
Comment: Of course, you could also have argued that \min_{v\in\mathbb R^2:\|v\|=1}f(\lambda v) = -\frac{\lambda^3}{\sqrt{2}}, and that as \lambda\to\pm\infty, this expression diverges to \mp\infty, to rule out either type of extremum.


b. Economic Formulation and Application

Suppose we have two individuals, Martin and Anna. Both like to spend their free time performing only two activities: relaxing (r) and going climbing (c). Otherwise, they don’t derive utility from any other source. Suppose that an hour of relaxation costs 1€ (e.g. for a Netflix account, food and drinks, or whatever you like to consume in your free time), and an hour of climbing costs 10€ (equipment, gym subscription, etc.). Suppose that both Martin and Anna are employed at the same job, and can work for a net hourly wage of 15€ to generate income; they both have no initial wealth. Their preferences differ: we have

    \[ u_M(r,c) = r^{\frac{1}{3}}c^{\frac{2}{3}} \]

for Martin and

    \[ u_A(r,c) = \sqrt{rc} \]

for Anna. This means that Martin puts more weight on climbing whereas both activities are equally weighted for Anna.

(i) Formulate the problem that Anna faces when maximizing utility within a given day that has 24 hours. Simplify the problem as much as possible.

When h denote hours worked,

    \[ \max_{c,r, h\in\mathbb R}\sqrt{rc} \hspace{0.5cm}\text{subject to}\hspace{0.5cm} c + r + h \leq 24,\ 10c + 1r \leq 15h,\ h,c,r\geq 0 \]

We can note a few things about this problem to simplify it. First of all, doing nothing does not generate utility and income, and because utility is strictly increasing at (c,r)\in (0,\infty)^2, this will never be optimal. accordingly, c+r+h\leq 24 will bind at the optimum, and we can set h = 24 - c - r. This allows to get rid of h as a choice variable altogether and solve the equivalent problem

    \[ \max_{c,r\in\mathbb R}\sqrt{rc} \hspace{0.5cm}\text{subject to}\hspace{0.5cm} c + r \leq 24,\ 10c + 1r \leq 15\cdot (24 - c - r),\ c,r\geq 0 \]

Moreover, c = 0 or r = 0 yields zero utility, which is strictly surpassed by any (c,r)\in (0,\infty)^2, such that c,r\geq 0 will never bind. Similarly, if c+r = 24, there is no income, and the allocation is not sustainable. Thus, we can neglect the inequality constraints in optimization and ex-post eliminate critical points that do not satisfy c,r\geq 0 or c+r = 24, if there are any.
Strict monotonicity of u_A on (0,\infty)^2 also implies that the budget constraint always binds, as when not all income is spent, utility can be strictly increased by spending more within the budget. This gives

    \[ 10c + 1r = 15\cdot (24 - c - r) \hspace{0.5cm}\Leftrightarrow\hspace{0.5cm} 25c + 16r = 360 \]

This equality can again be used to eliminate a choice variable:

    \[ c = \frac{72}{5} - \frac{16}{25}r \]

where positivity of c requires 72 - \frac{16}{5}r \geq 0, or equivalently r \leq \frac{45}{2} = 22.5

Thus, the simplified problem to solve is

    \[ \max_{r\in\mathbb R}u_A\left (\frac{72}{5} - \frac{16}{25}r, r\right ) \hspace{0.5cm}\text{subject to}\hspace{0.5cm} r \in (0, 22.5) \]

or, respectively,

    \[ \max_{r\in\mathbb R}\sqrt{\frac{72}{5}r - \frac{16}{25}r^2} \hspace{0.5cm}\text{subject to}\hspace{0.5cm} r \in (0, 22.5) \]

Comment: You don’t need any of the simplifications; you could at any intermediate problem apply the methods that we discussed in the course (Kuhn-Tucker or Lagrange). Sometimes, especially when we have more than 2 variables, we do not make the last “simplifying” step of plugging in the budget constraint as this may complexify the objective too much. Thus, the solution of (ii) also presents the approach without plugging the budget constraint into the objective.


(ii) How can you interpret the budget constraint that you obtain after simplification?

The constraint that we had obtained by bringing c and r to one side is

    \[ 25c + 16r = 360 \]

This can be interpreted as an “opportunity cost budget constraint”: effectively, Anna has the resources to make 360€. By either relaxing or climbing, she faces the opportunity cost of not working (15€) plus the actual cost of the activity, which gives total opportunity cost of 25€ per unit of climbing and 16€ per unit of relaxing.


(iii) Solve Anna’s utility maximization problem (finding the optimal distribution of time across activities is enough; the value of utility does not matter).

With substituted budget constraint: First, the solution solving the most simplified problem of (i) is given. The solution to the constrained problem we obtain when not plugging the budget constraint into the objective is given below.
We are concerned with solving

    \[ \max_{r\in\mathbb R}\sqrt{\frac{72}{5}r - \frac{16}{25}r^2} \hspace{0.5cm}\text{subject to}\hspace{0.5cm} r \in (0, 22.5) \]

Note that this problem is equivalent to the one with a more simplistic objective

    \[ \max_{r\in\mathbb R} \frac{72}{5}r - \frac{16}{25}r^2 \hspace{0.5cm}\text{subject to}\hspace{0.5cm} r \in (0, 22.5) \]

in terms of the extremizers (but of course not the value of the objective).
Note that [0,24] is compact and f(r) = \frac{72}{5}r - \frac{16}{25}r^2 is continuous. Hence, f assumes a global maximum and on [0,24] by Weierstrass. Because f(0) = 0 and f(24) = \frac{72}{5}24 - \frac{16}{25}24^2 < 0 and there exist r\in(0,24) for which f(r)>0 (e.g. r=1 for which f(r) = \frac{38}{3}), the global maximum is interior and thus a local maximum identifiable by the interior solution conditions. The first order condition of this “unconstrained” problem is

    \[ \frac{72}{5} - \frac{32}{25}r = 0 \hspace{0.5cm}\Leftrightarrow\hspace{0.5cm} r = \frac{25}{32}\cdot \frac{72}{5} = \frac{5\cdot 9}{4} = \frac{45}{4} = 11.25 \]

Note that the second derivative of the objective is equal to - \frac{32}{25} everywhere, so that every critical point is a local maximizer. Plugging r in to the budget constraint,

    \[ c = \frac{72}{5} - \frac{16}{25}r = \frac{72}{5} - \frac{16}{25}\cdot \frac{45}{4} = \frac{36}{5} = 7.2 \]

These quantities satisfy all inequality constraints and thus constitute a feasible solution. Hence, Anna works for 24 - \left (7.2 + 11.25\right ) = 5.55 hours, goes climbing for 7.2 hours and relaxes for 11.25 hours.
As a sanity check, you can verify again that the budget clears with equality: Anna earns 15\cdot \frac{111}{20} = \frac{3}{4}\cdot 111 = 83.25€, and her activity costs 7.2\cdot 10€ + 11.25\cdot 1€ = 83.25€.
Without substituted budget constraint: If we do not substitute for the budget constraint, we solve

    \[ \max_{r\in\mathbb R}\sqrt{cr} \hspace{0.5cm}\text{subject to}\hspace{0.5cm} 25c + 16r = 360,\ r \in (0, 22.5) \]

Again, the equivalent problem (in terms of the extremizers) with more simplistic objective is

    \[ \max_{r\in\mathbb R}cr \hspace{0.5cm}\text{subject to}\hspace{0.5cm} 25c + 16r = 360,\ c + r \in (0, 22.5) \]

Note that the budget set is compact (cf. Chapter 3). Thus, cr will attain a global maximum and minimum on the budget set. For c=0 or r = 0, cr = 0 < \tilde c\tilde r for any \tilde c, \tilde r > 0. Hence, the minimum lies on the boundary whereas the maximum is identifiable by Lagrange’s conditions. Lagrange’s first order condition is

    \[ \nabla (cr) = \lambda \nabla (25c + 16r - 360) \hspace{0.5cm}\Leftrightarrow\hspace{0.5cm} \begin{cases} r &= \lambda\cdot 25\\ c &= \lambda \cdot 16\\ 360 &= 25c + 16r \end{cases} \]

Plugging the first two lines into the third,

    \[ 360 = 25\cdot (16\lambda) + 16(\cdot 25\lambda) \hspace{0.5cm}\Leftrightarrow\hspace{0.5cm} \lambda = \frac{360}{2\cdot 25\cdot 16} = \frac{360}{800} = \frac{9}{20} \]

This gives

    \[ r = \lambda\cdot 25 = \frac{5}{4}\cdot 9 = \frac{45}{4} \hspace{0.5cm}\text{and}\hspace{0.5cm} c = \lambda \cdot 16 = \frac{4}{5}\cdot 9 = \frac{36}{5} \]

These quantities satisfy all inequality constraints and thus constitute a feasible solution. To check that this point indeed constitutes a local maximum, we check the Bordered Hessian,

    \[ H_\mathcal L (x) = \begin{pmatrix} 0 & -\nabla g(x)\\ -\nabla g'(x) & H_f(x) - \lambda H_g(x) \end{pmatrix} \]

Because H_g(x) = \mathbf 0_{2\times 2} and H_f(x) = \begin{pmatrix} 0 & 2\\ 2 & 0\end{pmatrix}, we have

    \[ H_\mathcal L (x) = \begin{pmatrix} 0 & - 25 & -16\\ -25 & 0 & 2\\ -16 & 2 & 0 \end{pmatrix} \]


    \[ \det H_\mathcal L (x) = (- 25)(- 16)2 + (- 25)(- 16)2 > 0 \]

so that \text{sgn}(\det H_\mathcal L (x)) = \text{sgn}[(-1)^2], which implies that we have found a local maximizer. Because this is the unique local maximizer, it is also the global maximizer.
Hence, Anna works for 24 - \left (7.2 + 11.25\right ) = 5.55 hours, goes climbing for 7.2 hours and relaxes for 11.25 hours.
As a sanity check, you can verify again that the budget clears with equality: Anna earns 15\cdot \frac{111}{20} = \frac{3}{4}\cdot 111 = 83.25€, and her activity costs 7.2\cdot 10€ + 11.25\cdot 1€ = 83.25€.


(iv) Assume now that Anna has some savings and does not need to work on the day we consider in our optimization problem here. Given her utility function, what is the minimum amount of money that she needs to spend to receive at least the same as before? (Even though she does not need to work here, she can still not spend more than 24 hours on both activities combined.)
Hint 1: Once you have simplified the problem to have only one choice variable, it may be instructive to investigate whether or not the time budget constraint binds by looking at the first derivative of the objective.
Hint 2: Don’t worry if your results don’t give nice numbers anymore, you will need a calculator for this exercise. You may round all intermediate results to two digits.

We first need to determine the level of utility Anna derives from her optimal time allocation: recall from (iii) that Anna chooses c = \frac{36}{5} =\frac{4}{5}\cdot 9 and r = \frac{45}{4} = \frac{5}{4}\cdot 9. Accordingly,

    \[ u_A\left (\frac{4}{5}\cdot 9, \frac{5}{4}\cdot 9\right ) = \sqrt{\left (\frac{4}{5}\cdot 9\right )\left (\frac{5}{4}\cdot 9\right )} = \sqrt{9^2} = 9 \]

The problem we are concerned with is

    \[ \min_{c,r} 10c + 1r \hspace{0.5cm}\text{subject to}\hspace{0.5cm} u_A(c,r)\geq 9,\ c + r\leq 24 \]

where it was already used that the non-negativity constraints for c and r do not bind because this would yield zero utility which violates the constraint. Furthermore, if the constraint does not bind, then we could lower expenditures and still satisfy the constraint because u_A(c,r) is continuous. Hence, we can equivalently solve

    \[ \min_{c,r} 10c + 1r \hspace{0.5cm}\text{subject to}\hspace{0.5cm} u_A(c,r) = 9,\ c + r\leq 24 \]

Because x^2 is a strictly monotonic transformation on [0,\infty), u_A(c,r) = 9 is equivalent to cr = 9^2 = 81, which gives r = \frac{81}{c}. Plugging this into the objective and the other constraint, the problem becomes

    \[ \min_{c} 10c + \frac{81}{c} \hspace{0.5cm}\text{subject to}\hspace{0.5cm} c + \frac{81}{c}\leq 24 \]

The first derivative of the objective is

    \[10 + (-1)\cdot \frac{81}{c^2}\]

which is equal to zero for

    \[ c^* = \frac{9}{\sqrt{10}} \approx 2.85 \]

For c<c^*, this expression is strictly smaller than zero, whereas it strictly exceeds zero for c>c^*. Hence, the objective strictly decreases on [0,2.85) and strictly increases on [2.85,\infty). Plugging c^* into the utility constraint, we arrive at

    \[ r^* = \frac{81}{c^*} = \frac{81\cdot \sqrt{10}}{9} = 9\cdot \sqrt{10} \approx 28.46 \]

such that (c^*,r^*) is not sustainable under c+r \leq 24. Hence, we know that the problem has no interior solution. The feasible set of the problem is given by

    \[ \{c\in\mathbb R_+: c + \frac{81}{c}\leq 24\} = \{c\in\mathbb R: c^2 - 24c + 81 \leq 0\} \]

To compute a more informative representation of this set, note that

    \[ c^2 - 24c + 81 = 0 \]


    \[ c\in \left \{12 \pm \sqrt{144 - 81}\right \} = \left \{12 \pm 3\sqrt{7}\right \} \approx \{4.06, 19.94\} \]


    \[ \frac{d}{dc}(c^2 - 24c + 81) = 2c - 24 \begin{cases} < 0 & \text{for }c=4.06\\ > 0 & \text{for }c= 19.94 \end{cases} \]

Hence, c^2 - 24c + 81 intersects the horizontal axis from above at c=4.06 and from below at c= 19.94. Because this polynomial is continuous, for c\in(4.06,19.94), this means that c^2 - 24c + 81 < 0. Accordingly, the problem’s feasible set is [4.06, 19.94]. Because the objective is strictly increasing on this set, we know that the smallest feasible value solves the problem, such that c^* = 4.06. This gives r^* = 24 - c^* = 19.94 (because c + \frac{81}{c}\leq 24 holds with equality on the boundary of [4.06, 19.94]).
In conclusion, Anna’s expenditures are

    \[ 10€\cdot 4.06 + 1€ \cdot 19.94 = 60.54€ \]

In comparison to her previous spendings when she had to earn her expenditures on the same day, which were equal to  83.25€, Anna spends 22.71€ less.


(v) How do you explain the difference in results of (iv) and (iii)?

In both scenarios, Anna attains the same level of utility. However, when she has to work for her money, her time constraint is effectively tighter as she can spend less time on utility-generating activities. This imposes a stronger restriction on expenditure minimization as in the case where she has all 24 hours of the day to generate utility, and therefore results in a relatively “inferior” allocation.
If Anna has more time at her hands, she can spend more of it in the cheaper activity (here: relaxing) and generate larger complementarity gains for the more costly activity. This effect can be clearly seen from the fact that in the scenario where Anna spends less time in utility-generating activities, her time spent in the more expensive activity is almost twice as large (7.2 vs. 4.06 hours).


(vi) How much would Martin need to earn per hour to afford Anna’s level of utility if he has no savings? You may not be able to solve for the wage to the cent; thus, assume that the wage is an integer value. You can use without proof that utility is strictly increasing in the wage and check in steps of 1 whether a given wage yields at least the desired level of utility.
Hint: Solve Martin’s utility maximization problem in analogy to Anna’s with variable wage to derive the maximal utility as a function of the wage in a first step.

Denote by w Martin’s wage. In analogy to (iii), the problem we are concerned with is

    \[ \max_{c,r\in\mathbb R}c^{\frac{2}{3}}r^{\frac{1}{3}} \hspace{0.5cm}\text{subject to}\hspace{0.5cm} c + r < 24,\ (10 + w)c + (1 + w)r =24w,\ c,r > 0 \]

where the opportunity cost formulation of the budget constraint (cf. (ii)) was used. Plugging r = \frac{24w}{1+w} - \frac{10+w}{1+w}c into the objective (which we take to the power of 3 for computational simplicity), we get the “unconstrained” problem

    \[ \max_{c\in\mathbb R}c^2 \left (\frac{24w}{1+w} - \frac{10+w}{1+w}c\right ) \hspace{0.5cm}\text{subject to}\hspace{0.5cm} c\in(0,24) \]

This time, it is more simplistic to substitute r because the expression is not squared; but technically, substituting r again would of course also work. Multiplying out the objective, we get

    \[ \max_{c\in\mathbb R} \frac{24w}{1+w}c^2 - \frac{10+w}{1+w}c^3 \hspace{0.5cm}\text{subject to}\hspace{0.5cm} c\in(0,24) \]

The first order condition is

    \[ 2\frac{24w}{1+w}c - 3\frac{10+w}{1+w}c^2 = 0 \]

Because c=0 is not a solution, we can divide by c and obtain

    \[ c(w) = \frac{48w}{1+w}\frac{1+w}{3\cdot(10 + w)} = \frac{16w}{10 + w} \]

Plugging this into r,

    \[\begin{split} r(w) &= \frac{24w}{1+w} - \frac{10+w}{1+w}c(w) \\&= \frac{24w}{1+w} - \frac{10+w}{1+w}\frac{16w}{10 + w} \\&= \frac{8w}{1+w} \end{split}\]

Accordingly, Martin’s utility given wage w is

    \[\begin{split} u_M(w) &= u_M(c(w),r(w)) = \left [\left (\frac{16w}{10 + w}\right )^2\frac{8w}{1+w}\right ]^{\frac{1}{3}} \\&= \left (\frac{4\cdot 8^3}{(10 + w)^2(1+w)}\right )^{\frac{1}{3}}w \\&= \frac{4^{\frac{1}{3}}\cdot 8w}{[(10 + w)^2(1+w)]^{\frac{1}{3}}} \end{split}\]

We want to find the wage w for which

    \[ u_M(w) = 9 \hspace{0.5cm}\Leftrightarrow\hspace{0.5cm} \frac{w^3}{(10 + w)^2(1+w)} = \left (\frac{9}{4^{\frac{1}{3}}\cdot 8}\right )^3 = \frac{1}{4}\cdot \left (\frac{9}{8}\right )^3 \approx 0.355957 \]

We use without proof that the LHS strictly increases in the wage. The first candidate is Anna’s wage:

    \[ \frac{w^3}{(10 + w)^2(1+w)}\bigr|_{w=15} = 0.3375 < 0.355957 \]

Unsurprisingly, because Martin puts more weight on the more expensive activity, with equal wage, he can not attain the same level of utility. However, the difference is not large. For w=16,

    \[ \frac{w^3}{(10 + w)^2(1+w)}\bigr|_{w=16} = 0.3564219 > 0.355957 \]

such that the wage at which both attain equal utility is an element of [15,16], and earning 1€ more per hour already allows him to attain a slightly larger level of utility than Anna.


(vii) What level of utility can Martin maximally attain as his wage increases? Why is utility not unbounded above? What can you say about Martin’s utility and time allocation when he does not have to work from this investigation?

From the previous exercise, we know that

    \[\begin{split} u_M(w) &= \frac{4^{\frac{1}{3}}\cdot 8w}{[(10 + w)^2(1+w)]^{\frac{1}{3}}} \\&= 4^{\frac{1}{3}}\cdot 8 \left (\frac{w^3}{(10 + 20w + w^2)(1+w)}\right )^{\frac{1}{3}} \\&= 4^{\frac{1}{3}}\cdot 8 \left (\frac{w^3}{w^3 + 21w^2 + 30w + 10}\right )^{\frac{1}{3}} \end{split}\]

The fraction in parentheses is asymptotically driven only by the polynomial term with largest power, i.e. x^3, such that

    \[ \lim_{w\to\infty} \frac{w^3}{w^3 + 21w^2 + 30w + 10} = 1 \]


    \[ \lim_{w\to\infty}u_M(w) = 4^{\frac{1}{3}}\cdot 8 \cdot 1^{\frac{1}{3}} = 4^{\frac{1}{3}}\cdot 8 \approx 12.70 \]

which is the maximum utility Martin can attain.
Utility is not unbounded above because Martin still faces the restriction of having only 24 hours a day.
The limit w\to\infty resembles the case where Martin does not have to work, as the time needed to generate the income required for financing his activities tends to zero as w\to\infty. Therefore, when Martin does not have to work, he will attain the level u_M = 12.70. The time allocated to activities in this case are

    \[ c = \lim_{w\to\infty} c(w) = \lim_{w\to\infty}\frac{16w}{10 + w} = 16 \]


    \[ r = \lim_{w\to\infty} r(w) = \lim_{w\to\infty}\frac{8w}{1+w} = 8 \]

Comment: This case is different from expenditure minimization when one does not have to work, as we considered in (iv). Here, cost do not matter at all because financial resources do not impose a restriction on optimization.


(viii) Consider the problem where now, c and r are tradeable goods, e.g. cookies and rice (in kg). Suppose that Martin and Anna live on a deserted island, on which there are 10 boxes of cookies and 12 kg of rice. Formulate the welfare-maximizing resource allocation problem when equal weight is given to both individuals and simplify it as much as possible. How do you proceed to find the solution (verbally)?

The objective is

    \[ \max_{c_A, c_M, r_A, r_M\in\mathbb R_+} \sqrt{c_Ar_A} + c_M^{\frac{2}{3}}r_M^{\frac{1}{3}} \hspace{0.5cm}\text{subject to}\hspace{0.5cm} c_A + c_M = 10,\ r_A + r_M = 12,\ \]

We can get rid of the constraints to arrive at an “unconstrained” problem:

    \[ \max_{c_M, r_M\in\mathbb R_+} \sqrt{(10 - c_M)(12 - r_M)} + c_M^{\frac{2}{3}}r_M^{\frac{1}{3}} \]

The word “unconstrained” is put in quotes as we still have to respect (c_M,r_M)\in [0,10]\times[0,12]. Note that the interval in \mathbb R^2 is compact, and that there is a solution. We will compare interior solutions to all border solutions, i.e. those solutions obtained from giving all resources to either individual (giving one resource completely to one and the other to the other individual yields zero aggregate utility. This scenario can be disregarded in maximization).


(ix) What is the allocation that solves the problem of (viii)?
Hint: Beware of border solutions.

The first order condition is

    \[\begin{split} (-1)\cdot\frac{1}{2}\sqrt{\frac{12 - r_M}{10 - c_M}} + \frac{2}{3}\left (\frac{r_M}{c_M}\right )^{\frac{1}{3}} &= 0 \\ (-1)\cdot\frac{1}{2}\sqrt{\frac{10 - c_M}{12 - r_M}} + \frac{1}{3}\left (\frac{r_M}{c_M}\right )^{-\frac{2}{3}} &= 0 \end{split}\]

or equivalently

    \[\begin{split} \sqrt{\frac{12 - r_M}{10 - c_M}} &= \frac{4}{3}\left (\frac{r_M}{c_M}\right )^{\frac{1}{3}} \\ \sqrt{\frac{12 - r_M}{10 - c_M}} &= \frac{3}{2}\left (\frac{r_M}{c_M}\right )^{\frac{2}{3}} \end{split}\]

Dividing the equations gives

    \[ 1 = \frac{8}{9}\left (\frac{r_M}{c_M}\right )^{-\frac{1}{3}} \hspace{0.5cm}\Leftrightarrow\hspace{0.5cm} r_M = \left ( \frac{8}{9} \right )^3 c_M \]

Multiplying the equations of the first order condition with each other, we obtain

    \[ \frac{12 - r_M}{10 - c_M} = 2 \frac{r_M}{c_M} \hspace{0.5cm}\Leftrightarrow\hspace{0.5cm} \frac{12 - r_M}{r_M} = 2 \frac{10 - c_M}{c_M} \]

Combining these two results,

    \[ \frac{12 - \left ( \frac{8}{9} \right )^3 c_M}{\left ( \frac{8}{9} \right )^3 c_M} = 2 \frac{10 - c_M}{c_M} \hspace{0.5cm}\Leftrightarrow\hspace{0.5cm} 12 - \left ( \frac{8}{9} \right )^3 c_M = \left ( \frac{8}{9} \right )^3 (20 - 2 c_M) \]

which gives

    \[ \left ( \frac{8}{9} \right )^3c_M = \left ( \frac{8}{9} \right )^3 20 - 12 \hspace{0.5cm}\Leftrightarrow\hspace{0.5cm} c_M = \frac{\left ( \frac{8}{9} \right )^3 20 - 12}{\left ( \frac{8}{9} \right )^3} \approx 2.91 \]


    \[ r_M = \left ( \frac{8}{9} \right )^3 c_M \approx 2.05 \]

This gives the candidate allocation (c_M, r_M) = (2.91, 2.05) and (c_A, r_A) = (7.09, 9.95) with aggregate utility level

    \[\sqrt{c_Ar_A} + c_M^{\frac{2}{3}}r_M^{\frac{1}{3}} \approx  8.40 + 2.59 = 10.99 \]

The border solutions to consider for maximization are (c_A, r_A) = (10, 12) and (c_M, r_M) = (0, 0) with aggregate utility level \sqrt{10\cdot 12} = \sqrt{120} \approx 10.96 and (c_A, r_A) = (0, 0) and (c_M, r_M) = (10, 12) with aggregate utility level 10^{\frac{2}{3}}12^{\frac{1}{3}} \approx 10.63. Accordingly, the interior solution constitutes the welfare-maximizing allocation.

In this allocation, a large share of both resources is given to Anna. Intuitively, this result is because Anna puts more weight on the more abundant resource, here rice, which makes it easier to raise aggregate welfare by giving resources to her.


(xi) Finally, consider again the island scenario but now assume that Anna initially owns all the cookies and Martin owns all the rice. Assume that they can freely discuss exchanging the goods, have perfect information about all aspects of the trade and there is no power asymmetry between the two. At what ratio do they trade the goods, and what is the final allocation? How does aggregate welfare compare to the previous exercise?
Hint: You can express both agents’ utility to trading a given quantity of goods at a fixed ratio as a function of the ratio and the goods quantity, and then solve for concrete values that sustain an equilibrium by thinking about the condition that ensures that both agents do not want do deviate.

Without loss of generality, fix the “price” of rice to one, such that the value of cookies, p_c, is expressed in units of rice. Then, from a given trade volume of x boxes of cookies (and p_c \cdot x kgs of rice), Anna derives utility

    \[ U_A(x) = u_A\left (10 - x, p_c\cdot x\right ) = \sqrt{(10 - x)(p_c\cdot x)} = \sqrt{p_c}\sqrt{10x-x^2} \]

and for Martin,

    \[ U_M(x) = u_M(x, 12 - p_c\cdot x) = x^{\frac{2}{3}}(12 - p_c\cdot x)^{\frac{1}{3}} = (12x^2 - p_cx^3)^{\frac{1}{3}} \]

Either agent prefers to trade marginally more if \frac{d}{dx} U(x)>0 and marginally less if \frac{d}{dx} U(x)<0. Alternatively, to think more explicitly in terms of optimization, the equilibrium trade volume x must maximize both agents’ utility, and therefore satisfiy their first order condition. Thus, an equilibrium trade volume x^* is such that \frac{d}{dx} U_A(x) = \frac{d}{dx} U_M(x) = 0, as in this case, neither agent wants to deviate from the allocation. We have

    \[ \frac{d}{dx} U_A(x) = \sqrt{p_c}\frac{10-2x}{\sqrt{10x-x^2}} \]


    \[ \frac{d}{dx} U_M(x) = \frac{1}{3}\frac{24x - 3p_cx^2}{(12x^2 - p_cx^3)^{\frac{2}{3}}} \]

This means that irrespective of p_c, Anna accepts an allocation if 10-2x = 0 or respectively, x=5. This can be plugged in into Martin’s condition to obtain the equilibrium ratio of trade:

    \[ (24x - 3p_cx^2)|_{x=5} = 0 \hspace{0.5cm}\Leftrightarrow\hspace{0.5cm} 120 - 75p_c = 0 \hspace{0.5cm}\Leftrightarrow\hspace{0.5cm} p_c = \frac{120}{75} = \frac{8}{5} = 1.6 \]

Thus, in equilibrium, one box of cookies is traded for 1.6 kgs of rice. In total, Anna gives x=5 boxes of cookies to Martin and receives 1.6\cdot x = 8 kgs of rice. Accordingly, the final allocation is (c_A, r_A) = (10-5, 8) = (5,8) and (c_M, r_M) = (5, 12-8) = (5,4).
Intuitively, this outcome makes sense: Martin values cookies relatively more, and thus, his final allocation puts relatively more weight on this good. Because the average valuation in the economy is higher for cookies and Anna initially owns all of this resource, she holds more “value” in equilibrium as well.
The utility levels are

    \[ u_A(c_A,r_A) = \sqrt{5\cdot 8} = 2\sqrt{10} \hspace{0.5cm}\text{and}\hspace{0.5cm} u_M(c_M,r_M) = (5^2 \cdot 4)^{\frac{1}{3}} = 100^{\frac{1}{3}} \]

and aggregate welfare is

    \[ U = 2\sqrt{10} + 100^{\frac{1}{3}} \approx 6.32 + 4.64 = 10.96 \]

This level is, of course, lower than the one of the previous exercise, as there, the task was precisely to find the allocation that maximizes overall welfare, which was different from the one resulting from trade. Note, however, that the level difference is not that large.

Comment 1: This result puts some emphasis on the fact that aggregate welfare maximization oftentimes overlooks the dimension of fairness, i.e. inequality in the distribution of goods and resources; in the exchange economy scenario, the welfare difference is not large, but the distribution of resources is much less skewed towards Anna. This should remind you to treat arguments concluding from maximum aggregate welfare on maximum desirability with a grain of caution! Nonetheless, even in the trading economy, there is inequality driven by the initial allocation of resources.

Comment 2: On a less serious note, this should teach you that when invited by someone, it is in your own economic (self-)interest to bring something they like rather than something you like as this both increases your level of utility and the degree of interaction between both parties, which is also something people generally value. Also, when you know that you will be stranded on a deserted island for a while, bring cookies, not rice! 😉