minimize $c^Tx$ such that $Ax=0, x^Tx\leq1$

Solution 1:

Let $N$ be a matrix where its columns consists of basis of nullspace of $A$.

That is we can define a vector $y$ such that $Ax = 0$ can be rewritten as $x=Ny$. That is rather than solving for $x$, we can solve for $y$.

$x^Tx=1$ is equivalent to $y^TN^TNy=1$.

Now, we are trying to solve for

$$\min (c^TN)y$$

subject to $$y^T(N^TN)y=1$$

which is equivalent to $$\max (-c^TN)y$$

subject to $$y^T(N^TN)y=1.$$

It is an optimization problem over an ellipsoid which has been addressed here

The optimal $y$ is

$$y^*=-\frac1{\sqrt{(c^TN)(N^TN)^{-1} (N^Tc)}} (N^TN)^{-1}N^Tc$$

and we can compute $x^*=Ny^*$.