3

It's my first time on this site:) I have to find a strictly increasing finite sequence $\{x_k\} _{k=1, \dots, n}$ with $x_1=c^2$ that will minimize the following expression $$\sum_{i=1}^n\sqrt{x_{i+1}-x_i} \frac{c}{\sqrt{x_i}},$$ subject to the constraint $x_{n+1}=c^\frac{2}{3}$, where $c$ is a constant less than 1.

It seems like an optimization problem but in my experience I have only had to minimize expressions with respect to one or few variables. Here, even the number of variables is unknown. I'm having problems understanding how to find an optimal sequence without presupposing its length. Is this even possible and does there exist any thoery on this subject?

For this particular problem, it makes sense to me to keep adding elements to the sequence in the beginning in order to make use of the $\frac{c}{\sqrt{x_i}}$ factor, and eventually, with enought terms, splitting the interval $[c^2,c^\frac{2}{3}]$ further is harmful because the dominating effect comes from creating a new term in the summation. It also seems the sequence should have more points close to $c^2$ than to the other endpoint, $c^\frac{2}{3}$, but that is as far as I've got.

Albert Fletcher
  • 191
  • The number of variables is known: it is $n-2$, because $x_1$ and $x_n$ are fixed. Also, note that you may factor $c$ out of your sum. Also, if $x_1=0$ then you divide by $0$ in the sum, fix this! – Alex M. Jun 01 '15 at 14:57
  • Right, it should be $x_1=c^2$. I'll edit that in the original post. Are you saying I should fix n=3, find the optimal solution, then fix n=4, find the optimal solution for that case, compare, and so on? – Albert Fletcher Jun 02 '15 at 10:18

2 Answers2

1

I think it might be that the lowest sum comes from putting all the intermediate points equal to either $x_1$ or $x_{n+1}$.
As a check: Fix all $x_j$ except one, $x_i$, then choose the best value for it. There are only two terms that involve $x_i$. Differentiate them with respect to $x_i$, and solve. The minimum is either where the derivative is zero; or at one end of the interval. But if it is at one end of the interval, that means either $x_i=x_{i-1}$ or $x_i=x_{i+1}$. And I think that is what happens.

Empy2
  • 50,853
  • This is what I was working on when it hit me: the OP wants a strictly increasing sequence. – Alex M. Jun 02 '15 at 10:57
  • How about $c,c+0.0000001,c+0.0000002,...c+0.000000n,c^{2/3}$ – Empy2 Jun 02 '15 at 10:59
  • First, note that $x_1 = c^2$; second, just adding some "epsilon" to each term in order not to make them equal cannot count for a solution. – Alex M. Jun 02 '15 at 11:00
  • Sorry about the $c^2$. I meant that the set of strictly increasing sequences is an open set, and may not have a minimum. The boundary of strictly increasing sequences is the set of increasing sequences with repetition; the best you can do with a strictly increasing sequence is get really close to the minimum. – Empy2 Jun 02 '15 at 11:03
1

As suggested in another answer, there is no minimum with a strictly increasing sequence. To see this note first that, given that we are dealing with positive numbers only:

$$ \sum_{i=1}^n \sqrt{x_{i+1}-x_i}\frac{c}{\sqrt{x_i}} = c \sum_{i=1}^n \sqrt{\frac{x_{i+1}}{x_i}-1}$$

For a strictly increasing sequence we can write $x_{i+i}=(1+y_i^2)x_i$ where $y_i^2>0$ is the increment at step $i$. Writing $y_i^2$ rather than $y_i$ is just a matter of convenience, so that the sum simplifies nicely:

$$\sum_{i=1}^n \sqrt{\frac{x_{i+1}}{x_i}-1} = \sum_{i=1}^n \sqrt{1+y_i^2-1} = \sum_{i=1}^n y_i $$

Here we can see easily that the minimum would $y_i=0$ for all $i$ (all $x_i$'s equal to $x_1$, apart from $y_1$ which must be zero per your constraints, and $y_n$ which must be $x_{n+1}-x_1$). However, this choice is forbidden by the constraint that the sequence be increasing.

Stefano
  • 309