Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

1 Answer

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|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
add comment

Your Answer

 
discard

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.