On Mon, 8 Jul 2013 10:25:33 -0700 (PDT), firstname.lastname@example.org wrote:
>On Monday, July 8, 2013 6:41:18 AM UTC-7, Leon Aigret wrote: >> So you are looking for the minimum of y_mean - a x_mean - b ? > >Yes, subject to each y_i - y(x_i) being >=0 (the "lower bound" criterion).
About the only thing not yet done in this thread is summarizing the findings:
The lower bound criterion turns out to be equivalent with the requirement that the bounding line stays below, with just touching allowed, the convex hull of the set of points. The best line y = a x + b is the line with the highest value of a x_mean + b. Obviously, that must be the "tangent" to the convex hull in the lowest point of the intersection of the convex hull with the line x = x_mean. The solution may not be unique if that intersection point happens to be one of the original data points.
Only the line segment of the lower hull that crosses the line x = x_mean is needed, so the determination of the upper hull can be skipped, and is it no longer necessary, once a hull point has been listed with x > x_mean, to add a new point to the list, except immediately after removing one or more points. After completion, the last two points on the list lie on the required bounding line.