An FPTAS for Optimizing a Class of Low-Rank Functions Over a Polytope

Shashi Mittal (mshashialum.mit.edu)
Andreas S. Schulz (schulzmit.edu)

Abstract: We present a fully polynomial time approximation scheme (FPTAS) for optimizing a very general class of nonlinear functions of low rank over a polytope. Our approximation scheme relies on constructing an approximate Pareto-optimal front of the linear functions which constitute the given low-rank function. In contrast to existing results in the literature, our approximation scheme does not require the assumption of quasi-concavity on the objective function. For the special case of quasi-concave function minimization, we give an alternative FPTAS, which always returns a solution which is an extreme point of the polytope. Our technique can also be used to obtain an FPTAS for combinatorial optimization problems with non-linear objective functions, for example when the objective is a product of a fixed number of linear functions. We also show that it is not possible to approximate the minimum of a general concave function over the unit hypercube to within any factor, unless P = NP. We prove this by showing a similar hardness of approximation result for supermodular function minimization, a result that may be of independent interest.

Keywords: Non-convex optimization, Combinatorial optimization, Approximation schemes

Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization )

Category 2: Combinatorial Optimization (Approximation Algorithms )

Category 3: Global Optimization (Theory )

Citation: Technical report, Operations Research Center, Massachusetts Institute of Technology.

Download: [Postscript][PDF]

Entry Submitted: 09/07/2011
Entry Accepted: 09/07/2011
Entry Last Modified: 09/07/2011

Modify/Update this entry