Minimizing a convex cost closure set

Many applications in the area of production and statistical estimation are problems of convex optimization subject to ranking constraints that represent a given partial order. This problem, which we call the convex cost closure (CCC) problem, is a generalization of the known maximum ( or minimum) closure problem and the isotonic regression problem. For a CCC problem on n variables and m constraints we describe an algorithm that has the complexity of the minimum cut problem plus the complexity of finding the minima of up to n convex functions. Since the CCC problem is a generalization of both minimum cut and minimization of n convex functions, this complexity is the fastest one possible. For the quadratic problem the complexity of our algorithm is strongly polynomial, O(mn log n(2)/m). For the isotonic regression problem the complexity is O(n log U) for U the largest range for a variable value.