Abstract
We consider the problem of maximization of a quadratic form over a box. We identify the NP-hardness boundary for sparse quadratic forms: the problem is polynomially solvable for nonzero entries, but it is NP-hard if the number of nonzero entries is of the order for an arbitrarily small.
Then we inspect further polynomially solvable cases. We define a sunflower graph over the quadratic form and study efficiently solvable cases according to the shape of this graph (e.g. the case with small sunflower leaves or the case with a restricted number of negative entries).
Finally, we define a generalized quadratic form, called t-norm form, where the quadratic terms are replaced by t-norms. We prove that the optimization problem remains NP-hard with an arbitrary Lipschitz continuous t-norm. (C) 2021, Springer Nature Switzerland AG.