Linear regressor to under/over estimate prediction Suppose I have a dataset $(X, Y) \in \mathbb{R}^{n \times 2}$ of 2d points and I want to fit a linear regressor, in such a way that it best underestimate the points (or overstimate them). To give an idea of what I mean, attached is an image of the regressor I want to obtain:

I understand that to obtain it I need to change the cost function to be minimized, and I have tried with the following term:
$$
\ell(X, Y) = \sum_{i = 1}^n |\hat{y}_i - y_i|\Phi(\hat{y}_i \ge y_i) + M\Phi(\hat{y}_i < y_i)
$$
With $M$ be a very large penalty, and $\Phi$ being the indicator function.
So far, it seems to not work as intended. Can someone give me a feedback?
 A: The solution depends on what you mean by "best underestimate".


*

*If you want to underestimate all points, then you are looking for a line such that all the points are above it. To do this, calculate the convex hull of your point cloud. Each pair of consecutive points on the lower half of the hull between the rightmost and the leftmost point defines a line such that all points are above (or on) it. In all but the most degenerate cases, there will be more than one such line, and you will need to decide how to choose between the lines.

*If you want a specified proportion of points above your line, e.g., 90%, then as Dave writes, quantile-regression with an appropriate value of the parameter $\tau$ (for 90%, pick $\tau=1-0.9=0.1$), is the tool of choice.
Here is an example with randomly generated points. In the left panel, the points that make up the convex hull are marked with red circles. Note how we find three lines that satisfy your condition (depending on the random seed, it will be more or fewer). R code below.

set.seed(3)
nn <- 50
xx <- rnorm(nn)
yy <- rnorm(nn)

par(mfrow=c(1,2))
plot(xx,yy,pch=19,las=1,xlim=c(-3,2),ylim=c(-3,2),main="Convex hull")
hull <- chull(xx,yy)
points(xx[hull],yy[hull],cex=1.7,col="red")

candidate <- 1
while ( TRUE ) {
    if ( xx[hull[candidate+1]]>xx[hull[candidate]] ) break
    abline(reg=lm(yy[hull[candidate:(candidate+1)]]~xx[hull[candidate:(candidate+1)]]))
    candidate <- candidate+1
}

plot(xx,yy,pch=19,las=1,xlim=c(-3,2),ylim=c(-3,2),main="Quantile regression")
require(quantreg)
abline(reg=rq(yy~xx,tau=0.1))

