KKT points for minimization problem?

Question

I have the following problem:

$$\begin{array}{ll} \text{minimize} & \frac{1}{2} \|x \|_4^4\\ \text{subject to} & \| x \|_2^2 - 1 = 0\end{array}$$

and I don't know how to start. Maybe I can find all KKT points, but can anyone show me how to proceed? After finding KKT points, how would I also find the global max and min? Via the Hessian?

Answer 1

The Lagrangian is $$ L(x, \lambda) = \frac{1}{2} \| x \|_4^4 + \lambda (\| x \|_2^2 - 1) $$ and its partial derivative with respect to $x \in \mathbb R^d$ is

$$ \frac{\partial L(x, \lambda)}{\partial x} = (2 x_i^3 + 2 \lambda x_i)_{i = 1}^{d} = 2 \big( x_i (x_i^2 + \lambda) \big)_{i = 1}^{d}.$$

For this partial derivative to be zero, we either need $x_i = 0$ or $x_i = \pm \sqrt{\lambda}$. If all entries are choosen to be zero, we have $\| x \|_2^2 = 0 \ne 1$, so this is not a minimiser.

Let $\tilde{x}$ have $k \in \{ 1, \ldots, d \}$ entries equal to $\pm \sqrt{\lambda}$ and the rest be zero. Plugging $\tilde{x}$ into the constraint yields

$$ 1\overset{!}{=} \| \tilde{x} \|_2^2 = \sum_{i = 1}^{d} x_i^2 = k \lambda, $$ implying $\lambda = \frac{1}{k}$.

Hence the minimum is achieved for any vector with $k \in \{1, \ldots, d \}$ entries equal to $\pm \frac{1}{\sqrt{k}}$ and the rest equal to zero. For such a vector $\tilde{x}$ we have $$ \frac{1}{2} \| \tilde{x} \|_4^4 = \frac{1}{2} \sum_{i = 1}^{d} x_i^4 = \frac{1}{2} k \left( \frac{1}{\sqrt{k}} \right)^4 = \frac{1}{2 k}. $$ Hence the optimal value is

$$ \min_{k \in \{ 1, \ldots, d \}} \frac{1}{2k} = \frac{1}{2 d},$$ which is achieved for a vecvtor consisting of the entries $\pm \frac{1}{\sqrt{d}}$.