The complexity of approximating a nonlinear program

Authors: Mihir Bellare and Phillip Rogaway

Reference: Journal of Mathematical Programming B, Vol. 69, No. 3, pp. 429-441, September 1995. (Earlier version in Complexity of Numerical Optimization, P. M. Pardalos, ed., World Scientific, 1993.)

Abstract: We consider the problem of finding the maximum of a multivariate polynomial inside a convex polytope. We show that there is no good polynomial time approximation algorithm for this problem unless P=NP. We show that even quadratic programming (the case where the polynomial is quadratic) has no good polynomial time approximation algorithm unless NP is contained in quasi-polynomial time. Our results rely on recent advances in the theory of interactive proof systems. They exemplify an unusual interplay of discrete and continuous mathematics - using a combinatorial argument to get a hardness result for a continuous optimization problem.

Full version available in PDF or PostScript .