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).
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}||}$.
Construct $x$ from an unconstrained vector $u$ $$\eqalign{ \def\qiq{\quad\implies\quad} \def\s{\oslash} \def\h{\odot} \def\o{{\tt1}} \def\P{\frac{\o}{\pi}} \def\PK{\frac{\o}{\|p_k\|}} \def\p{\partial} \def\e{{\large\varepsilon}} \def\l{\lambda} \def\c#1{\color{red}{#1}} \def\BR#1{\Big(#1\Big)} \def\LRB#1{\left[#1\right]} \def\LR#1{\left(#1\right)} \def\fracLR#1#2{\LR{\frac{#1}{#2}}} p &= \tfrac12\, u\h u &\qiq &p\ge0,\quad\pi = \|p\| \\ U &= \operatorname{Diag}(u) &\qiq &dp = u\h du = U\,du \\ x &= \frac{p}{\|p\|} &\qiq &\|x\| = \frac{\|p\|}{\|p\|}=\o \\ &&\qiq &x\ge0 \\ \\ dx &= \LR{\frac{\pi^2\,I-pp^T}{\pi^3}}dp &\quad\;\;=&\P\LR{I-xx^T}U\,du \\ }$$ where $\h$ denotes the elementwise/Hadamard product.
Rewrite the objective and calculate the gradient wrt $u$ $$\eqalign{ \l &= w^Tx \\ d\l &= w^T\,\c{dx} \\ &= w^T\,\c{\P\LR{I-xx^T}U\,du} \\ &= \P\BR{U\LR{I-xx^T}w}^Tdu \\ &= \P\BR{w\h u -(w^Tx)\,(x\h u)}^T du \\ \frac{\p \l}{\p u} &= \P\BR{w -(w^Tx)\,x}\h u \\ }$$ This gradient expression can be used in a gradient descent iteration $$\eqalign{ p_k &= \tfrac12\,u_k\h u_k \\ x_k &= \frac{p_k}{\|p_k\|} \\ g_k &= \frac{u_k}{\|p_k\|}\h\BR{w -(w^Tx_k)\,x_k} \\ u_{k+1} &= u_k - \sigma_k\,g_k \\ k &= k+\o \\ }$$ where the recipe for the step length $\sigma_k$ differs from algorithm to algorithm.
A good starting point for the iteration is to find the minimum component of $w$ $$j=\arg\min_j(w)$$ and set $u=40\,\e_j\:$ (the corresponding cartesian basis vector).
This would be the exact solution to the related problem with $\|x\|=\|x\|_\o$
and will be closer to the solution of the current problem with $\|x\|=\|x\|_2\:$
than a random guess.
