1
$\begingroup$

Let $Q$ be an $n \times n$ real symmetric matrix and $x$ an $n \times 1$ real vector. Consider the following minimization problem:

$\min_{\pi \in S_n} ~(\pi x)^{\rm T} Q (\pi x)$,

where $S_n$ denotes the collection of all permutations on $x$.

I wonder if there is any sufficient condition on the matrix $Q$ that guarantees that the solution is given by the permutation that puts $x$ in increasing order. For instance, such a $Q$ qualifies: $Q = \left(\begin{matrix} 0 & -1 & 0 & 0 \\\ -1 & 0 & 0 & 0 \\\ 0 & 0 & 0 & -1 \\\ 0 & 0 & -1 & 0\end{matrix}\right)$. Does it have anything to do with majorization theory?

P.S., I googled a bit and it seems this is a particularization of the so-called quadratic assignment problem. There are a lot of discussions dealing with complexity of finding the solution. I wonder if we can we come up with some sufficient condition to guarantee that the optimal solution is to simply perform a sort.

$\endgroup$
4
  • 1
    $\begingroup$ Unless there are more conditions on $x$, a necessary condition is that $Q$ be persymmetric (both equal to its transpose and unchanged when the order of the rows and order of the columns are reversed) since $x$ and $-x$ take the same value on the quadratic form but are sorted in opposite order. $\endgroup$
    – Tracy Hall
    Aug 3, 2010 at 6:02
  • $\begingroup$ Did you mean for the example $Q$ to have its $1$'s on the antidiagonal, or to have $-1$'s, or for the optimization to seek the maximum? As stated, $Q$ fails for $x$ with two $0$'s and two $1$'s: the minimum is $0$, but sorting gives $2$. $\endgroup$
    – Tracy Hall
    Aug 3, 2010 at 6:17
  • $\begingroup$ Sorry for the typo... 1's should be -1's. $\endgroup$
    – gondolier
    Aug 3, 2010 at 6:24
  • $\begingroup$ BTW, the x I am considering is a probability vector, or equivalently, $x \in \mathbb{R}_+^n$. $\endgroup$
    – gondolier
    Aug 3, 2010 at 6:26

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.