Optimization Online


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

Shashi Mittal (mshashi***at***alum.mit.edu)
Andreas S. Schulz (schulz***at***mit.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society