$P \mapsto \left\| P X P' - Y \right\|_1$ is tagged as non-convex by Julia

Question

I have an optimization problem where the objective function is

$$\underset{P \in S_n}{\text{minimize}} \quad \left\| P X P' - Y \right\|_1$$

over the set of permutation matrices $S_n$. However, my solver in Julia (Convex.jl package) says the objective function is not DCP. Since it is the $\ell_1$ norm, I expect it to be convex. Can anyone explain me why it is not convex?

Answer 1

$$\begin{array}{ll} \text{minimize} & \| \mathrm P \mathrm X \mathrm P^{\top} - \mathrm Y \|_1\\ \text{subject to} & \mathrm P \in \mathbb P_n\end{array}$$

where $\mathbb P_n$ is the set of $n \times n$ permutation matrices. Since $\mathbb P_n$ is a discrete set, we have a discrete optimization problem, which is obviously non-convex. Instead, the feasible region could be the (convex) Birkhoff polytope $\mathbb B_n$, whose $n!$ extreme points are the $n!$ permutation matrices in $\mathbb P_n$.

Dropping the constraint $\mathrm P \in \mathbb P_n$ and introducing a new matrix variable $\mathrm Q \in \mathbb R^{n \times n}$, we obtain

$$\begin{array}{ll} \text{minimize} & \langle 1_n 1_n^{\top}, \mathrm Q \rangle \\ \text{subject to} & -\mathrm Q \leq \mathrm P \mathrm X \mathrm P^{\top} - \mathrm Y \leq \mathrm Q\end{array}$$

which is not a linear program (LP). It is a quadratically constrained linear program (QCLP). Is it even convex? What does Julia say?

Answer 2

$f(g(\cdot))$ is not convex just because $f(\cdot)$ is convex. A sufficient condition is, e.g., $f(\cdot)$ convex non-decreasing and $g(\cdot)$ convex.

In your case, simply plot the scalar function $|p^2-1|$ by hand and convince yourself that it is nonconvex.

(skipping the general problem that the set of permutation matrices is nonconvex to begin with)