EPSILON-APPROXIMATION MINIMIZATION OF CONVEX-FUNCTIONS IN FIXED DIMENSION

We consider the problem of minimizing a convex function v(lambda), ove r a closed convex set Lambda subset of or equal to R(m), where for som e fixed c is an element of R(n), an n x m matrix A of reals, and a set X subset of or equal to R(n), we define v(lambda) = max {(c - A lambd a)(T)x:x is an element of X}. We show the following result: if for any given lambda is an element of Lambda, and any fixed epsilon, 0 < epsi lon < 1, v(lambda) can be evaluated by an epsilon-approximation (stron gly) polynomial combinatorial algorithm, and if any linear function in lambda can be optimized over Lambda by a strongly polynomial combinat orial algorithm, then for a fixed dimension m, v = v(lambda*) = min { v(lambda): lambda is an element of Lambda} epsilon-approximation (stro ngly) polynomial combinatorial algorithm.