Can one maximize $\sum_i c_i x_i^2$ where the $c_i$ are constants (possibly negative), subject to linear constraints over the $x_i$?
This paper seems to come close to answering "no." They show it is NP-hard for target functions $x_1 - x^2_2$. However they have $x_1$ which is not squared, and from the two pages I can access online I can't understand if that's critical or not.
Bonus question: Is there a free software that can be tried to solve these problems (possibly heuristically)?