Is the weighted graph matching problem a convex problem?

Question

According to Umeyama, the weighted graph matching problem can be formulated as

$min_P || PA_GP^T - A_H ||$

s.t. $P$ is a doubly stochastic matrix

where $A_G$ and $A_H$ are n-by-n matrices

How can we show the convexity of this problem?

Answer 1

The problem is not convex. You can have multiple different permutation matrices $P$ such that $PA_GP^{\mathrm T}=A_H$, but their convex combination may not have the same property.

For example, let $n=2$ and $A_G=A_H=\begin{bmatrix}1&0\\0&1\end{bmatrix}$. Then the optimal solutions are $P_1=\begin{bmatrix}1&0\\0&1\end{bmatrix}$ and $P_2=\begin{bmatrix}0&1\\1&0\end{bmatrix}$ with $P_1A_GP_1^{\mathrm T}=A_H=P_2A_GP_2^{\mathrm T}$, but their convex combination $P_3=\frac12P_1+\frac12P_2=\begin{bmatrix}1/2&1/2\\1/2&1/2\end{bmatrix}$ has $P_3A_GP_3^{\mathrm T}=P_3\ne A_H$.