COMPUTATIONAL-COMPLEXITY OF NORM-MAXIMIZATION

This paper discusses the problem of maximizing a quasiconvex function phi over a convex polytope P in n-space that is presented as the intersection of a finite number of halfspaces. The problem is known to be NP-hard (for variable n) when phi is the p(th) power of the classical p-norm. The present reexamination of the problem establishes NP-hardness for a wider class of functions, and for the p-norm it proves the NP-hardness of maximization over n-dimensional parallelotopes that are centered at the origin or have a vertex there. This in turn implies the NP-hardness of {-1, 1}-maximization and {0,1}-maximization of a positive definite quadratic form. On the "good" side, there is an efficient algorithm for maximizing the Euclidean norm over an arbitrary rectangular parallelotope.