0

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?

Rein
  • 1,174
  • I don't think you can. The domain of your problem itself is not convex: a convex combination of permutation matrices is not generally a permutation matrix. –  Mar 04 '13 at 10:00
  • @RahulNarain Sorry the domain should be relaxed as doubly stochastic matrix – Rein Mar 04 '13 at 13:16

1 Answers1

0

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