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 have a set of points in two-dimensional space. I'd like to find the line of best fit that minimizes the distance between the line and the points such that the line is below all points. How can I find the slope and intercept of a line that minimizes this distance?

share|improve this question
    
Yes, I know OLS, but I don't want a line of best fit though the points. I want to find a line below all points. –  user1728853 Jan 21 '13 at 18:19
    
Thanks for the help. Unfortunately, I don't know how to do this. Can you provide a simple explanation? –  user1728853 Jan 21 '13 at 18:25
    
you can find the line with least squares and then translate this line so that he pass over the lowest point. At this point you can say that the line is below all points (except for one) –  the_candyman Jan 21 '13 at 18:44
1  
@the_candyman: Are you sure the translated line will be optimal among all possible lines that lie below all points? –  Rahul Jan 21 '13 at 22:28
add comment

1 Answer 1

up vote 2 down vote accepted

Just solve the following optimization problem for $(a,b)$: \begin{align*} \text{Minimize}&\quad \sum_{i=1}^n (y_i - (a \, x_i + b))^k \\ \text{such that}& \quad a \, x_i + b \le y_i \end{align*} Here, you can choose $k = 2$ (least squares) or $k=1$.

This is a smooth, convex problem (for $k=1$ even a linear problem). Try to write down the optimality conditions and solve them.

share|improve this answer
add comment

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.