Minimize $x + y + z$ subject to $x^2 + y^2 + z^2 \le 1$ and $x \ge 0$

Question

I'm trying to solve this problem by KKT's condition:

$$\begin{align*} \text{min} & \quad x + y + z \\ \text{s.t} & \quad x^2 + y^2 + z^2 &&\le 1 \\ & \quad x &&\ge 0 \end{align*}$$

The linear independence constraint constraint qualification - LICQ is

The gradients of the active inequality constraints and the gradients of the equality constraints are linearly independent at $x^{*}$.

The Mangasarian-Fromovitz constraint qualification - MFCQ is

The gradients of the equality constraints are linearly independent at $x^{*}$ and there exists a vector $v \in \mathbb{R}^{n}$ such that $\langle \nabla g_{i}\left(x^{*}\right), v \rangle<0$ for all active inequality constraints and $\langle \nabla h_{j}\left(x^{*}\right), v\rangle=0$ for all equality constraints.

Could you please verify if I correctly apply the KKT's theorem? Thank you so much for your help!

---

$\textbf{My attempt:}$

Let $f = x + y + z$, $g_1 = x^2+y^2 + z^2-1$, $g_2 = -x$, and $$\mathcal K= \{(x,y,z) \in \mathbb R^3 \mid g_1(x,y,z) \le 0 \text{ and } g_2(x,y,z) \le 0\}$$

Because $\mathcal K$ is compact and $f$ is continuous, the problem has a solution.

Moreover, $\nabla f (x,y,z) = \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix}$, $\nabla g_1 (x,y,z) = \begin{pmatrix} 2x \\ 2y \\ 2z \end{pmatrix}$, and $\nabla g_2 (x,y,z) = \begin{pmatrix} -1 \\ 0 \\ 0 \\ \end{pmatrix}$. Consider the system $$\begin{cases} \mu_1 \nabla g_1 (x,y,z) + \mu_2 \nabla g_2 (x,y,z) &=0 \\ g_1(x,y,z) &= 0\\ g_2(x,y,z) &=0 \end{cases} \iff \begin{cases} \mu_1 \begin{pmatrix} 2x \\ 2y \\ 2z \end{pmatrix} + \mu_2 \begin{pmatrix} -1\\ 0 \\ 0 \\ \end{pmatrix} &= \begin{pmatrix} 0\\ 0 \\ 0 \\ \end{pmatrix} \\ x^2 + y^2 + z^2 &= 1\\ -x &= 0 \end{cases}$$

$$\iff \begin{cases} x &= 0\\ \mu_2 &= 0 \\ \mu_1 y &= 0 \\ \mu_1 z &= 0\\ y^2+z^2 &= 1 \end{cases} \implies \mu_1 = \mu_2 = 0 $$

Hence LICQ is satisfied. It follows from KKT's theorem that the solution satisfies

$$\begin{cases} \mu_1,\mu_2 &\ge 0\\ \mu_1 g_1(x,y,z) &= 0\\ \mu_2 g_2(x,y,z) &=0 \\ \nabla f (x,y,z) + \mu_{1} \nabla g_1(x,y,z) + \mu_{2} \nabla g_2(x,y,z)&=0 \end{cases} \iff \begin{cases} \mu_1, \mu_2 &\ge 0\\ \mu_1 (x^2+y^2 + z^2-1) &=0\\ \mu_2 x &= 0 \\ \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix} +\mu_1 \begin{pmatrix} 2x \\ 2y \\ 2z \end{pmatrix} + \mu_2 \begin{pmatrix} -1\\ 0 \\ 0 \\ \end{pmatrix} &= \begin{pmatrix} 0\\ 0 \\ 0 \\ \end{pmatrix} \end{cases}$$ $$\iff \begin{cases} \mu_1, \mu_2 &\ge 0\\ \mu_1 (x^2+y^2 + z^2-1) &=0\\ \mu_2 x &=0 \\ 1+ 2 \mu_1 x &= \mu_2 \\ 1+ 2 \mu_1 y &=0 \\ 1+ 2 \mu_1 z &=0 \end{cases} \iff \begin{cases} \mu_1 &> 0\\ \mu_2 &\ge 0\\ \mu_2 x &=0 \\ x^2+y^2 + z^2 &= 1 \\ 1+ 2 \mu_1 x &= \mu_2 \\ 1+ 2 \mu_1 y &=0 \\ 1+ 2 \mu_1 z &=0 \end{cases}$$ $$\iff\begin{cases} \mu_1 &= 1/\sqrt{2}\\ \mu_2 &= 1 \\ x &=0 \\ y &=-1/\sqrt{2} \\ z &=-1/\sqrt{2} \end{cases} \qquad \text{or} \qquad\begin{cases} \mu_1 &= \sqrt{3}/2 \\ \mu_2 &= 0 \\ x &= -1/\sqrt{3} \\ y &= -1/\sqrt{3} \\ z &= -1/\sqrt{3} \end{cases}$$

