ECON526: Problem Set 0 (Solutions)

SOLUTIONS

Instructions

• This problem set covers linear algebra and optimization material from the MA Math Camp.
• Submit as PDF on Canvas

Question 1

Minimize the function \(x^2 + y^2 +z^2\) subject to

\[ \begin{aligned} 3x + y + z = 7 \\ x + y + z = 1 \end{aligned} \]

TipSOLUTIONS

The Lagrangian is

\[ \Lambda (x,y,z,\lambda,\mu) = x^2 + y^2 + z^2 + \lambda(7-3x-y-z ) + \mu(1-x-y-z) \]

The first-order conditions are

\[ \begin{aligned} x: 2x - 3\lambda - \mu = 0 \\ y: 2y - \lambda - \mu = 0 \\ z: 2z - \lambda - \mu = 0 \\ \lambda: 7-3x-y-z = 0 \\ \mu: 1-x-y-z = 0 \end{aligned} \]

Solving this system of equations gives the following solution:

\[ \begin{aligned} x = 3 \\ y = -1 \\ z = -1 \\ \mu = - 6 \\ \lambda = 4 \\ \end{aligned} \]

Question 2

Question 2.1

For the following optimization problem:

1. Show the Lagrangian
2. Provide all of the first-order conditions for the optimization problem
3. Solve the optimization problem for the \(x\) value and any Lagrange multipliers, being formal in the use of equations and inequalities where possible.

\[ \begin{aligned} \max_x &\{2 x\}\\ \text{s.t. } & x^2 \leq 5 \end{aligned} \]

TipSOLUTIONS

Take the Lagrangian

\[ \mathcal{L}(x,\lambda) = 2x + \lambda\,(5 - x^2),\quad \lambda \ge 0. \]

The KKT conditions are

\[ \begin{aligned} &\text{FOC:} && \partial_x \mathcal{L} = 2 - 2\lambda x = 0 \\ &\text{Constraint:} && x^2 \le 5 \\ &\text{LM positivity:} && \lambda \ge 0 \\ &\text{complementary slackness:} && \lambda\,(5 - x^2) = 0. \end{aligned} \]

1. From the FOC above, \(2 - 2\lambda x = 0\). If \(\lambda = 0\), then \(2=0\) (contradiction), so by dual feasibility \(\lambda > 0\).
2. With \(\lambda>0\) and complementary slackness \(\lambda(5-x^2)=0\), the constraint binds: \(5-x^2=0 \Rightarrow x^2=5\).
3. Plug into the FOC: \(2 - 2\lambda x = 0 \Rightarrow \lambda = 1/x\).
4. Primal feasibility gives \(x \in \{\pm\sqrt{5}\}\). Dual feasibility (\(\lambda\ge 0\)) plus \(\lambda=1/x\) implies \(x>0\), hence \(x^*=\sqrt{5}\) and \(\lambda^* = 1/\sqrt{5}\).
5. Optimal value (objective \(2x\)): \(2x^* = 2\sqrt{5}\).

Question 2.2

For the following optimization problem:

1. Show the Lagrangian
2. Provide all of the first-order conditions for the optimization problem
3. Solve the optimization problem for the \(x\) value and any Lagrange multipliers, being formal in the use of equations and inequalities where possible.

\[ \begin{aligned} \max_x &\{2 x\}\\ \text{s.t. } & x^2 \geq 5 \end{aligned} \]

TipSOLUTIONS

Lagrangian and KKT conditions (write constraint as \(g(x)=x^2-5\ge 0\)):

\[ \mathcal{L}(x,\lambda)=2x+\lambda\,(x^2-5),\quad \lambda\ge 0. \]

KKT conditions

\[ \begin{aligned} &\text{FOC:} && \partial_x \mathcal{L}=2+2\lambda x=0 \\ &\text{Constraint:} && x^2 - 5\ge 0 \\ &\text{LM positivity:} && \lambda\ge 0 \\ &\text{Complementary slackness:} && \lambda\,(x^2-5)=0. \end{aligned} \]

Steps:

1. Assume constraint does not bind, i.e. \(\lambda = 0\)
   • Then the FOC gives that \(2 = 0\), a contradiction.
2. Then assume the constraint binds, and \(\lambda \neq 0\)
   • By slackness, this means \(x^2 = 5\), so \(x = \pm\sqrt{5}\)
   • At \(x = -\sqrt{5}\), the FOC gives \(2 - 2 \lambda \sqrt{5} = 0\), so \(\lambda = 1/\sqrt{5} > 0\): this is a KKT point, a constrained local maximum on the negative branch.
   • At \(x = \sqrt{5}\), the FOC gives \(\lambda = -1/\sqrt{5}\), which is negative—contradicting the LM positivity.

