Convexity in a specific matrix optimization problem

Question

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.

Answer 1

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

Answer 2

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.