How do i find $$ \min \hspace{1cm} ||x||_2 - c^{T}x \\ \text{subject to} \hspace{1cm}Ax = b $$
My attempt: $x^T x - c^Tx - \lambda(Ax-b) = 0$. I need to differentiate this equation wrt $\lambda$ and $x$. But first, I am not sure this is the right formulation since $||x||_2 = \sqrt{x^Tx}$ rather than $x^Tx$. But if I use square root, I don't know how to proceed. What is the correct formulation?
Here is one approach:
Suppose $x_0$ is a minimum norm solution to $Ax_0 = b$, then if $Ax = b$ we have $x = x_0+ x-x_0$ with $x_0 \bot x-x_0$.
The problem becomes $\min_{\delta \in \ker A} \sqrt{\|x_0\|^2+\|\delta\|^2}-c^T \delta -c^T x_0$.
Let $k= \sup_{\|h\| \le 1, h \in \ker A} |c^T h|$ and suppose $h$ is a unit vector in $\ker A$ such that $\|h\|=1$ and $k=c^T h$.
If $k>1$ and $t >0$ then since $\sqrt{\|x_0\|^2+\|th\|^2}-tc^T h \le \|x_0\| + t(1-k)$, we see that the cost is unbounded below and so there is no solution as such.
If $ k \le 1$, since $-k\|\delta\| \le -c^T \delta $, we can assume that $\delta$ is a multiple of $h$ to get the equivalent problem $\inf_t \sqrt{\|x_0\|^2 + t^2} -t k$.
If $k=1$ then there is no minimiser, but it is clear that $\inf_t \sqrt{\|x_0\|^2 + t^2} -t =0$.
If $k<1$ then $t={1 \over \sqrt{{1 \over k^2} -1} } \|x_0\|$.