|
A fast scaling algorithm for minimizing separable convex functions subject to chain constraints R.K. Ahuja and J.B. Orlin, Operations Research 49,784-789, 2001 In this paper, we consider the problem of minimizing å jÎ N Cj(xj) , subject to the following chain constraints x1 £ x2 £ x3 £ … £ xn, where Cj(xj) is a convex function of xj for each j Î 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 xn and a lower bound on an optimal value of x1. Under the assumption that the evaluation of any function Cj(xj) 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(n2 log U) to solve the same problem. In addition, when our algorithm is specialized to the isotonic median regression problem (where å jÎ N Cj(xj) = å jÎ N cj|xj -aj| for specified values of cj’s and aj’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. |