8
$\begingroup$

Consider

$\max_{x_1, x_2, x_3, x_4} u(x) = \sqrt{x_1 x_2} + \sqrt{x_3 x_4}$

s.t. $\; p_1x_1 + p_2x_2 + p_3x_3 + p_4x_4 \le w$

I know we can solve the max problem through separately considering case(i): $x_1, x_2 > 0$ and $x_3 = x_4 = 0$; and case (ii) $x_1 = x_2 = 0$ and $x_3, x_4 > 0$.

But is it possible to solve the whole optimization problem through the Kuhn–Tucker method?

We can write down the Lagrangian $L(x,\lambda)=\sqrt{x_1x_2}+\sqrt{x_3x_4}+\lambda(w-p_1x_1-p_2x_2-p_3x_3-p_4x_4)$

with the complementary slackness conditions:

$\frac{\partial L}{\partial x_1}=\frac{1}{2}\sqrt{\frac{x_2}{x_1}}-\lambda p_1 \le 0,\quad x_1 \ge 0, \quad \text{and}\quad x_1 \frac{\partial L}{\partial x_1}=0$.

$\frac{\partial L}{\partial x_2}=\frac{1}{2}\sqrt{\frac{x_1}{x_2}}-\lambda p_2 \le 0,\quad x_2 \ge 0, \quad \text{and}\quad x_2 \frac{\partial L}{\partial x_2}=0$.

$\frac{\partial L}{\partial x_3}=\frac{1}{2}\sqrt{\frac{x_4}{x_3}}-\lambda p_3 \le 0,\quad x_3 \ge 0, \quad \text{and}\quad x_3 \frac{\partial L}{\partial x_3}=0$.

$\frac{\partial L}{\partial x_4}=\frac{1}{2}\sqrt{\frac{x_3}{x_4}}-\lambda p_4 \le 0,\quad x_4 \ge 0, \quad \text{and}\quad x_4 \frac{\partial L}{\partial x_4}=0$.

However, when guessing say, $x_1 = 0$ and $x_2,x_3,x_4>0$, $\lim_{x_1 \to 0}\frac{\partial L}{\partial x_1} \to \infty$, which does not satisfy the complementary slackness $x_1 \frac{\partial L}{\partial x_1} = 0$.

I do not know whether we can use the Kuhn–Tucker method to solve this optimization problem? And if not, what are the reasons?

$\endgroup$
1
  • 2
    $\begingroup$ Here's a good trick for any microeconomic optimization problem: if the agent's preferences are locally non-satiated, then Walras' Law will hold. That is, $p x = w$. Also note that monotonic preferences are locally non-satiated, and as your objective function is weakly increasing in each of its arguments, you have weakly monotonic preferences. $\endgroup$
    – NBm424
    Oct 30, 2018 at 1:59

4 Answers 4

4
$\begingroup$

No, you can't. The Karush-Kuhn-Tucker theorem is for functions defined on $\mathbb{R}^n$ or at least an open subset thereof and requires the function to be maximized to be differentiable on the domain. That the solution has to lie in the nonnegative orthant is not something that can be represented by inequality constraints here, since the utility function is not defined on a larger open domain on which it is differentiable. Indeed, the function $(x_1,x_2)\mapsto \sqrt{x_1x_2}$ is not differentiable at points where $x_1=0$ or $x_2=0$. To see this, note that if the function is differentiable at, for example, the point $(x_1,x_2)=(0,1)$, then there would exists a vector $v=(v_1,v_2)$ such that $$\lim_{h\to 0}\frac{\|\sqrt{(x_1+h_1)(x_2+h_2)}-\sqrt{x_1x_2}-v_1x_1-v_2x_2 \|}{\|h\|}=0$$ $$\lim_{h\to 0}\frac{\|\sqrt{h_1+h_1h_2}-v_2 \|}{\|h\|}=0.$$ But, for example, taking for $h=(0,1/n)$ $$\lim_{n\to \infty}\frac{\|\sqrt{0+0\cdot 1/n}-v_2 \|}{1/n}=\lim_{n\to\infty }n\|-v_2\|,$$ which is only $0$ if $v_2=0$. So assume $v_2=0$ and take $h=(1/n,1/n)$ instead, you get $$\liminf_{n\to \infty}\frac{\|\sqrt{1/n+1/n^2}\|}{\sqrt 2~ 1/n}\geq 1/\sqrt 2.$$ No derivative exists at $(0,1)$.

Misuse of the Karush-Kuhn-Tucker theorem is very prevalent, even in otherwise very rigorous textbooks. The appendix of the following paper lists several examples of textbooks that apply the KKT-theorem to problems where it can't:

