Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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).

share|cite|improve this question
$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
up vote 1 down vote accepted

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}||}$.

share|cite|improve this answer
Take $w=(1,0)^T$, then the minimizing $x$ is $(0,1)^T$. – copper.hat Aug 14 '12 at 16:44
what about the non-negativiy constraint? – leonbloy Aug 14 '12 at 18:11
@leonbloy thanks. I modify my answer. – vesszabo Aug 15 '12 at 8:07

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.