A fast scaling algorithm for minimizing separable convex functions subject to chain constraints

We consider the problem of minimizing Sigma (j epsilonN) C-j(x(j)), subject to the following chain constraints x(1) less than or equal to x(2) less than or equal to x(3) less than or equal to ... less than or equal to x(n) where C-j(x(j)) is a convex function of x(j) for each j epsilon N = {1, 2,...,n}. This problem is a generalization of the isotonic regression problems with complete order, an important class of problems in regression analysis that has been examined extensively in the literature. We refer to this problem as the generalized isotonic regression problem. In this paper, we focus on developing a fast-scaling algorithm to obtain an integer solution of the generalized isotonic regression problem. Let U denote the difference between an upper bound on an optimal value of x,, and a lower bound on an optimal value of x(1) Under the assumption that the evaluation of any function C-j(x(j)) takes O(1) time, we show that the generalized isotonic regression problem can be solved in O(n log U) time. This improves by a factor of n the previous best running time of O(n(2) log U) to solve the same problem. In addition, when our algorithm is specialized to the isotonic median regression problem (where C-j(x(j)) = c(j)\x, - a(j)\) for specified values of c(j)s and a(j)s, the algorithm obtains a real-valued optimal solution in O(n log n) time. This time bound matches the best available time bound to solve the isotonic median regression problem, but our algorithm uses simpler data structures and may be easier to implement.