Maximizing Non-Linear Concave Functions in Fixed Dimension

Consider a convex set in R^d and a piecewise polynomial concave function . Let be an algorithm that given a point x ∈ R^d computes F(x) if , or returns a concave polynomial p such that p(x) < 0 but for any , p(y) ≥ 0. We assume that d is fixed and that all comparisons in depend on the sign of polynomial functions of the input point. We show that under these conditions, one can find in time which is polynomial in the number of arithmetic operations of . Using our method we give the first strongly polynomial algorithms for many non-linear parametric problems in fixed dimension, such as the parametric max flow problem, the parametric minimum s-t distance, the parametric spanning tree problem and other problems. We also present an efficient algorithm for a very general convex programming problem in fixed dimension.