# $\ell_1$ norm is tagged as non-convex by Julia

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?

• $P X P'$ is quadratic, not linear. – Rodrigo de Azevedo Mar 20 '17 at 11:48
• does it matter, what is inside the matrix ?. For any matrix or vector norm is defined irrespective of the individual elements structure right ?. – Shew Mar 20 '17 at 11:54
• @Shew: It certainly matters what is inside the matrix. For example, $|\sin x|$ is not a convex function of $x$, even though the norm $|\cdots|$ is convex. – Henning Makholm Mar 20 '17 at 12:05
• Yes, true. So in general, the statement norm is a convex function is wrong. – Shew Mar 20 '17 at 12:08
• Can you paste the exact error message you're getting? – littleO Mar 20 '17 at 12:36

## 2 Answers

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

$$\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?

• minimize for Q, right ?. Then which P matrix I should use ? – Shew Mar 20 '17 at 16:51
• No, both $\rm P$ and $\rm Q$. You can use the constraint $\mathrm P \in \mathbb B_n$, which is a succinct way of writing $2n$ equality constraints and $n^2$ inequality constraints. – Rodrigo de Azevedo Mar 20 '17 at 16:58