Let $f(\bf{x})$ be the following function:
$$f\left( \mathbf{x} \right)={{\mathbf{x}}^{\text{T}}}{{\mathbf{S}}^{\text{T}}}\mathbf{Sx},$$
where $\mathbf{S}\in {{\left\{ -1,0,1 \right\}}^{N\times M}}$ is a given matrix with given $N$ and $M$, and $\bf{x}=\{\mathit{x}_\mathit{i}\}$ is a positive vector. Suppose that we have
$${{x}_{i}}\in \left\{ x_{i}^{\left( 1 \right)},x_{i}^{\left( 2 \right)},...,x_{i}^{\left( {{m}_{i}} \right)} \right\}$$
for all $1 \le i \le M$, where $m_i$ is a known integer, and the parameters $x_{i}^{\left( 1 \right)},x_{i}^{\left( 2 \right)},...,x_{i}^{\left( {{m}_{i}} \right)}$ are also given. Could you please help me how to obtain
$${{\mathbf{x}}^{*}}=\underset{\mathbf{x}}{\mathop{\arg \min }}\,f\left( \mathbf{x} \right)$$
in the most efficient way? Is there any polynomial algorithm to perform this minimization?