Stretching of a set of numbers to align to a reference

Question

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.

Answer 1

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