How to solve the problem $\min c^T x$ subject to $Ax=0$ and $\|x\|_2^2\le1$ using KKT?

Question

Given an optimization as follows: \begin{align} \text{minimize}\quad &c^Tx \\ \text{subject to}\quad &Ax = 0 \\ & \|x\|_2^2 \leq 1 \end{align} where $A \in \Re^{m\times n}$ is of full row rank and $c \in \Re^n$. Let $x^*$ be the optimal solution to this problem. Because $c^Tx$, $\|x\|_2^2 - 1$ are convex and $Ax$ is linear, the KKT condition must hold: \begin{align} &c + 2v \cdot x^* + A^Tw = 0\\ &v \geq 0\\ &v \cdot (\|x^*\|_2^2 - 1) = 0\\ &Ax^* = 0\\ &\|x^*\|_2^2 - 1 \leq 0 \end{align}

The KKT condition is also sufficient in this case. But could anybody provides a hint how to solve the KKT problem to get the optimal $x^*$?

Answer 1

Solving the first condition gives you $x^* = -\tfrac{1}{2v}(A^Tw+c)$ for some $w \in \mathbb{R}^m$.

Using the fourth condition $Ax^* = 0$, you get $-\tfrac{1}{2v}(AA^Tw+Ac) = 0$.

Solving yields $w = -(AA^T)^{-1}Ac$. (Note that $AA^T$ is invertible since $A$ has full row rank).

Thus, $x^* = \tfrac{1}{2v}(A^T(AA^T)^{-1}Ac-c)$ where $v$ is some scalar.

Then, the third condition tells us that either $v = 0$ or $\|x^*\| = 1$. It should be obvious which one.