# 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. Commented Aug 14, 2012 at 12:55
• It should have been $x$ instead of $w^tx$. Commented Aug 14, 2012 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) Commented Aug 14, 2012 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$. Commented Aug 14, 2012 at 16:44
• what about the non-negativiy constraint? Commented Aug 14, 2012 at 18:11
• @leonbloy thanks. I modify my answer. Commented Aug 15, 2012 at 8:07

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.