1
$\begingroup$

I have a covariance matrix C. I have then formulated an quadratic optimization problem that involves the following matrix in the quadratic form:

[ C C ]
[ C C ]

However, the quadratic solver complains that this matrix is not positive definite. I can also reformulate the optimization problem so that it uses the following matrix in quadratic form:

[ C -C ]
[-C  C ]

This matrix is also not positive definite. Now, I know that the problem I am trying to solve might not be possible to set up for quadratic optimization. However, I was wondering if maybe someone encountered a similar setup before, and can give me any hints? Maybe reformulate the problem? Or do some approximation? Make the matrix positive definite somehow? I know, now very clear, but I don't know what else I could add. Thank you!

$\endgroup$
  • $\begingroup$ I think it'd be clearer if you write the optimization problem. $\endgroup$ – Shamisen Mar 7 '14 at 18:05
  • 1
    $\begingroup$ @Shamisen min (a_T * x + 1/2 * x_T * M * x), where x <= 0, a - real valued vector, M = [ C, -C; -C, C ], and C is some covariance matrix (symmetric positive definite). $\endgroup$ – akuz Mar 7 '14 at 18:50
  • $\begingroup$ @MoritzFirsching The synonymization of qcqp and quadratic-programming - with quadratic-programming as the master tag - was recently suggested on meta. As far as I can tell, you are the creator of one of these two tags. So I wanted to let you know in case you have something to add to the discussion on meta. Feel free to ping me here or in chat to let me know that you've seen this message and I can remove it. $\endgroup$ – Martin Sleziak Mar 4 '19 at 17:48
3
$\begingroup$

If $C$ is positive semidefinite, then so is $\begin{bmatrix} C & C\\ C & C\end{bmatrix}$ for the simple reason that it is nothing but the Kronecker product of $\begin{bmatrix} 1 & 1\\ 1 & 1\end{bmatrix}$ with $C$.

EDIT

For those who don't like Kronecker products, here is an alternative proof using block-matrices:

Since $C>0$, we can write $C^{1/2}$. Then, we can write \begin{equation*} \begin{bmatrix} C & C\\ C & C\end{bmatrix} = \begin{bmatrix} C^{1/2} & 0\\ C^{1/2} & 0\end{bmatrix} \begin{bmatrix} C^{1/2} & C^{1/2}\\ 0 & 0\end{bmatrix}, \end{equation*} which is a Gram matrix, hence semidefinite.

$\endgroup$
  • $\begingroup$ Strange, then why is my optimization package complaining it's not either positive definite, nor positive semi-definite? Are you sure? (Sorry for this lame question!) $\endgroup$ – akuz Mar 7 '14 at 19:27
  • $\begingroup$ please see above comment. also, here it seems like there are additional conditions: math.stackexchange.com/questions/391852/… $\endgroup$ – akuz Mar 7 '14 at 19:41
  • 2
    $\begingroup$ @akuz: my answer addresses what you wrote in the question. I just proved the said matrix to be semidefinite but given your comment it seems that you are not convinced :-) please read the wikipedia page on Kronecker products to feel more convinced :-) $\endgroup$ – Suvrit Mar 7 '14 at 20:42
  • $\begingroup$ Thanks @Suvrit a lot for your answer. I will check the details, sorry I'm not too familiar with this subject. All I'm saying is that when I specify [ C C; C C ] matrix in my optimization routine (joptimizer), it complains it's not positive (semi-)definite. That might be a bug in their code too... $\endgroup$ – akuz Mar 8 '14 at 2:40
  • 2
    $\begingroup$ It's semidefinite, so it means there is an eigenvalue which is exactly zero. If your optimization routine computes a matrix factorization, it might be the case that numerical errors perturb an eigenvalue to $-10^{-16}$ or the like. It would be best if you reformulated the problem deflating manually out the zero subspace (which you can compute explicitly). $\endgroup$ – Federico Poloni Mar 8 '14 at 9:21

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