# Convexity in a specific matrix optimization problem

I'm trying to figure out whether the following optimization problem is convex, but I haven't found the proper answer yet. I have not much experience in convex analysis so I hope I can get some insight from you. The following objective function arises from a practical data mining problem we are trying to solve.

The problem is the following: We want to find a matrix $F \in \mathbb{R}^{f\times q}$ that assigns objects from a set $\mathcal{Q}, q = |\mathcal{Q}|$ of sets of objects in $\mathcal{R}, r = |\mathcal{R}|$, where $R$ is a $r \times q$ binary matrix that represents which object is in which set in $\mathcal{Q}$. For a series of property that we need in our problem, we came up with the following objective

$$\arg\min_F \frac{1}{2}|| FR^T - J_{f,r}||_F^2 + \frac{1}{2}e^TFF^Te - tr(FF^T)$$

where $J$ is the matrix of ones and $e$ is the vector of ones.

There might be a more compact or convenient way to write such thing, so sorry if it is not the best way to present the problem. The matrix $F$ is ideally binary but the problems becomes NP-hard so we can relax it to be any non-negative real number.

Is the above optimization convex? Can it be optimized easily?

Thanks all for the help.

• Do you really want the matrix two-norm in this objective rather than the Frobenius norm? – Brian Borchers May 3 '17 at 12:41
• Sorry, that was a typo, I know corrected it. – Mutandon May 3 '17 at 12:59
• $R$ is assumed to be a thin matrix. – Mutandon May 3 '17 at 15:09

The quadratic part of the objective function to be minimized is

$$\frac 12 \,\mbox{tr} \left( \mathrm F \left( \mathrm R^{\top} \mathrm R - 2 \mathrm I_q \right) \mathrm F^{\top} \right) + \frac 12 \| \mathrm F^{\top} 1_f\|_2^2$$

Thus, a sufficient condition for convexity is

$$\mathrm R^{\top} \mathrm R \succ 2 \mathrm I_q$$

or, equivalently,

$$\lambda_{\min} (\mathrm R^{\top} \mathrm R) > 2$$

If this condition holds, then $\mathrm R^{\top} \mathrm R - 2 \mathrm I_q$ is positive definite and, thus, it has a factorization of the form $\rm M M^{\top}$, which allows us to write the objective function as follows

$$\frac 12 \,\mbox{tr} \left( \mathrm F \mathrm M \mathrm M^{\top} \mathrm F^{\top} \right) + \frac 12 \| \mathrm F^{\top} 1_f\|_2^2 = \frac 12 \| \mathrm F \mathrm M \|_{\text F}^2 + \frac 12 \| \mathrm F^{\top} 1_f\|_2^2$$

which is convex. This sufficient condition does not use $\| \mathrm F^{\top} 1_f\|_2^2$ and, thus, it may be too conservative.

Let us look for a better sufficient condition. Writing the objective function in vectorized form,

$$\frac 12 \, \mbox{tr} \left( \mathrm F \left( \mathrm R^{\top} \mathrm R - 2 \mathrm I_q \right) \mathrm F^{\top} \right) + \frac 12 \, \| \mathrm F^{\top} 1_f\|_2^2 = \\ = \frac 12 \, \mbox{vec}^{\top} (\mathrm F) \left( \color{blue}{\left( \left( \mathrm R^{\top} \mathrm R - 2 \mathrm I_q \right) \otimes \mathrm I_f \right) + \left( \mathrm I_q \otimes 1_f 1_f^{\top} \right)} \right) \mbox{vec} (\mathrm F)$$

A better sufficient condition for convexity is imposing that the Hessian be positive definite, i.e.,

$$\left( \left( \mathrm R^{\top} \mathrm R - 2 \mathrm I_q \right) \otimes \mathrm I_f \right) + \left( \mathrm I_q \otimes 1_f 1_f^{\top} \right) \succ \mathrm O_{f q}$$

which can be rewritten as follows

$$\boxed{\left( \mathrm R^{\top} \mathrm R \otimes \mathrm I_f \right) + \left( \mathrm I_q \otimes 1_f 1_f^{\top} \right) - 2 \mathrm I_{f q}\succ \mathrm O_{f q}}$$

• Thanks for the derivation and sorry for silly questions but I'm a bit puzzled now, since my linear algebra skills are not so advanced. First, if I got correctly you don't consider here the $-||F||_F^2$ term right? Second, the last condition looks to me pretty hard to interpret, so what is the actual property the matrix $R$ should possess in order to make that problem tractable? Unfortunately, I don't have many assumptions on that matrix apart that it is binary and every row represents (in a set-cover way) which items is contained in which set. – Mutandon May 4 '17 at 8:14
• @Mutandon I did consider the $-\| \rm F \|_{\text{F}}^2$ term, which is why there is a $- 2 \mathrm I_q$ in $$\mathrm R^{\top} \mathrm R - 2 \mathrm I_q$$ The last condition states that if the (symmetric) matrix $$\left( \mathrm R^{\top} \mathrm R \otimes \mathrm I_f \right) + \left( \mathrm I_q \otimes 1_f 1_f^{\top} \right) - 2 \mathrm I_{f q}$$ is positive definite, one can immediately conclude that the objective function is convex. Just use MATLAB to compute the Kronecker products and the eigenvalues. – Rodrigo de Azevedo May 4 '17 at 8:23
• @Mutandon The simpler, more conservative sufficient condition $$\mathrm R^{\top} \mathrm R \succ 2 \mathrm I_q$$ states that if the minimum eingenvalue of $\mathrm R^{\top} \mathrm R$ is greater than $2$, we can conclude that the objective is convex. If $\rm R$ is thin and does not have full column rank, we can immediately conclude that this sufficient condition is not satisfied. – Rodrigo de Azevedo May 4 '17 at 8:30
• Now I see, thanks a lot for your effort, this helps me a lot. Just as a final remark, if I removed the last term in the equation than the function would be convex, right? – Mutandon May 4 '17 at 8:38
• @Mutandon Yes, it would be convex because it would be the sum of two norms. – Rodrigo de Azevedo May 4 '17 at 8:40

No, I'm afraid that it's non-convex. The problem here is the last term $\mbox{tr}(FF^{T})=-\| F \|_{F}^{2}$ which is non-convex.

To make a specific counter example, let $F$ be 1 by 1 (a scalar), and let $R=0$. Then you've got

$\min \| 0-J \|_{F}^{2} + (1/2) F^{2} - F^{2}$

which is clearly non-convex. Of course, if $R=1$, then the problem would be convex.

In general, it's possible that additional constraints on $R$ could make the problem convex. The objective is quadratic in the elements of $F$, so you could try to work out the Hessian, and show that it's positive semidefinite, but this doesn't look easy.

• Your answer looks correct at first glance. – Brian Borchers May 3 '17 at 20:20