Erik J. Balder, "Exact and useful optimization methods for microeconomics" in: New Insights into the Theory of Giffen Goods (W. Heijman and P. Mouche, eds.), Lecture Notes in Economics and Mathematical Systems 655, Springer, 2012, pp. 21-38.

$\endgroup$
6
  • $\begingroup$ Thanks Michael. Regarding your comment about the misuse, let me clarify that the conditions in the theorem are sufficient conditions. That means it is possible that in conditions other than the ones that are mentioned in the theorem, the KKT conditions can still be used. For example, in situations where solutions to the optimization problems does not lie on the boundaries (where the function is not differentiable) we can use KKT conditions to find the solutions even when the function is not differentiable at these points as long as it is continuous at those points. $\endgroup$
    – Amit
    May 28, 2022 at 5:04
  • $\begingroup$ Let me know if you want me to prove this. I can provide you the proof. But yes, your point about this particular problem is well taken (since the solution lies on the boundary). And I have presented an alternative way to do this using KKT method in my another answer. $\endgroup$
    – Amit
    May 28, 2022 at 5:11
  • $\begingroup$ If we know that the solution does not lie on the boundary, we can of course use $\mathbb{R}_{++}$ as the domain. This is the case of "neoclassical preferences" as definedAliprantis Brown, Burkinshaw, which is also mentioned in Balder's paper. $\endgroup$ May 28, 2022 at 7:44
  • $\begingroup$ That’s right. That’s the proof 😊 $\endgroup$
    – Amit
    May 28, 2022 at 7:45
  • $\begingroup$ But on the open convex set $\{(x_1,x_2,x_3,x_4)\in\mathbb{R}^4| x_i > 0\}$ the function IS differentiable. $\endgroup$
    – Davius
    Jun 6, 2022 at 22:32
3
$\begingroup$

Why do you want to guess that some $x$ is zero? What is the problem of having all four goods strictly positive at the solution?

In fact, due to the presence of the square root in the first order conditions, the solution looks straightforward, since the inequality cannot hold (and assuming exhaustion of the budget).


ADDENDUM
Given the f.o.c's provided by the OP, all $x$'s have to be strictly positive at the solution, since otherwise we have division by zero and/or the undetermined form $0/0$.

This in turn implies that $\partial L/\partial x_i = 0$ at the solution, which now becomes easy to compute.

$\endgroup$
1
  • 2
    $\begingroup$ It's because the solutions are (i) if $p_1p_2 < p_3 p_4$, then $x_1 = \frac{M}{2p_1}$, $x_2 = \frac{M}{2p_2}$, $x_3 =x_4 =0$; (ii) if $p_1p_2 > p_3 p_4$, then $x_3 = \frac{M}{2p_3}$, $x_4 = \frac{M}{2p_4}$, $x_1 =x_2 =0$; and (iii) with an interior solution, when $p_1p_2 = p_3 p_4$. $\endgroup$
    – Yun
    Oct 30, 2018 at 5:39
3
$\begingroup$

\begin{eqnarray*}\max_{x_1,x_2, x_3, x_4} & \sqrt{x_1x_2} + \sqrt{x_3x_4} \\ \text{s.t.} & \ p_1x_1 + p_2x_2+p_3x_3 +p_4x_4 \leq w \\ \text{and } & \ x_1, x_2, x_3, x_4 \geq 0\end{eqnarray*}

One way to solve this problem is using Kuhn-Tucker method.

Here is another way to solve this problem:

Consider the following two-stage problem:

  • In stage 1, allocate $w_{12}\geq 0, w_{34}\geq 0$ out of the entire income $w$ (such that $w_{12} + w_{34}\leq w$) to spend on bundles $(x_1, x_2)$ and $(x_3, x_4)$ respectively, in the best possible way.
  • In stage 2, spend the allocated amount in the best possible way.

Formally, this is how we can define the problem: \begin{eqnarray*}\max_{w_{12}\geq 0, \ w_{34} \geq 0, \ w_{12} +w_{34} \leq w} \left[\max_{x_1\geq 0, \ x_2 \geq 0, \ p_1x_1 + p_2x_2 \leq w_{12}}\sqrt{x_1x_2} + \max_{x_3\geq 0, \ x_4 \geq 0, \ p_3x_3 + p_4x_4 \leq w_{34}}\sqrt{x_3x_4} \right] \end{eqnarray*}

It can be easily shown that the solution set to this problem will be same as the solution set of the problem we want to solve. Let me know if you want to see the proof.

We can now solve this by backward induction:

Solution to the problems inside the parenthesis is:

