# Linear optimization of line under points.

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?

-
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 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 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 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 Narain Jan 21 at 22:28

## 1 Answer

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 4, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9016312956809998, "perplexity_flag": "head"}