Let \begin{align*} f_A(x) = x^\intercal A x \end{align*} for some positive semi-definite $A \in \mathbb{R}^{n\times n}$. Unlike the standard problem \begin{align*} f^* = \max_{x: \|x\| = 1}f_A(x) \end{align*} which is well-known to equal the largest eigenvalue $\lambda_1$ of $A$, obtained when $x$ equals the corresponding eigenvector, I'm interested in solving \begin{align*} \tilde{f} = \max_{x: x \in \sigma(v)} f_A(x) \end{align*} for a vector $v \in \mathbb{N}_{\ge 0}^n$ and $\sigma(v)$ is the set of all permutations of $v$. This can be formulated as an integer programming problem, but I'm wondering if there is a direct way to solve it. Here are my observations

  1. If we let $P$ be a $n \times n$ permutation matrix; that is, \begin{align*} P \in \mathcal{P} := \{P \in \{0, 1\}^{n\times n}: P \mathbf{1}_n = P ^\intercal\mathbf{1}_n = \mathbf{1}_n, \} \end{align*} then the problem can be reformulated as \begin{align*} \max_{P \in \mathcal{P}}(Pv)^\intercal A(Pv) \end{align*} which is a mixed-integer quadratic-programming. While there are efficient ways to solve this, one can show that $\mathcal{P}$ is not entirely convex and some kind of relaxation would be needed to make the problem not NP-hard.

  2. If $A$ were diagonal, say $A = \text{diag}(a_1, \cdots, a_n)$, then it can be easily shown that the optimal solution is \begin{align*} \tilde{f} = \sum_{i=1}^{n} a_{(i)} v_{(i)}^2 \end{align*} where $a_{(i)}$ are the order statistics of $a_i$; that is, a permutation of $a_i$ such that $a_{(1)} \le \cdots \le a_{(n)}$. This solution is obtained by simply matching the permuted elements of $v$ to match the ranks of the elements of $a$. One can show this result rather easily using the rearrangement inequality.

But, with the off-diagonal terms, this problem seems helpless to solve directly. What do you suggest?

  • $\begingroup$ Here, $x$ is the decision (optimization) variable, and $v$ is given. If it helps, we could write $f_{A, v}(x)$ to make it more clear. $\endgroup$ – Tom Chen Aug 16 '19 at 15:33
  • $\begingroup$ At first glance, this looks very much like an instance of the quadratic assignment problem. $\endgroup$ – Rodrigo de Azevedo Aug 16 '19 at 23:31

Note an answer but too long to write as a comment: Note that since $A$ is PSD, it is a gram matrix so we can write $A = M^TM$ for some $M$. Then note that $$x^TAx = \|Mx\|_2^2 $$ so it suffices to find $$ \max_{x : x \in \sigma(v)} \|Mx\|_2^2.$$ We can now expand to find that $$ \|Mx\|_2^2 = \sum_i \left( \sum_j m_{ij}x_j \right)^2 = \sum_i \sum_j m_{ij}^2x_j^2 + \sum_i \sum_{j \ne k} m_{ij} m_{ik} x_j x_k.$$ The above sum can be broken into two terms: $$ \sum_j x_j^2 \left( \sum_i m_{ij}^2 \right)$$ and $$ \sum_{j \ne k}x_jx_k \left( \sum_i m_{ij}m_{ik} \right). $$

Note that both of these sums can be maximized individually by using the rearrangement inequality since the sequences $\{x_j^2\}$ and $\{x_jx_k\}$ are permutation invariant. So in practice, you can check either of them individually and see which one is bigger. It would probably make sense to maximize the second sum since there are more terms and you might be able to control the error you received from the first sum if you have some control over the norms of the columns of $M$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.