# Optimization with non-negativity and norm constraint

I am facing the following optimization problem:

$$\min_x w^tx \\ s.t. ||x|| = 1, \forall i: x_i \geq 0$$

where $w$ and $x$ are real valued vectors. How would I solve this?

My background is not optimization (only some experience with equality constraints via Lagrange multipliers).

-
$w^t x$ is the inner product of $w$ and $x$? What is the norm? $w^t x$ is a real number. – vesszabo Aug 14 '12 at 12:55
It should have been $x$ instead of $w^tx$. – bayer Aug 14 '12 at 12:56
Do you really mean ||w'*x||? Since w'*x is a scalar, the condition means that the objective w'*x is either 1 or -1. (oops sorry didn't see the clarification) – dmuir Aug 14 '12 at 13:12

Assume $\mathbf{w}\neq\mathbf{0}$. We have $$<\mathbf{w},\mathbf{x}>=||\mathbf{w}||\, ||\mathbf{x}|| \cos(\varphi)=||\mathbf{w}|| \cos(\varphi),$$ where $0\leq\varphi\leq\pi$ the angle between $\mathbf{w}$ and $\mathbf{x}$.
If $w_i\leq 0$ for all $i$ we obtain the minimal value in the only case $\varphi=\pi$ and $\mathbf{x}=\frac{\mathbf{w}}{||\mathbf{w}||}$.
If there are $i_0, j_0$ such that $w_{i_0}>0$ and $w_{j_0}<0$ then choose $\mathbf{y}$ such that $y_{i_0}:=0$ and $y_{j_0}:=-w_{j_0}$. Then $\mathbf{x}=\frac{\mathbf{y}}{||\mathbf{y}||}$.
If $w_i\geq 0$ for all $i$ then project $\mathbf{w}$ to the coordinate-axes. We obtain the vectors $\mathbf{w}_1,\ldots,\mathbf{w}_n$. The angles between $\mathbf{w}$ and $\mathbf{w}_i$ are $\varphi_i$. Choose $i_0$ such that the angle would be maximal (it is not necessarily unique). Then $\mathbf{x}=\frac{\mathbf{w}_{i_0}}{||\mathbf{w}_{i_0}||}$.
Take $w=(1,0)^T$, then the minimizing $x$ is $(0,1)^T$. – copper.hat Aug 14 '12 at 16:44