Do you think there exists a efficient algorithm(non brute-force) for the following problem. I search the optimal solution for the following problem: Given a vector $u=(u_1, u_2,..., u_k)^T$ with $\forall u_i \in \mathbb{N}, i \in \{1, 2, ..., k\}$. I search a vector $v=(v_1, v_2, ..., v_k)^T$ with $\forall v_i \in \{1, -1\}, i \in \{1, 2, ..., k\}$, such that the squared dot product $(uv)^2$ is minimal. Another objective funktion could be the absoulte value of the dot produvt $|uv|$. I have developed a algorithm that is based on a sorted list of $u_i$. But sadly this algorithm does not always calucluate the optimal value.
Any ideas? Thanks in advance!
This is, unfortunately, an NP-hard problem. It is a special case of the general quadratic maximization problem \begin{array}{ll} \text{minimize} & v^T Q v \\ \text{subject to} & v_i^2 = 1, ~i=1,2,\dots, n \end{array} where, in this case, $Q=uu^T$. The class of problems for general $Q$ is of considerable academic and practical interest. I found these lecture notes by Pablo Parillo at MIT that provide an overview of the problem an techniques for solving it approximately.