Linear Programming: Minimizing Vertical Distance to Line

[morry]

Ok, I hope this is the right section.

I have a problem that I can't even start. I have a set of points on a plane. I need to formulate a linear program so that the vertical distance between each point and a line is minimised. The line must have a positive gradient, positive y-intercept and each point must be below the line.

I have no idea what I am doing. Can anyone point me in the right direction?
Cheers.

 

[morry]

Hmm, so how would I go about setting this up so I could solve it using matlab?
thanks for the help.

 

[morry]

Could I let x=[1,2,3,4,5 etc] and y=[5,4,3,2,1 etc] ie the points I am given.

Then make some function Y=mx+c? And I want to minimise Y-y.

Am I on the right track here?

 

[quantumdude]

Enuma Elish,

While we do appreciate the work that you put into the homework help section of PF, it is nonetheless contrary to the Physics Forums Guidelines (which you agreed to) to post complete solutions to problems, or to offer assistance to students who have not shown some attempt at the problem. I have therefore soft deleted your post, and will restore it once this thread is resolved.

Helping somone with homework is great. Doing someone's homework is not OK.

Tom

 

[EnumaElish]

make some function Y=mx+c? And I want to minimise Y-y.

That's correct but incomplete.

 

[morry]

Ok, so I create that linear function, add the rest of the constraints.

What I don't understand is how to get MATLAB to find the gradient. Is it just a matter of making m a variable too?

I think I get this, but I am not quite there.

Thanks for the help again Enuma. :)

 

[enigma]

Do you really need the gradient, or do you just need the derivative of the line?

If it's the second, look up finite difference approximations (Taylor series expansion with higher order terms discarded)

 

[morry]

Well, the question asks me to find the equation for the line. Its a straight line, so I suppose the derivative is the gradient.

Doing a Taylor series sounds a bit extreme, all I am asked to do it formulate a linear program.

Ill have a crack and see what I can do.

Thanks enigma.

 

[enigma]

Taylor series with one term is nothing more than a secant approximation. Find two points close together. Compute rise over run. Viola. Looking up finite difference approximation methods give you some ways to do it to minimize error

 

[morry]

Hmm, ok I think I can write the problem down correctly.

But I have no idea how to solve it using matlab. The only examples of these problems are the min f(x)=x1+x2 etc with constraints x1>2 etc.

I am a retard at matlab.

Heres what I just tried:
x=[1,2,3,5,7,9]
y=[4,7,9,17,9,14]

syms X
syms Y
Y=mX+c (I have no idea how to write this equation out)
How can I put in the constraints c>0, m>0, Y>y?

Cheers.