Comparing the values at these points, we get the solution is $(x,y,z) = (-1/\sqrt{3},-1/\sqrt{3},-1/\sqrt{3})$.

Answer 1

Your ultimate solution is wrong because $x$ is not $\ge 0$, but the other solution where $x = 0$ is correct. Also there's a lot of work there and I'm not sure how much of it is necessary. (It's all correct except for the solution you have with $x < 0$.) I guess my point is we can just assume that $x^2 + y^2 + z^2 = 1$ and $x = 0$, get an easy Lagrange-multiplier problem and then go back and check the KKT conditions + regularity conditions. This is how I solved it, so you can compare:

If we only have $x^2 + y^2 + z^2 \le 1$ then $\min x + y + z$ occurs along the line $t(1,1,1)$ and from that you get $(x,y,z)=(-1/\sqrt3, -1/\sqrt3, -1/\sqrt3)$ without having to do any complicated calculation.

If we want $x \ge 0$ then it must be that $x = 0$ since we are sliding the level set $x + y + z = -3/\sqrt{3}$ to a point where $x \ge 0$ and that must happen at $x = 0$. So now if $x = 0$ we get $\min y + z$ subject to $y^2 + z^2 \le 1$ and this occurs along the line $t(0,1,1)$. That is, the optimal point is

$$ (x,y,z) = \left(0, -\frac1{\sqrt{2}}, -\frac1{\sqrt{2}} \right).$$

Now the easiest regularity to check is either linear independence or Slater's condition. For linear independence, the gradients of $x$ and $x + y + z$ are $(1, 0, 0)$ and $(1, 1, 1)$ so they are independent. Slater's condition is also easily seen to hold.

Finally, let us check the KKT conditions:

1. Complementary slackness is irrelevant because both inequalities are tight.
2. Feasibility is by construction.
3. We have

$$(1, 1, 1) + \frac{1}{\sqrt{2}}(0,-\sqrt{2},-\sqrt{2}) + (-1,0,0) = (0,0,0).$$

Now, in general, the KKT conditions are not sufficient. But they are for convex programs that satisfies Slater's condition (i.e. the feasible region has an interior point). You can also see directly that this is the minimum if you can see directly that 1. both inequalities are tight and 2. $y + z$ has a unique minimum on the curve $y^2 + z^2 = 1$.

Answer 2

Alternate Solution :

$x^2 + y^2 + z^2 \le 1 $ represents a solid sphere of radius 1

Now, we need to find a point on sphere such that the value of $x+y+z$ is minimum

It is also given that, $x \ge 0 $ , So we need to only consider the 4 octants out of 8

Now, out of these 4 octants, a minimum occurs when both $y$ and $z$ are negative, so we need to consider only 5th octant. Since $y$ and $z$ are negative a minimum occurs on the surface of the sphere i.e $y^2 + z^2 = 1$

Since $y$ and $z$ are already chosen to be negative, all it remains is what values of x make the result minimum, it is simply at x = $0$

All we need to find is a point on the sphere such that $x = 0$, $y$ and $z$ are negative. It doesn't take a lot of work to think that it occurs simply at $y = z$

$\implies y^2 + y^2 = 1 \implies y = z = \frac{-1}{\sqrt{2}} $

So, we can conclude that a minimum occurs at $(0,\frac{-1}{\sqrt{2}}\frac{-1}{\sqrt{2}})$

and hence the minimum value is $-\sqrt{2}$

Hope this helps.