Consider the nonlinear program \begin{equation}
\underset{\mathbb{R}^2}{\text{min}} f(x_1 , x_2 ) = x_1^2 – x_1 x_2 + x_2^2 – x_1 – x_2 \end{equation} subject to the conditions:
\begin{equation}
\begin{split}
&x_1x_2>1\\
&x_1^2+x_2^2\le 2
\end{split} \end{equation}
Find the KKT points.
In order to find the KKT point one needs to solve the problem by methods of Lagrange multipliers.
Here we have the suggested approach:
Let $f(x_1,x_2)=x_2^2-x_1x_2+x_2^2-x_1-x_2$ and $g(x_1,x_2)=x_1x_2>1$, $h(x_1,x_2)=x_1^2+x_2^2\leq 2$
That gives
$$\mathcal{L}(x_1,x_2,\lambda,\mu)=x_2^2-x_1x_2+x_2^2-x_1-x_2-\lambda(x_1x_2-1)-\mu(x_1^2+x_2^2-2)$$
The system of equations equalling zero, for the gradients with respect to each variable, $x_1, x_2, \lambda, \mu$ is then
\begin{equation}
\begin{split}
&-x_2-1-\lambda x_2-2\mu x_1=0\\
&2x_2-x_1+2x_2-1-\lambda x_1-2\lambda x_2=0 \\
& -x_1x_2-1=0 \\
&-x_1^2-x_2^2-2=0
\end{split}
\end{equation}
But this system has no solutions. Did I do a mistake in forming the Lagrangian?
Thanks
Best Answer
Actually, in the context of the method of Lagrange multipliers with inequality constraints, the latter are usually turned into standard (equality) constraints with the help of "slack variables". Concretely, one has : $$ \left\{ \begin{array}{r} x_1^2 + x_2^2 \le 2 \\ x_1x_2 > 1 \end{array} \right. \quad\Longrightarrow\quad \left\{ \begin{align} x_1^2 + x_2^2 - 2 + s^2 &= 0 & (a)\\ x_1x_2 - 1 - t^2 &= 0 & (b) \end{align} \right. $$ where $s^2 \ge 0$ and $t^2 > 0$ are the said slack variables $-$ note that the squares are here to ensure their positiveness. Now, the Lagrangian is defined as
$$ L(x_1,x_2;\lambda,\mu;s,t) = f(x_1,x_2) - \lambda(x_1^2 + x_2^2 - 2 + s^2) - \mu(x_1x_2 - 1 - t^2) $$ and extremized as usual, i.e. $$ \left\{ \begin{align} \displaystyle \frac{\partial L}{\partial x_1} &= 2x_1 - x_2 - 1 - 2\lambda x_1 - \mu x_2 = 0 & (1) \\ \displaystyle \frac{\partial L}{\partial x_2} &= 2x_2 - x_1 - 1 - 2\lambda x_2 - \mu x_1 = 0 & (2) \end{align} \right., $$ together with the above equality contraints, as well as the following conditions : $$ \left\{ \begin{align} \displaystyle \frac{\partial L}{\partial s} &= -2\lambda s = 0 \\ \displaystyle \frac{\partial L}{\partial t} &= +2\mu t\, = 0 \end{align} \right. $$ The last two conditions impose to distinguish several cases, depending on whether the constraints are "active" or not; in other words, the slack variables are free in the case where the Lagrange multipliers are equal to zero (this is the inactive case) and active otherwise.
1st case : $\lambda = \mu = 0$. Then we have $x_1 = x_2 = 1$ from $(1)$ and $(2)$, which implies $s^2 = t^2 = 0$ by $(a)$ and $(b)$. Since $t$ must be strictly positive, we conclude that this first case is not feasible.
2nd case : $\lambda \neq 0$, $\mu = 0$. Then we have $x_1 = x_2 = \frac{1}{1-\lambda}$ from $(1)$ and $(2)$, as well as $\lambda = 1 \pm \frac{1}{\sqrt{1+t^2}}$ by $(b)$, recalling that $t^2$ is free due to $\mu = 0$, hence finally $s^2 = 2 - \frac{2}{(1-\lambda)^2} = -2t^2 < 0$. Yet, $s^2$ should be positive, that is why this case is also impossible.
3rd case : $\lambda = 0$, $\mu \neq 0$. Idem to the 2nd case by switching the roles of $\lambda/\mu$ and $s/t$ respectively.
4th case : $\lambda,\mu \neq 0$. Here, several sub-cases are to be considered depending on the exact values of $\lambda$ and $\mu$. However, I let you verify that they all fail to ensure positive slack variables and are thus non-feasible too.
As Föölücks concluded in his answer, there is no solution which optimizes this Lagrangian under the considered constraints. At the very least, you saw how to proceed. One more comment to add : in the case where several cases had been feasible, then you would have had to compute and compare the different values of the Lagrangian in order to determine the true optimum.