\begin{eqnarray*} (x_1^i, x_2^i)(p_1, p_2, w_{12}) & = & \left(\frac{w_{12}}{2p_1},\frac{w_{12}}{2p_2} \right) \\ (x_3^i, x_4^i)(p_3, p_4, w_{34}) & = & \left(\frac{w_{34}}{2p_3},\frac{w_{34}}{2p_4} \right)\end{eqnarray*}

Using the solution above, we can re-write the problem as: \begin{eqnarray*}\max_{w_{12}, w_{34}} & \frac{w_{12}}{2\sqrt{p_1p_2}} + \frac{w_{34}}{2\sqrt{p_3p_4}} \\ \text{s.t.} & \ \ w_{12}\geq 0, \ w_{34} \geq 0, \ w_{12} +w_{34} \leq w \end{eqnarray*}

Now this is a standard perfect substitutes case, and we get

\begin{eqnarray*} (w_{12},w_{34})(p_1, p_2, p_3, p_4, w) \in \begin{cases} \left\{\left(w, 0\right)\right\} & \text{if } p_1p_2 < p_3p_4 \\ \left\{\left(0,w\right)\right\} & \text{if } p_1p_2 > p_3p_4 \\ \left\{\left(m,n\right)\in\mathbb{R}^2_+| m+n=w\right\} & \text{if } p_1p_2 = p_3p_4\end{cases} \end{eqnarray*}

Now we can substitute this back in $(x_1^i, x_2^i)$ and $(x_3^i, x_4^i)$ to get the demands: \begin{eqnarray*} (x_1^d,x_2^d, x_3^d, x_4^d)(p_1, p_2, p_3, p_4, w) \in \begin{cases} \left\{\left(\frac{w}{2p_1},\frac{w}{2p_2}, 0, 0\right)\right\} & \text{if } p_1p_2 < p_3p_4 \\ \left\{\left(0,0,\frac{w}{2p_3},\frac{w}{2p_4}\right)\right\} & \text{if } p_1p_2 > p_3p_4 \\ \left\{\left(\frac{m}{2p_1},\frac{m}{2p_2},\frac{n}{2p_3},\frac{n}{2p_4}\right)\in\mathbb{R}^4_+| m+n=w\right\} & \text{if } p_1p_2 = p_3p_4\end{cases} \end{eqnarray*}

$\endgroup$
3
$\begingroup$

As Michael pointed out that we cannot use Kuhn-Tucker conditions here because the objective function is not differentiable everywhere (at the boundary). Here is what we can do in light of the above:

Theorem. Let $u:\mathbb{R}^n_+\rightarrow\mathbb{R}$ be continuously differentiable on $\mathbb{R}^n_{++}$, increasing and continuous everywhere and suppose that $u$ is concave and prices $p_i>0 \text{ for each } i \in \{1, 2\ldots, n\}$and $w>0$ then $(x_1^*, x_2^*, \ldots, x_n^*)$ solves the problem \begin{eqnarray*} \max_{x_1, x_2, \ldots, x_n} & u(x_1, x_2,\ldots, x_n) \\ \text{s.t.} & \ \sum_{i=1}^{n} p_ix_i \leq w \\ \text{and } & x_i \geq \epsilon_i & \text{ for each } i \in \{1, 2\ldots, n\}\end{eqnarray*} for all $\epsilon_i> 0$ (and sufficiently small so that the constraint set is non-empty).

if and only if it satisfies the Kuhn-Tucker conditions.

Of course, the above is true by the Kuhn-Tucker Theorem.

Proposition: This is how we can use the Kuhn-Tucker conditions to solve the problem we are interested in i.e. when $\epsilon_i=0$:

Since $p_i>0 \text{ for each } i \in \{1, 2\ldots, n\}$, constraint set is compact and convex, and given that the utility function is concave and continuous, the solution set is non-empty, convex and compact. And the solution set to the Kuhn-Tucker conditions is same as the solution set of the optimization problem (by the above theorem). Since the solution set to the optimization problem (including the case where $\epsilon_i$s are possibly $0$) is a upper hemi-continuous correspondence in $\epsilon = (\epsilon_1, \epsilon_2, \ldots, \epsilon_n)$ (under our assumptions), it has a closed graph. So, we can just solve the problem above using the Kuhn-Tucker conditions for positive $\epsilon_i$s and then find the limit points of the graph of the solutions. Since graph is closed, set of points at $(\epsilon_1, \epsilon_2, \ldots, \epsilon_n)= 0$ in the closure of the graph will be the solution of the desired optimization problem and this is how we can now use the Kuhn-Tucker conditions to solve the problem. This approach may not give all the solutions to the desired optimization problem but will definitely give a non-empty subset of the solutions.*

*In the problem with $u= \sqrt{x_1x_2} +\sqrt{x_3x_4}$, it'll give all the solutions, and right now I cannot think of a case where this approach will not give all the solutions.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.