2
$\begingroup$

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$
  • $\begingroup$ $P X P'$ is quadratic, not linear. $\endgroup$ – Rodrigo de Azevedo Mar 20 '17 at 11:48
  • $\begingroup$ does it matter, what is inside the matrix ?. For any matrix or vector norm is defined irrespective of the individual elements structure right ?. $\endgroup$ – Shew Mar 20 '17 at 11:54
  • 1
    $\begingroup$ @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. $\endgroup$ – Henning Makholm Mar 20 '17 at 12:05
  • $\begingroup$ Yes, true. So in general, the statement norm is a convex function is wrong. $\endgroup$ – Shew Mar 20 '17 at 12:08
  • 1
    $\begingroup$ Can you paste the exact error message you're getting? $\endgroup$ – littleO Mar 20 '17 at 12:36
2
$\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$
0
$\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$
  • $\begingroup$ minimize for Q, right ?. Then which P matrix I should use ? $\endgroup$ – Shew Mar 20 '17 at 16:51
  • $\begingroup$ 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. $\endgroup$ – Rodrigo de Azevedo Mar 20 '17 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.