There is no global maximizer: feasible \(x \to +\infty\) makes \(2x\) unbounded above.

Question 3

Consider a household whose utility is defined over consumption of two goods, \(x\) and \(y\), and is given by the following function:

\[ u(x,y)=(a x^\eta + b y^\eta)^{\frac{1}{\eta}}, \]

where \(\eta\leq 1\) is a parameter governing the elasticity of substitution between goods \(x\) and \(y\), and \(0<a<1\) and \(0<b<1\).

Prices of the goods are determined in competitive markets and are given by \(p_x\) and \(p_y\). The household has a total income of \(m\). (i) Write down the budget constraint facing the household. (ii) Find the utility-maximizing demand for the two goods.

TipSOLUTIONS

The budget constraint is

\[ p_x x + p_y y = m \]

The Lagrangian is:

\[ \Lambda(x,y,\lambda) = (a x^\eta + b y^\eta)^{\frac{1}{\eta}} + \lambda[m - p_x x - p_y y] \]

The first-order necessary conditions are:

\[ \begin{aligned} \frac{\partial \Lambda}{\partial x} = (a x^\eta + b y^\eta)^{\frac{1}{\eta}-1} a x^{\eta-1} - \lambda p_x = 0 \\ \frac{\partial \Lambda}{\partial y} = (a x^\eta + b y^\eta)^{\frac{1}{\eta}-1} b y^{\eta-1} - \lambda p_y = 0 \\ \frac{\partial \Lambda}{\partial \lambda} = m - p_x x - p_y y = 0 \end{aligned} \]

Combining the 1st and 2nd conditions above gives \(\frac{a}{b} \left(\frac{x}{y}\right)^{\eta-1} = \frac{p_x}{p_y}\).

Substituting this into the budget constraint gives

\[ \begin{aligned} p_x y \left( \frac{p_x}{p_y} \frac{b}{a}\right)^{\frac{1}{\eta-1}} + p_y y = m \\ p_y y \left( \frac{p_x}{p_y} \right)^{\frac{\eta}{\eta-1}} \left(\frac{b}{a} \right)^{\frac{1}{\eta-1}} + p_y y = m \\ p_y y = \frac{m}{\left( \frac{p_x}{p_y} \right)^{\frac{\eta}{\eta-1}} \left(\frac{b}{a} \right)^{\frac{1}{\eta-1}} + 1} \end{aligned} \]

We can solve for \(x\) from the budget constraint as a residual:

\[ x = \frac{m - p_y y}{p_x} \]

with \(y\) from the expression above.

The interior expression above applies for \(\eta < 1\), \(\eta \neq 0\) (with positive goods, prices, and income). If \(\eta = 1\), utility is \(a x + b y\): spend all income on \(x\) when \(a/p_x > b/p_y\), on \(y\) when \(a/p_x < b/p_y\), and any budget bundle is optimal when the ratios tie. The displayed utility is undefined at \(\eta = 0\) unless a limiting convention is specified.

Question 4

Being formal and explicit about the rules of matrix algebra (e.g., when operations are commutative, distributive, and when invertibility is required), solve for \(x \in {\mathbb{R}}^N\). Constants: vectors \(b,c,d \in {\mathbb{R}}^N\), matrices \(A,B,Q,R \in {\mathbb{R}}^{N\times N}\), and scalar \(m \in {\mathbb{R}}\).

1. \((I - A)\,x = b + c\)
2. \(A x + (x^\top B)^\top = d\)

TipSOLUTIONS

Solution part 1

• \((I - A)x = b + c\), starting point
• Assuming \(I - A\) is invertible, left-multiply by \((I - A)^{-1}\)
• \((I - A)^{-1}(I - A)x = (I - A)^{-1}(b + c)\), using left multiplication
• \(x = (I - A)^{-1}(b + c)\), using \((I - A)^{-1}(I - A) = I\) and \(Ix = x\)

Solution part 2

• \(A x + (x^{\top} B)^{\top} = d\), starting point
• \((x^{\top} B)^{\top} = B^{\top} (x^{\top})^{\top} = B^{\top} x\), using \((XY)^{\top} = Y^{\top} X^{\top}\) and \((x^{\top})^{\top} = x\)
• \((A + B^{\top}) x = d\), using distributivity: \((A + B^{\top})x = A x + B^{\top} x\)
• If \((A + B^{\top})\) is invertible, left-multiply by \((A + B^{\top})^{-1}\)
• \(x = (A + B^{\top})^{-1} d\)

