Linear optimization of line under points.

Question

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?

Answer 1

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.