Recognize that the function is unbounded below

Suppose we have the following optimization problem:

$$\min_{x_1, x_2} x_1+x_2+x_1x_2$$ s.t. $$x_1^2+x_2^2 = 1$$

The assignment is to solve this with the concept of duality.

So when I write out the dual function

$$ \min_{x_1, x_2} x_1+x_2+x_1x_2+\lambda(x_1^2+x_2^2-1)$$, I can get the derivative wrt $x_1=x_2=x$ and then substitute to get the dual function as:

$$D(\lambda) = -1-3\lambda-\lambda^2$$

maximizing this over $\lambda$, I get $\lambda = -\frac{3}{2}$ as the solution to the dual problem.

But when I check this, it says that the dual function is unbounded below when $\lambda$ is less than $\frac{1}{2}$.

In my understanding, this means that the dual function is:

for $\lambda \ge\frac{1}{2}: D(\lambda) = -1-3\lambda-\lambda^2$

for $\lambda < \frac{1}{2}: D(\lambda) = -\infty $

But how can we recognize that the dual function is unbounded below when $\lambda$ is less than $\frac{1}{2}$ ?

Solution 1:

The lagrange function is $$L(x_1,x_2,\lambda)=x_1+x_2+x_1x_2+\lambda(x_1^2+x_2^2-1).$$ We minimize it by taking derivative w.r.t. $x_1$ and $x_2$.
$$\frac{\partial L}{\partial x_1}=1+x_2+2\lambda x_1=0$$ and $$\frac{\partial L}{\partial x_2}=1+x_1+2\lambda x_2=0$$
On solving, we get $$x_1=x_2=\frac{-1}{1+2\lambda}.$$
Thus, the dual is $$\max_{\lambda} D(\lambda)= \max_{\lambda}\Big\{-\frac{1}{1+2\lambda}-\lambda\Big\},$$ where $\lambda\neq -\frac{1}{2}.$
Case 1: When $\lambda>\frac{1}{2}$, $$-\frac{1}{1+2\lambda}<0\text{ and }-\lambda<-\frac{1}{2}.$$
Hence, $D(\lambda)<-\frac{1}{2}$. So $D(\lambda)$ is bounded above.
Case 2: When $\lambda<\frac{1}{2}$, as $\lambda\rightarrow -\infty$, $$-\frac{1}{1+2\lambda} \rightarrow 0\text{ and }-\lambda\rightarrow \infty.$$ In this case, $D(\lambda)$ is unbounded.

Solution 2:

$$f(x_1,x_2,\lambda)=x_1+x_2+x_1 x_2+\lambda (x_1^2+x_2^2-1)$$

$$\partial f/\partial x_1=1+x_2+2\lambda x_1=0 \Rightarrow x_2=-1-2\lambda x_1$$

$$\partial f/\partial x_2=1+x_1+2\lambda x_2=0 \Rightarrow 1+x_1-2\lambda -4\lambda^2 x_1=0 \Rightarrow \lambda=1/2 \lor x_1=-\frac{1}{2\lambda+1}$$

When $\lambda \neq \pm \frac{1}{2}$:

$x_1=-\frac{1}{2\lambda+1}$, $x_2=-1-2\lambda x_1=-\frac{1}{2\lambda+1}=x_1$, $x_1^2+x_2^2=2x_1^2=1\Rightarrow x_1=\pm\frac{1}{\sqrt{2}}\Rightarrow$ $x_1+x_2+x_1 x_2=\pm \sqrt{2} +\frac{1}{2}$.

When $\lambda=1/2$:

$x_2=-1-2\lambda x_1=-1-x_1 \Rightarrow x_1^2+x_2^2=2x_1^2+2x_1+1=1 \Rightarrow x_1^2+x_1=0\Rightarrow x_1=0 \lor x_1=-1$. For $x_1=0$, $x_2=-1$, $x_1+x_2+x_1 x_2=-1$. For $x_1=-1$, $x_2=0$, $x_1+x_2+x_1 x_2=-1$.

When $\lambda=-1/2$:

$x_2=-1-2\lambda x_1=-1+x_1\Rightarrow x_1^2+x_2^2=2x_1^2-2x_1+1=1\Rightarrow x_1^2-x_1=0\Rightarrow x_1=0 \lor x_1=1$. For $x_1=0$, $x_2=-1$, $x_1+x_2+x_1 x_2=-1$. For $x_1=1$, $x_2=0$, $x_1+x_2+x_1 x_2=1$.

The minimum value is $-1$ which is obtained at $x_1=-1,x_2=0$ or $x_1=0,x_2=-1$.