Take the 2-minute tour ×

I'm looking at the following problem: Minimize $\sum_{i=1}^{m} \frac{x_i}{x_{i-1}}$ under the constraints $-x_0 \le -1$, $x_{i-1} - x_i \le 0$, and $x_m \ge N$ where $N>0$ and $m>0$ are some constants. What methods can I use to evaluate this (symbolically)?

Edit: fixed typo in last constraint.

share|improve this question
That's a very roundabout way of stating the constraints $1\le x_0\le x_1\le\ldots\le x_m\ge -N$. –  joriki Apr 3 '13 at 9:33
True - I just wanted to write them in canonical form. –  somebody Apr 3 '13 at 9:56
What canonical form is this? –  joriki Apr 3 '13 at 10:15

1 Answer 1

up vote 1 down vote accepted

The first constraint is $x_0\geq 1$ and furthermore we have $x_i\geq x_{i-1}$. Therefore, $x_i\geq 1, \forall i\geq 0$. Knowing, that all $x_i$ have to be positive, we derive that $\frac{x_i}{x_{i-1}}\geq 1$ for every $i>0$. But this tells us, that our sum becomes minimal if each term equals its minimum, which is $1$. So we have to choose $x_i=c, \forall i\geq 0$ with $c\geq1$. Doing so, our minimum is $m$. I do not see how the constraint $x_m\geq N$ should be used. Assuming $N<1$ we already satisfy this constraint because $x_i\geq1$. If $N>1$ we can simply choose $c=N$, which does not change the result.

share|improve this answer
Why is the choice $\forall i\ge 0: x_i = c = N$ minimal? –  somebody Apr 3 '13 at 9:52
We know that $x_i/x_{i-1} \geq 1, \forall i$. So we have a minmum if it is equal to one. This is only the case if $x_i=x_{i-1} \forall i$ so all $x_i$ have to be the same. –  sonystarmap Apr 3 '13 at 10:46
Note that the question has changed and it's now $x_m\ge N$. –  joriki Apr 3 '13 at 10:49
@joriki: thanks! I think this does not change the fact that $x_i=N, \forall i$ is a solution of the problem. –  sonystarmap Apr 3 '13 at 10:55
@macydanim: It doesn't; it only changes some signs in your answer. –  joriki Apr 3 '13 at 10:57

Your Answer


