# Stretching of a set of numbers to align to a reference

I am trying to align an ordered set of n real, strictly positive numbers

$$Q = {q_{1},q_{2},..., q_{n}}$$

to a reference set of the same size and with the same properties

$$R = {r_{1},r_{2},..., r_{n}}$$

I am looking for an analytical solution to find the resulting set

$$S = {s_{1},s_{2},..., s_{n}}$$

that minimizes the differences between S and R

$$F(S)=\sum_1^n|r_{i}-s_{i}|$$

$$argmin_S F(S)$$

but preventing the length of each "segment" $s_{n}s_{n+1}$ from stretching too much from the original length $q_{n}q_{n+1}$, keeping the ratio between two numbers $\alpha$ and $\beta$.

$$\alpha \le {s_{n+1} - s_{n}\over q_{n+1} - q_{n}} \le \beta$$

with $0\lt\alpha \le 1$ and $\beta \ge 1$ that are input data of the problem.

In case there is not an analytical solution, I would like to find a numerical solution with a complexity that is not exponential. Thank you.

-
Perhaps you mean "minimizing the difference between $S$ and $R$" instead? The equation for $F(S)$ probably also needs to refer to $r_i$ instead of $q_i$. –  Rahul Jan 12 '13 at 19:16
thank you, edited –  Alex Darsonik Jan 12 '13 at 19:20
hope it's understandable though. if it's lots of work to solve it, I'd like some pointers to solve such problems and I will try to answer the solution myself –  Alex Darsonik Jan 12 '13 at 19:40

This is a linear programming problem. Introduce $n$ variables $z_i$ with linear constraints \begin{align} z_i &\ge r_i-s_i, \\ z_i &\ge -(r_i-s_i). \end{align} For fixed $r_i$ and $s_i$, we have $\min z_i = \lvert r_i-s_i \rvert$. (It's instructive to visualize the two-dimensional feasible set for just $z_1$ and $s_1$.) So you can express your problem as minimizing the linear objective $$f(s_1,\ldots,s_n,z_1,\ldots,z_n) = z_1 + \cdots + z_n$$ subject to the linear constraints \begin{align} s_{n+1} - s_{n} &\ge \alpha(q_{n+1} - q_{n}),\\ s_{n+1} - s_{n} &\le \beta(q_{n+1} - q_{n}),\\ z_i &\ge r_i-s_i, \\ z_i &\ge -(r_i-s_i). \end{align}
@Alex: There is a lot of software out there for solving linear programming problems. You just put your numbers into the solver and it gives you the answer. I wouldn't recommend writing your own code to solve it yourself (just like you wouldn't write your own sqrt). –  Rahul Jan 12 '13 at 20:24