CONVEX SEPARABLE OPTIMIZATION IS NOT MUCH HARDER THAN LINEAR OPTIMIZATION

The polynomiality of nonlinear separable convex (concave) optimization problems, on linear constraints with a matrix with "small" subdeterminants, and the polynomiality of such integer problems, provided the integer linear version of such problems is polynomial, is proven. This paper presents a general-purpose algorithm for converting procedures that solves linear programming problems with or without integer variables, to procedures for solving the respective nonlinear separable problems. The conversion is polynomial for constraint matrices with polynomially bounded subdeterminants. Among the important corollaries of the algorithm is the extension of the polynomial solvability of integer linear programming problems with totally unimodular constraint matrix, to integer-separable convex programming problem that is polynomial in log(I/epsilon) and the input size and the largest subdeterminant of the constraint matrix is also presented. These developments are based on proximity results between the continous and integral optimal solutions for problems with any nonlinear separable convex objective function. The practical feature of our algorithm is that is does not demand an explicit representation of the nonlinear function, only a polynomial number of function evaluations on a prespecified grid.