Minimize euclidean distance in relation to horizontal distance for a series of points by only adjusting y axis

constraintseuclidean-geometryoptimizationstatistics

So I have sort of a niche question for a personal project I have been working on for some time now and I was hoping someone could help me gain a little insight as to how to proceed.

Situation:

I am trying to come up with an algorithm that minimizes the euclidean distance from point to point to be as close as possible to the horizontal distance from point to point with the constraint that each element on the y axis can be incremented by an amount within a set of bounds.

Example:

I have a series of points on a 2D graph with a immutable x axis,
x = [10,20,25,30,35,40,45,50,55,60,70,80]

and a mutable y axis y = [20, 24, 28, 24 ,20 ,18, 20, 32 ,30, 28, 20 ,24]

I also have the constraint that each point in y can be raised by a c value anywhere from 0 to 2.

I am trying to come up with an algorithm that minimizes the euclidean distance from point to point to be as close as possible to the horizontal distance from point to point with the constraint that each element in y can be raised by 0 <= c <= n for a y of any length with any values and with any n > 0.

EDIT: To be clear, I want to minimize the difference between the euclidean distance and horizontal distance between all adjacent points. The constraints are that we can move each point in y up independently by anywhere between 0 and 2 units. We cannot however, change the x values.

I am very new to optimization problems and although I have seen problems that look similar to my question, I have not seen any that I've been able to gather enough information to help push me further towards an answer.

If possible, I was hoping someone would help me define the objective function, constraints, and other necessary functions that would lead me to an answer.

This is not a homework problem so therefore I have no course material to help guide me to an answer. The only guidance I have is from the comments and answers to this post. Please understand that I am in no way a mathematician so I really need all the help I can get. Thanks!

Best Answer

It sounds like you want to minimize the sum of Euclidean distances $$\sum_{i=1}^{n-1} \sqrt{(x_i-x_{i+1})^2+(y_i'-y_{i+1}')^2}$$ subject to $y_i' \in [y_i,y_i+2]$ for all $i\in\{1,\dots,n\}$. The initial sum of distances is $88.097$, and by perturbing $y$ to

[22, 26, 28, 25, 22, 20, 22, 32, 30, 28, 22, 24]

you can reduce the sum of distances to $82.398$.

enter image description here

By request, here is the SAS code:

data indata;
   input x y;
   datalines;
10 20
20 24
25 28
30 24
35 20
40 18
45 20
50 32
55 30
60 28
70 20
80 24
;

proc optmodel;
   set POINTS;
   num x {POINTS};
   num y {POINTS};
   read data indata into POINTS=[_N_] x y;

   var C {POINTS} >= 0 <= 2;
   impvar Yprime {i in POINTS} = y[i] + C[i];
   min Z = sum {i in 1..card(POINTS)-1} sqrt((x[i]-x[i+1])^2+(Yprime[i]-Yprime[i+1])^2);

   solve;

   create data outdata from [i] x y C Yprime;
quit;

proc sgplot data=outdata noautolegend;
   scatter x=x y=y;
   vector x=x y=Yprime / xorigin=x yorigin=y lineattrs=(color=red);
run;
Related Question