Skip to main content
added 1 characters in body
Source Link
gondolier
  • 1.8k
  • 12
  • 19

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 hashave 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.

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 has 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.

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.

upper case title
Link
Charles Matthews
  • 12.6k
  • 35
  • 64

minimizing Minimizing quadratic form over permutations

added 4 characters in body
Source Link
gondolier
  • 1.8k
  • 12
  • 19

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)$$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 has 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.

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 has 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.

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 has 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.

Source Link
gondolier
  • 1.8k
  • 12
  • 19
Loading