Minimize linear objective subject to unit norm constraint I have a linear function with unit norm constraint that I need to minimize.
$$\begin{array}{ll} \underset{w}{\text{minimize}} & w^\top x\\ \text{subject to} & \|w\| = 1 \end{array}$$
Is there a way to do this analytically?
My current thinking is that:
$$ \frac{d}{d w} w^\top x = x $$
$$ w = \|x\| $$
But this doesn't seem to make sense at all. 
Thanks
 A: Taking the lagrangian we have equivalently
$$
L(w,\lambda) = w^\top x + \lambda (w^\top w -1)
$$
and the stationary points are the solutions for
$$
\nabla L = 0 = \cases{x+2\lambda w = 0\\ w^\top w - 1 = 0}
$$
As $w = -\frac{1}{2\lambda}x$ we have
$$
\frac{1}{4\lambda^2}x^\top x = 1
$$
or
$$
\lambda = \pm\frac 12||x||
$$
and finally
$$
w = \pm \frac{x}{||x||}
$$
A: Good thinking, incorrect calculation.  Instead of doing this "matricially", do it using the dot product: $w \cdot x$ is maximized for that $w$, of unit magnitude, which points in the direction of $x$.  Therefore, $w$ must be co-directional with $x$ and must have unit magnitude; i.e.,
$$
w = {1 \over || x ||} x.
$$
Your attempt at a gradient calculation is incorrect because it ignores the constraint that $w$ must lie on the unit sphere.  Here is a way to do it.  If $w(t)$ is a smooth curve on that sphere parametrized by $t$, however, and if the maximum of $w(t) \cdot x$ is attained at some $t^*$, then:
$$
0 = {d \over dt}|_{t = t^*} ( w(t) \cdot x ) = w'(t^*) \cdot x,
$$ 
which means $w'(t^*)$ must be orthogonal to $x$.  We see that $x$ is normal to the hyperplane that is tangent to the unit sphere at $w(t^*)$, which means that $w(t^*)$ is co-directional with $x$.
