Why are the solutions of the $3\times 3$ system like that?

Question

Consider the problem:$$ \min \quad -x_1^2-4x_1x_2-x_2^2\\ \text{s.t.} \quad x_1^2 + x_2^2 = 1$$ The KKT system is given by\begin{align*} x_1 (-1 + v) + 2 x_2 &= 0 \tag{1} ,\\ x_2 (-1 + v) + 2 x_1 &= 0 \tag{2},\\ x_1^2 + x_2^2 &= 1 \tag{3} \end{align*} The solutions according to the book are$$ (x_1,x_2)=\left(\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}}\right),\ v=3;\\ (x_1,x_2)=\left(-\frac{1}{\sqrt{2}},-\frac{1}{\sqrt{2}}\right),\ v=3;\\ (x_1,x_2)=\left(\frac{1}{\sqrt{2}},-\frac{1}{\sqrt{2}}\right),\ v=-1,\\ (x_1,x_2)=\left(-\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}}\right),\ v=-1,\\ $$ I tried to solved by hand: Substracting (1) and (2) I get $(x_1-x_2)(1+v)=0$. As $v$ cannot be zero (by the KKT condition) we have that $x_1=x_2$ if $v\neq -1$.

Thus I get the solutions:$$ (x_1,x_2)=\left(\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}}\right);\\ (x_1,x_2)=\left(-\frac{1}{\sqrt{2}},-\frac{1}{\sqrt{2}}\right);\\ (x_1,x_2)=\left(\frac{1}{\sqrt{2}},-\frac{1}{\sqrt{2}}\right);\\ (x_1,x_2)=\left(-\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}}\right);\\ $$ only asking $v\neq -1$.

Why the book ask $v=-1$ and $v=3$? Could someone explain please?

Answer 1

First of all, your KKT system has a wrong sign, it must be \begin{align*} x_1 (-1 + v) \color{red}{-} 2 x_2 &= 0 \tag{1'} ,\\ x_2 (-1 + v) \color{red}{-} 2 x_1 &= 0. \tag{2'} \end{align*} However, the conclusion $(x_1-x_2)(1+v)=0$ from (1') minus (2') is correct.

You cannot get all four solutions "only asking $v\ne -1$" simply because if $v\ne-1$ then $x_1=x_2$, and it is only first two solutions that satisfy $x_1=x_2$. It means that when you study the case $v\ne-1$ you get first two solutions and $v=3$.

For a complete solution, you have to study the remaining case $v=-1$ as well. Set $v=-1$ into (1') and (2') to get $x_1+x_2=0$, i.e. $x_1=-x_2$, which gives you another two solutions from (3).

Answer 2

Using polar coordinates,

$$\begin{aligned} x_1 &= \cos (\theta)\\ x_2 &= \sin (\theta)\end{aligned}$$

we obtain the unconstrained $1$-dimensional maximization problem in $\theta$

$$\text{maximize} \quad 1 + 2 \sin (2\theta)$$

Differentiating the objective and finding where the derivative vanishes, we obtain $\cos(2\theta) = 0$, whose solution set is

$$\left\{ \frac{\pi}{4} + k \frac{\pi}{2} : k \in \{0,1,2,3\} \right\}$$

Thus, in terms of $x_1$ and $x_2$, the solution set is

$$\left\{ \pm \left(\frac{\sqrt 2}{2},\frac{\sqrt 2}{2}\right), \pm \left(\frac{\sqrt 2}{2},-\frac{\sqrt 2}{2}\right)\right\}$$

which is the same you obtained via other means.

Answer 3

$(x_1-x_2)^2\geq0$ gives $$x_1x_2\leq\frac{x_1^2+x_2^2}{2}=\frac{1}{2}.$$ The equality occurs for $x_1=x_2$.

Thus, $$-x_1^2-4x_1x_2-x_2^2=-1-4x_1x_2\geq-1-4\cdot\frac{1}{2}=-3.$$ The equality occurs for $$(x_1,x_2)\in\left\{\left(\frac{1}{\sqrt2},\frac{1}{\sqrt2}\right),\left(-\frac{1}{\sqrt2},-\frac{1}{\sqrt2}\right)\right\}$$ only.