Minimizing a convex cost closure set
Abstract
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 problem, or (CCC) -- 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 convex cost closure problem is a generalization of both
minimum cut and of minimization of n convex functions this
complexity is fastest possible. For the quadratic problem the
complexity of our algorithm is strongly polynomial, O(mn\log
{\frac{n^2}{m}}). For the isotonic regression problem the
complexity is O(n\log U), for U the largest range for a
variable value.
Download Information
Click on the following title to view and download the paper in PostScript format.
Email to me if you wish to get a copy.
hochbaum@ieor.berkeley.edu
10/30/02