2
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mutandon May 4 '17 at 8:14
  • $\begingroup$ @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. $\endgroup$ – Rodrigo de Azevedo May 4 '17 at 8:23
  • $\begingroup$ @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. $\endgroup$ – Rodrigo de Azevedo May 4 '17 at 8:30
  • $\begingroup$ 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? $\endgroup$ – Mutandon May 4 '17 at 8:38
  • $\begingroup$ @Mutandon Yes, it would be convex because it would be the sum of two norms. $\endgroup$ – Rodrigo de Azevedo May 4 '17 at 8:40
1
$\begingroup$

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.

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

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.