Title: On the Complexity of Detecting Convexity over a Box,
Abstract: It has recently been shown that the problem of testing global convexity of
polynomials of degree four is {strongly} NP-hard, answering an open question of
N.Z. Shor. This result is minimal in the degree of the polynomial when global
convexity is of concern. In a number of applications however, one is interested
in testing convexity only over a compact region, most commonly a box (i.e.,
hyper-rectangle). In this paper, we show that this problem is also strongly
NP-hard, in fact for polynomials of degree as low as three. This result is
minimal in the degree of the polynomial and in some sense justifies why
convexity detection in nonlinear optimization solvers is limited to quadratic
functions or functions with special structure. As a byproduct, our proof shows
that the problem of testing whether all matrices in an interval family are
positive semidefinite is strongly NP-hard. This problem, which was previously
shown to be (weakly) NP-hard by Nemirovski, is of independent interest in the
theory of robust control.