Convex separable optimization is not much harder than linear optimization

Reviewer: Joseph M. Lambert

The authors consider nonlinear optimization in either integer or continuous variables for the optimization problem min i=1 n f i x i &vbm0;Axb where the f i are convex, the polyhedron X&vbm0;A x b is bounded, A is an m×n integer matrix, and b is an integer vector. They also consider the corresponding maximization problem. The paper contains two main results. First, the authors give a polynomial algorithm for the continuous problem that is polynomial in the input size, the logarithm of the accuracy desired in the solution, and &Dgr;, the maximum absolute value of the values of the subdeterminants of A . The second result is a polynomial algorithm for the integer nonlinear problem over a polytope with its &Dgr; polynomially bounded. The authors carefully state the polynomial aspect of the algorithms in the sense that, for arbitrary functions, the length of the input is not well defined. The algorithms contain no provision for representing the functions in the objective function. The authors assume that an oracle exists that will compute the functions on a polynomial grid and that this oracle is called at most polynomially many times. The analysis relies on sensitivity results on the proximity between integer and continuous solutions for separable nonlinear programs; proximity results between continuous solutions for two different piecewise linear approximations of the nonlinear objective function; and a strongly polynomial algorithm for linear programming when &Dgr; is of polynomial length. The algorithm maintains a feasible reg ion of boxlike shape that holds the optimal solution. The algorithm is iterative—at each iteration it reduces the volume of the box by a factor of 2 in each dimension and divides the interval for each variable x i into a grid of polynomially many points. The nonlinear objective function is then approximated by a piecewise linear function on that grid. This latter approximation problem is solved as an ordinary linear program. The paper presents a proximity result to the original problems and the solution found by the algorithm as a polynomial bound that depends on the bounds for linear programming problems and integer linear programming problems. The authors present short algorithms to determine the accuracy of the results. A key step in the algorithm is the solving of the linear integer programming problem in polynomial time. The paper gives no computational results. The concluding section discusses extensions of this work. The remaining problems are interesting and difficult. In particular, finding an optimal solution to an unconstrained optimization problem is a bottleneck to progress. Extending the work to nonseparable functions causes problems even if a proximity result can be proven, because the linearization of nonseparable functions can cause exponential explosions. This important paper is well written. It contains 23 references, all of which will be helpful to the reader.