Question 5

1. Find a unit vector \(x \in {\mathbb{R}}^2\) such that \(x \cdot \begin{bmatrix}3 & 4\end{bmatrix} = 0\). Hint: perpendicular vectors to any \(\begin{bmatrix}a & b\end{bmatrix}\) is \(\begin{bmatrix}-b & a\end{bmatrix}\) or \(\begin{bmatrix} b & -a \end{bmatrix}\) and a unit vector is one where \(||x||_2 = 1\).
2. Given any nonzero vectors \(u,v \in {\mathbb{R}}^N\), explain how to test using the norm and inner product whether they are (i) orthogonal and (ii) collinear, and if collinear, whether they point in the same or opposite direction.

TipSOLUTIONS

Solution part 1

• Condition: \(x \cdot \begin{bmatrix}3 & 4\end{bmatrix} = 0\).
• A perpendicular vector to \(\begin{bmatrix}3 & 4\end{bmatrix}\) is \(\begin{bmatrix}-4 & 3\end{bmatrix}\), using \((a,b) \perp (-b,a)\).
• Normalize to unit length: \(\|(-4,3)\|_2 = \sqrt{(-4)^2 + 3^2} = 5\).
• One unit solution is \(x = \tfrac{1}{5}\begin{bmatrix}-4 & 3\end{bmatrix}\) (also \(-x\) works).

Solution part 2

• Orthogonality: \(u \perp v\) if and only if \(u^\top v = 0\).
• Collinearity: For nonzero \(u,v\), compute \(\cos\theta = \dfrac{u^\top v}{\|u\|_2\,\|v\|_2}\).
  • If \(|\cos\theta| = 1\) (equivalently, \(\dfrac{u}{\|u\|_2} \cdot \dfrac{v}{\|v\|_2} = \pm 1\)), then \(u\) and \(v\) are collinear.
  • Same direction if \(\cos\theta = 1\); opposite direction if \(\cos\theta = -1\).

Question 6

1. What is the span of the vectors \(\begin{bmatrix}1 & 2\end{bmatrix}\) and \(\begin{bmatrix}2 & 4\end{bmatrix}\) in \({\mathbb{R}}^2\)?
2. For a set of vectors \(u^1,\ldots,u^k \in {\mathbb{R}}^n\), what are the possible dimensions of \(\operatorname{span}\{u^1,\ldots,u^k\}\)? State the minimum and maximum values and when they occur.

TipSOLUTIONS

Solution part 1

• Note \(\begin{bmatrix}2 & 4\end{bmatrix} = 2\,\begin{bmatrix}1 & 2\end{bmatrix}\), so the vectors are linearly dependent.
• The span is all scalar multiples of \(\begin{bmatrix}1 & 2\end{bmatrix}\), i.e. \[ \operatorname{span}\left\{\begin{bmatrix}1 & 2\end{bmatrix},\begin{bmatrix}2 & 4\end{bmatrix}\right\} = \left\{ t\,\begin{bmatrix}1 & 2\end{bmatrix} : t \in {\mathbb{R}}\right\}, \] which is a one-dimensional subspace (a line through the origin) in \({\mathbb{R}}^2\).
• Don’t punish people for saying the span is actually \({\mathbb{R}}^1\) if you think they understand what is going on. But use this sort of thing to distinguish between an A and A+. They just don’t have the language to talk about subspaces.
• Another full marks, full subtlety answer is to say that it is a line in \({\mathbb{R}}^2\).

Solution part 2

• Let \(U = \operatorname{span}\{u^1,\ldots,u^k\} \subseteq {\mathbb{R}}^n\).
• The dimension satisfies \(0 \le \dim U \le \min\{k,n\}\).
  • Minimum: \(\dim U = 0\) if and only if all \(u^i = 0\) (the zero subspace).
  • Otherwise \(\dim U \ge 1\) if at least one vector is nonzero.
  • Maximum: \(\dim U = \min\{k,n\}\), achieved when the set contains \(\min\{k,n\}\) linearly independent vectors (e.g., \(k \le n\) and the \(u^i\) are linearly independent; or \(k \ge n\) and the set spans \({\mathbb{R}}^n\)).
  • As before, be very flexible with the exact terminology and answers here if they seem like they know what is going on. If they say the span is \({\mathbb{R}}^k\) but seem to know what is going on instead of saying it is a subspace of \({\mathbb{R}}^n\) of dimension at most \(\min\{k,n\}\), that is fine of course.