LCS Publication Details
Publication Title: THE COMPLEXITY OF CONTINUOUS OPTIMIZATION
Publication Author: Rogaway, Phillip
Additional Authors:
LCS Document Number: MIT-LCS-TM-452
Publication Date: 6-1-1991
LCS Group: No Group Specified
Additional URL: No URL Given
Abstract:
given a polynomial objective function f(x1,....,xn), we consider the problem of finding the maximum of this polynomial inside some convex set D={ : Ax, B}. We show that, under a complexity assumption, this extremum cannot be approximated by ant polynomial-time algorithm, even exceeding poorly. This represents an unusual interplay of discrete and continuous mathematics: using a combinatorial argument to get a hardness result for a continuous optimization problem.
To obtain this publication:

    To purchase a printed copy of this publication please contact MIT Document Services.