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 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.

share|improve this question
1  
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

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
it it right that the first two formulas are identical? I read a bit about linear programming and get back to this, because I have no clue on how to use it to write my routine! –  Alex Darsonik Jan 12 '13 at 20:12
    
@Alex: They're not identical. I rewrote them anyway to make it more obvious. –  Rahul Jan 12 '13 at 20:21
    
@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
    
sorry i can't upvote! –  Alex Darsonik Jan 12 '13 at 21:41
    
got it! glpk rocks –  Alex Darsonik Jan 13 '13 at 1:48

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.