I have an optimization problem where the objective function is
$$\text{minimize}_{P \in S_n} ~~ \| PXP'-Y \|_1$$
over the set of permutation matrices $S_n$. However, my solver in Julia (convex 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?
$\endgroup$ 52 Answers
$\begingroup$$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)
$\endgroup$ $\begingroup$$$\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?
$\endgroup$ 2
