Source: http://bdesgraupes.pagesperso-orange.fr/UPX/Master1/MNM1_exos_doc2.pdf
We consider a two products economy: a consumption good and work. The index 1 designs the consumption good, with a price $p_1 > 0$, while the index 2 denotes the work, with a salary $p_2 >0$.
The preferences of an economic agent, with workforce the lone ressource, can be represented with a utility function $$ U(x_1, x_2) = 2 \ln x_1 + \ln (3 - x_2). $$ It is assumed that there is a minimum consumption level $x_1 \geq 1$ while the work cannot exceed 3. We want to determine the demand function of the consumption good and the job supply function. Formulate the maximization program, give a geometric representation of the problem and solve it by means of Karush-Kuhn-Tucker's conditions. The solution estelle unique? Why?
We have to maximize the utility $U(x_1, x_2) = 2 \ln x_1 + \ln (3 - x_2)$ under the constraints $x_1 \geq 1$ and $x_2 \leq 3$. Moreover, it is not possible to spend more than what is earned: $p_1x_1 \leq p_2x_2$. Putting everything together, we obtain the program
We can reformulate the problem as \begin{align*} \min_x\ & -2 \ln x_1 - \ln (3 - x_2) \\ \mbox{s.t. } & -x_1+1 \leq 0 \\ & x_2 - 3 \leq 0 \\ & p_1x_1 - p_2x_2 \leq 0 \\ & -x_1 \leq 0, -x_2 \leq 0. \end{align*} Therefore, the Lagrangian is $$ L(x,\lambda) = -2 \ln x_1 - \ln (3 - x_2) + \lambda_1 (1-x_1) + \lambda_2 (x_2-3) + \lambda_3 (p_1x_1 - p_2x_2) - \lambda_4 x_1 - \lambda_5 x_2. $$
The KKT conditions can then be written as \begin{align*} -\frac{2}{x_1}-\lambda_1+p_1\lambda_3-\lambda_4 &= 0 \\ \frac{1}{3-x_2}+\lambda_2-p_2\lambda_3-\lambda_5 &= 0 \\ -x_1+1 &\leq 0 \\ x_2 - 3 & \leq 0 \\ p_1x_1 - p_2x_2 & \leq 0 \\ -x_1 &\leq 0 \\ -x_2 & \leq 0 \\ \lambda_1(-x_1+1) & = 0 \\ \lambda_2(x_2 - 3) & = 0 \\ \lambda_3(p_1x_1 - p_2x_2) & = 0 \\ \lambda_4 x_1 & = 0 \\ \lambda_5 x_2 & = 0 \\ \lambda_i & \geq 0,\ i = 1,\ldots,5 \end{align*}
We cannot have $x_1 = 0$, since it would violate the constraint $-x_1 + 1 \leq 0$, and therefore $\lambda_4 = 0$. Moreover, the constraint $x_1 \geq 0$ is implied by the constraint $x_1 \geq 1$. We can therefore simplify the KKT system as \begin{align*} -\frac{2}{x_1}-\lambda_1+p_1\lambda_3 &= 0 \\ \frac{1}{3-x_2}+\lambda_2-p_2\lambda_3-\lambda_5 &= 0 \\ -x_1+1 &\leq 0 \\ x_2 - 3 & \leq 0 \\ p_1x_1 - p_2x_2 & \leq 0 \\ -x_2 & \leq 0 \\ \lambda_1(-x_1+1) & = 0 \\ \lambda_2(x_2 - 3) & = 0 \\ \lambda_3(p_1x_1 - p_2x_2) & = 0 \\ \lambda_5 x_2 & = 0 \\ \lambda_i & \geq 0,\ i = 1,\ldots,5, \lambda_4 = 0. \end{align*}
We can also exclude the case $x_2 = 0$, as otherwise, the constraint $p_1 x_1 - p_2 x_2$ contradicting $x_1 \geq 1$. Consequently, $\lambda_5 = 0$, and the system can furter be simplified as \begin{align*} -\frac{2}{x_1}-\lambda_1+p_1\lambda_3 &= 0 \\ \frac{1}{3-x_2}+\lambda_2-p_2\lambda_3 &= 0 \\ -x_1+1 &\leq 0 \\ x_2 - 3 & \leq 0 \\ p_1x_1 - p_2x_2 & \leq 0 \\ -x_2 & \leq 0 \\ \lambda_1(-x_1+1) & = 0 \\ \lambda_2(x_2 - 3) & = 0 \\ \lambda_3(p_1x_1 - p_2x_2) & = 0 \\ \lambda_i & \geq 0,\ i = 1,2,3. \end{align*}
Observe also that $x_2 \ne 3$, as otherwise the derivative of the Lagrangian with respect to $x_2$ would be not defined. As a consequence, $x_2 < 3$, $\lambda_2 = 0$ and $$ \frac{1}{3-x_2} = p_2\lambda_3. $$ This implies $\lambda_3 \ne 0$, and $p_1x_1 = p_2x_2$.
Assume $x_1 = 1$. Then $$ x_2 = \frac{p_1}{p_2}. $$ If $\frac{p_1}{p_2} \geq 3$, the solution violates the constraint $x_2 < 3$, and we have have to reject it. Otherwise, the conditions $$ x_2 \geq 0,\ p_1x_1 - p_2x_2 \geq 0 $$ are trivially satisfied, and from the second equality, we have $$ \frac{1}{3-p_1/p_2} = p_2\lambda_3, $$ or, equivalently, $$ \frac{1}{3p_2-p_1} = \lambda_3. $$ As $\lambda_3 \geq 0$, this equality can hold only if $3p_2-p_1 > 0$, or $p_1 < 3p_2$. The first equality gives $$ -2 - \lambda_1+p_1 \frac{1}{3p_2-p_1} = 0 $$ or $$ \lambda_1 = \frac{-2(3p_2-p_1) + p_1}{3p_2-p_1} $$ As we must have $\lambda_1 \geq 0$, this holds only if $$ -6p_2 + 3p_1 \geq 0 $$ or $$p_1 \geq 2p_2.$$
Assume now $x_1 > 1$. Then $\lambda_1 = 0$ and $$ \lambda_3 = \frac{2}{p_1x_1}. $$ This in turn implies $$ \frac{1}{3-x_2}-\frac{2p_2}{p_1x_1} = 0, $$ or $$ p_1x_1 - 2p_2(3-x_2) = p_1x_1 +2p_2x_2 -6p_2 = p_1x_1 - p_2x_2 +3p_2x_2 -6p_2 = 0. $$ Therefore, $x_2 = 2$. This leads to $$ x_1 = 2\frac{p_2}{p_1}, \ \lambda_3 = \frac{1}{p_2}. $$ All the conditions are then satisfied at the condition $2\frac{p_2}{p_1} > 1$, or $p_1 < 2p_2$.
In summary, we have to consider three cases
Consider the problem \begin{align*} \min\ & f(x,y) = x^2+2y^2 \\ \mbox{t.q. } & x+y-b = 0 \end{align*}
The Lagrangian is $$ L(\lambda,x,y) = x^2 + 2y^2 + \lambda(x+y-b) $$
The Lagrangian is convex in $(x,y)$ and reach a minimum when $\nabla_{x,y} L(\lambda, x, y) = 0$. Indeed, $$ \nabla_{x^2,y^2}^2 L(\lambda, x, y) = \begin{pmatrix} 2 & 0 \\ 0 & 4 \end{pmatrix} $$ which is positive definite (striclty diagonaly dominant).
Therefore, $\nabla_{x,y} L(\lambda, x, y) = 0$ implies $x = 2y$, and from the constraint, $$ 2y + y - b = 0 $$ or $$ y = \frac{b}{3} $$ and $$ x = \frac{2b}{3} $$
Consider the optimization problem \begin{align*} \min_{x,y} \ & y \\ \mbox{s.t. } & (x-1)^2 + y^2 = 1 \\ & (x+1)^2 + y^2 = 1 \end{align*}
If we substract the second constraint to the first one, we obtain $$ (x-1)^2 - (x+1)^2 = 0 $$ or, equivantly $$ x^2-2x+1 - x^2-2x-1 = -4x = 0 $$ Therefore, $x = 0$ and consecutively, $y = 0$. The feasible set is therefore the singleton $\{ (0,0) \}$
The Jacobian matrix of the constraints is $$ J(x,y) = \begin{pmatrix} 2(x-1) & 2y \\ 2(x+1) & 2y \\ \end{pmatrix} $$ Therefore, $$ J(0,0) = \begin{pmatrix} -2 & 0 \\ 2 & 0 \\ \end{pmatrix} $$ The gradients of the active constraints are therefore linearly dependent. In other terms, the LICQ does not hold.
using LinearAlgebra
J = [ -2 0 ; 2 0]
rank(J)
The Lagrangian is $$ L(x, y, \lambda) = y + \lambda_1 ((x-1)^2 + y^2 - 1) + \lambda_2 ((x + 1)^2 + y^2 - 1) $$ and the KKT conditions are \begin{align*} 2\lambda_1 (x-1) + 2\lambda_2 (x+1) &= 0 \\ 1 + 2\lambda_1 y + 2\lambda_2 y &= 0 \\ (x-1)^2 + y^2 &= 1 \\ (x+1)^2 + y^2 &= 1 \end{align*} Since only (0,0) is feasible, the two first equalities become \begin{align*} -2\lambda_1 + 2\lambda_2 &= 0 \\ 1 &= 0 \end{align*} which obviously is not true.
We can show the duality properties by considering the problem \begin{align*} q(\lambda) &= \inf_{(x,y)} \{y + \lambda_1 ((x-1)^2 + y^2 - 1) + \lambda_2 ((x + 1)^2 + y^2 - 1) \} \\ &= \inf_{(x,y)} \{y + \lambda_1 ( x^2 - 2x + y^2 ) + \lambda_2 ( x^2 + 2x + y^2 ) \} \end{align*} with $\lambda = (\lambda_1, \lambda_2)$.
If $\lambda = 0$, $q(0) = -\infty$.
If $\lambda_1 = -\lambda_2$. Then \begin{align*} q(\lambda) &= \inf_{(x,y)} \{y + \lambda_1 ((x-1)^2 + y^2 - 1) - \lambda_1 ((x + 1)^2 + y^2 - 1) \} \\ &= \inf_{(x,y)} \{y + \lambda_1 (x^2-2x+1) - \lambda_1 (x^2 +2x +1) \} \\ &= \inf_{(x,y)} \{y - 4\lambda_1 x \} \end{align*} Therefore $q(\lambda) = -\infty$.
Assume now that $\lambda_1 + \lambda_2 \ne 0$. If $L(x,y,\lambda)$ is strongly convex with respect to $(x,y)$, we can compute the value of $q(\lambda)$ by setting $\nabla (x,y) L(x,y,\lambda) = 0$.
We have $$ \nabla (x,y) L(x,y,\lambda) = \begin{pmatrix} 2\lambda_1 (x-1) + 2\lambda_2 (x+1) \\ 1 + 2\lambda_1 y + 2\lambda_2 y \end{pmatrix} $$ and $$ \nabla^2 (x^2,y^2) L(x,y,\lambda) = \begin{pmatrix} 2\lambda_1 + 2\lambda_2 & 0 \\ 0 & 2\lambda_1 + 2\lambda_2 \end{pmatrix} $$ $Det\left(\nabla^2 (x^2,y^2) L(x,y,\lambda)\right| = 4(\lambda_1+\lambda_2)^2 > 0$.
If $\lambda_1+\lambda_2 < 0$, $L$ is strongly concave and $q(\lambda) = -\infty$.
If $\lambda_1+\lambda_2 > 0$, $L$ is strongly convex and $q(\lambda)$ achieves its minimum at the zero of the gradient.
In summary, if $\lambda_1 + \lambda_2 \leq 0$, $q(\lambda) = -\infty$. Otherwise $q(\lambda)$ is finite.
Assume $\lambda_1 + \lambda_2 > 0$. $\nabla (x,y) L(x,y,\lambda) = 0$ if and only if $$ \begin{cases} x = \frac{\lambda_1 - \lambda_2}{\lambda_1 + \lambda_2} \\ y = \frac{-1}{2\lambda_1 + 2\lambda_2} \end{cases} $$ Substituing in $q(\lambda)$, we obtain \begin{align*} q(\lambda) &= -\frac{1}{2(\lambda_1 + \lambda_2)} + \lambda_1 \left( \left( \frac{\lambda_1 - \lambda_2}{\lambda_1 + \lambda_2}-1 \right)^2 + \frac{1}{4(\lambda_1 + \lambda_2)^2} - 1 \right) + \lambda_2 \left( \left(\frac{\lambda_1 - \lambda_2}{\lambda_1 + \lambda_2} + 1\right)^2 + \frac{1}{4(\lambda_1 + \lambda_2)^2} - 1 \right) \\ &= -\frac{1}{2(\lambda_1 + \lambda_2)} + (\lambda_1 + \lambda_2) \left( \frac{1}{4(\lambda_1 + \lambda_2)^2} - 1 \right) + 4\frac{\lambda_1\lambda_2^2}{(\lambda_1 + \lambda_2)^2} + 4\frac{\lambda_1^2\lambda_2}{(\lambda_1 + \lambda_2)^2} \\ &= -\frac{1}{2(\lambda_1 + \lambda_2)} + \frac{1}{4(\lambda_1 + \lambda_2)} - (\lambda_1 + \lambda_2) + 4\lambda_1\lambda_2 \frac{\lambda_1+\lambda_2}{(\lambda_1 + \lambda_2)^2} \\ &= -\frac{1}{4(\lambda_1 + \lambda_2)} + \frac{-(\lambda_1 + \lambda_2)^2+4\lambda_1\lambda_2}{\lambda_1 + \lambda_2} \\ &= -\frac{1}{4(\lambda_1 + \lambda_2)} + \frac{-\lambda_1^2 - \lambda_2^2+2\lambda_1\lambda_2}{\lambda_1 + \lambda_2} \\ &= -\frac{1}{4(\lambda_1 + \lambda_2)}-\frac{(\lambda_1 - \lambda_2)^2}{\lambda_1 + \lambda_2} \\ &= \frac{-1-4(\lambda_1 - \lambda_2)^2}{4(\lambda_1 + \lambda_2)} \end{align*}
Therefore $q(\lambda) < 0$, but $\sup_{\lambda} q(\lambda) = 0$ as when $\lambda_1 = \lambda_2 \rightarrow +\infty$, $q(\lambda) \rightarrow 0$. The strong duality does hold, but asymptotically.
Consider the variant \begin{align*} \min_{x,y} \ & y \\ \mbox{s.t. } & (x-1)^2 + y^2 \leq 1 \\ & (x+1)^2 + y^2 \leq 1 \end{align*}
Since $y^2 \geq 0$, we deduce the a necessary feasibility condition is $$ \begin{cases} (x-1)^2 \leq 1 \\ (x+1)^2 \leq 1 \end{cases} $$
But if $x \ne 0$, $x-1$ or $x+1$ is strictly greater than 1, so one of the conditions is violated. Therefore we must have $x = 0$ and $y = 0$.
Thus, the set $\{ (x,y) \,|\, (x-1)^2 + y^2 < 1,\ (x+1)^2 + y^2 < 1 \}$ is empty, and the Slater CQ is not satisfied.
It is possible to show that the strong duality again asymptotically holds.
First note that the Lagrangian expression is the same, but we now must have $\lambda_1 > 0$, $\lambda_2 > 0$, and therefore $q(\lambda) < 0$. But if we set $\lambda_1 = \lambda_2$ and take the limit as $\lambda_1 \rightarrow +\infty$, we have $$ \lim_{\lambda_1 \rightarrow +\infty} q(\lambda_1,\lambda_1) = 0. $$ In other words, we cannot find a finite dual solution, but the strong duality still holds.
In both cases, we cannot find a finite dual solution by solving the KKT conditions.
Consider the problem \begin{align*} \min\ & x+y \\ \mbox{t.q. } & y \geq 0 \\ & y \leq x^3 \end{align*} The second constraint implies $x \geq 0$, and therefore, the solution is trivially $(0,0)$.
The dual Lagrangian function is $$ q(\lambda) = \inf_{x,y} x + y - \lambda_1 y + \lambda_2 (y-x^3) = \inf_{x,y} x(1 - x^2 \lambda_2) + y (1+\lambda_2 - \lambda_1) $$
Then $$ \nabla_{(x,y)} L(x,y, \lambda) = \begin{pmatrix} 1-3x^2\lambda_2 \\ 1-\lambda_1+\lambda_2 \end{pmatrix} $$
If $1-\lambda_1+\lambda_2 \ne 0$, there is no solution to $\nabla_{(x,y)} L(x,y, \lambda) = 0$, and it is easy to see that $q(\lambda) = -\infty$.
If $1-\lambda_1+\lambda_2 = 0$, $$ L(x,y, \lambda) = x(1-x^2\lambda) $$ and again $q(\lambda) = -\infty$.
Therefore there is an infinite duality gap.
The LICQ does not hold as, at $(0,0)$, both constraints are active and the Jacobian matrix of the constraints is $$ J(x,y) = \begin{pmatrix} 0 & -1 \\ -3x^2 & 1 \\ \end{pmatrix} $$ Therefore, $$ J(0,0) = \begin{pmatrix} 0 & -1 \\ 0 & 1 \\ \end{pmatrix} $$
The KKT system is \begin{align*} 1 - 3x^2\lambda_2 &= 0 \\ 1-\lambda_1+\lambda_2 &= 0 \\ -y &\leq 0 \\ y-x^3 &\leq 0 \\ \lambda_1(-y) &= 0 \\ \lambda_2 (y-x^3) &= 0 \\ \lambda_1, \lambda_2 &\geq 0 \end{align*}
The first equality implies $\lambda_2 \ne 0$ and therefore $y = x^3$. The first equality also implies $x \ne 0$, thus $y \ne 0$ and $\lambda_1 = 0$. Therefore, from the second equality, $\lambda_2 = -1$, in contradiction with $\lambda_2 \geq 0$. Therefore, the system has no solution.
Consider the convex problem \begin{align*} \min_{x,y}\ & e^{-x} \\ \mbox{t.q. } & x^2/y \leq 0 \\ & x, y \geq 0. \end{align*}
The constraint $$ \frac{x^2}{y} \leq 0 $$ is satisfied for $x = 0$ et $y > 0$ only.
The feasible set is therefore $\{ (x,y) \,|\, x = 0,\ y > 0\}$, which is convex.
Similarly, the objective function is convex, and thus, we are facing a convex problem.
However, since no point such that $x > 0$ is feasible, the Slater condition is not satisfied for the constraints given in the given form.
As $x = 0$ for any feasible point, the objective function is equal to $1$ whatever the feasibke point considered, and therefore any feasible solution is also optimal, with the value 1 being optimal.
The Lagrangian is $$ L(x,y,\lambda) = e^{-x} + \lambda_1 x^2/y - \lambda_2 x - \lambda_3 y $$ and the dual problem is \begin{align*} \max_{\lambda}\ & q(\lambda) = \inf_{x, y} L(x,y,\lambda) \\ \mbox{t.q. } & \lambda \geq 0. \end{align*}
In order to evaluate $q(\lambda)$, search $(x,y)$ tel que $$ \nabla_{x,y} L(x,y,\lambda) = \begin{pmatrix} -e^{-x} + 2\lambda_1 x/y - \lambda_2 \\ -\lambda_1 x^2/y^2 - \lambda_3 \end{pmatrix} = 0 $$
If $\lambda_3 \ne 0$, $L(0,y,\lambda) = 1-\lambda_3 y$ and $q(\lambda) = -\infty$, by letting $y$ going to $+\infty$. Observe also that for $x = 0$, the second gradient component of the Lagrangien is equal to $-\lambda_3$ and therefore cannot be equal to 0.
Consider now the case $\lambda_3 = 0$. Note that now, the second gradient component is equal to 0 for any $x = 0$.
If $\lambda_1 \ne 0$, $\lambda_1 > 0$, and we must have $x = 0$ and $\lambda_2 = 1$ in order to find a root of the Lagrangian gradient. If $\lambda_2 \ne 1$, then $q(\lambda)$ has no finite extremum as then, the first component of $\nabla_{x,y} L(x,y,\lambda)$ becomes, for $x = 0$, $-1 -\lambda_2$. By taking $y < 0$ and letting $x$ go to $+\infty$, we get $q(\lambda) = -\infty$. The same observation holds for $\lambda_2 = 1$, and thus the gradient root does not correspond to a global minimizer.
If $\lambda_1 = 0$, $L(x,y,\lambda) = e^{-x} - \lambda_2 x$. As $x$ grows to $+\infty$, we observe that $q(\lambda) = 0$ if $\lambda_2 = 0$, $-\infty$ otherwise.
The maximum of $q(\lambda)$ is therefore equal to 0, and is obtained when $\lambda = 0$.
Thus, there is a duality gap equal to 1.
We sometimes keep the non-negativity constraints when building the Lagrangian. For the example, we then have $$ L(x,y,\lambda) = e^{-x} + \lambda x^2/y $$ and $$ q(\lambda) = \inf_{x,y \geq 0} L(x,y,\lambda) $$
In this case, if $\lambda \geq 0$, $L(x,y,\lambda) > 0$ and $q(\lambda) = 0$, for instance by taking $x = t$ and $y = t^3$, as then $$ L(x,y,\lambda) = -e^{-t} + \lambda t^2/t^3 = -e^{-t} + \lambda 1/t $$ and we can let $t$ go to $+\infty$.
The duality gap is therefore again equal to 1.