Suppose $A,B\succeq0$ and $C\in\mathbb R^{n\times n}$. I am hoping to solve an instance of the following optimization problem: $$ \min_{\textrm{permutation matrices }P} \mathrm{tr}(BP^\top AP+C^\top P) . $$ This objective function is convex in $P$, but the constraint forces $P$ to be a permutation matrix. In essence, this is the quadratic assignment problem (QAP) with an additional assumption that the objective function is convex.

If $A=0$ or $B=0$, the problem would be the linear assignment problem. If we relaxed the constraint and thought of $P$ as doubly-stochastic, we could optimize the resulting convex problem and get a permutation matrix anyway (the vertices of the Birkhoff polytope are permutations).

Is there any similar trick for the problem above? I know QAP is NP-hard in general, but maybe it's easier if the objective function is convex?

  • $\begingroup$ Hmm, at least "vanilla" gradient descent in the Birkhoff polytope won't do it. For instance, the objective function $\|P\|_{\mathrm{Fro}}^2=\mathrm{tr}(P^\top P)$ is constant for all permutation matrices but the minimizer in the Birkhoff polytope is a multiple of the constant matrix $\mathbf1\mathbf1^\top$. Motivation here comes from a particular MLE problem we're facing in statistics, but generically it seems natural to think about instances of QAP that are solvable. $\endgroup$ – Justin Solomon Sep 1 '19 at 22:54
  • $\begingroup$ Is there a decent way to randomly round a Birkhoff matrix into a permutation matrix? If so, you could solve the relaxed problem then round back into the space of permutation matrices. This paper seems to say there are decent algorithms for constructing an approximate Caratheodory decomposition which would definitely allow you to randomly round: users.cs.duke.edu/~kulkarni/papers/sparsebvn.pdf $\endgroup$ – cdipaolo Oct 7 '19 at 16:25
  • $\begingroup$ Hmm I guess you could round by solving a linear assignment problem: max <P,P0> subject to P doubly stochastic $\endgroup$ – Justin Solomon Oct 8 '19 at 17:13
  • $\begingroup$ Do you require a guarantee of finding the global optimum, or just an adequately "good" solution? If the latter, you could try something like $\ell_p$-box ADMM. $\endgroup$ – user3883 Oct 11 '19 at 11:19

Your Answer

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

Browse other questions tagged or ask your own question.