Given a sequence of points y1, . . . , yn, isotonic regression seeks to fit a piecewise linear non-decreasing function that is as close as possible to the observed points. Figure 1 illustrates the comparison of the isotonic regression curve (blue) and usual least squares line (dotted red line) with 10 points. Formulate the problem of obtained the best isotonic regression curve in the least squares sense (that is, finding the best non-decreasing curve that minimizes the sum of squared errors between predictions and observations yi) as an optimization problem.

10 8 3 6 4 0 0 2 4 6 8 10 Figure 1: Isotonic regression with n = 10. Red points represent each observation. The blue line corresponds to the isotonic fit, whereas the red line (dotted) represents the usual linear regression line