Can $u(x) = \sqrt{x_1 x_2} + \sqrt{x_3 x_4}$ be solved by Kuhn–Tucker conditions?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

\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*}

Answer 4

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.