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!

Improve this question
$\endgroup$
3
  • $\begingroup$ I think it'd be clearer if you write the optimization problem. $\endgroup$
    – Tadashi
    Commented Mar 7, 2014 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
    Commented Mar 7, 2014 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
    Commented Mar 4, 2019 at 17:48

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
12
  • $\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
    Commented Mar 7, 2014 at 19:27
  • $\begingroup$ please see above comment. also, here it seems like there are additional conditions: math.stackexchange.com/questions/391852/… $\endgroup$
    – akuz
    Commented Mar 7, 2014 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
    Commented Mar 7, 2014 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
    Commented Mar 8, 2014 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
    Commented Mar 8, 2014 at 9:21

Not the answer you're looking for? Browse other questions tagged .