3
$\begingroup$

A necessary condition in any quadratic programming to be convex is the matrix $\mathbf{Q}$ in the formulation $x^\intercal \mathbf{Q}x$ to be positive definite or positive semidefinite. Positive definiteness (PD) or semidefiniteness (PSD) requires the eigen values of the matrix either to be $> 0$ or $\geq 0$ respectively. Is the symmetry of the matrix $\mathbf{Q}$ a necessary condition for the matrix to be PD or PSD?

This link in Matlab documentations checks for the symmetry of the matrix before finding the eigen values. I can't find this information explicitly anywhere in any reference.

$\endgroup$
8
$\begingroup$

Yes, a real PSD matrix $M$ is a symmetric matrix with $$x^TMx\ge 0$$ for any $x$ (see e.g. https://en.wikipedia.org/wiki/Definite_matrix).

However, this is not a real restriction. (We have two meanings of "real" here). We can form $$M' = \frac{M+M^T}{2}$$ Now $M'$ is symmetric and we have $$x^TM'x = x^TMx$$ for any $x$. So you can make $M$ symmetric by preprocessing it without affecting the solution.

$\endgroup$
3
  • $\begingroup$ Thanks sir for this detailed answer. Consider this matrix: \begin{equation} \mathbf{Q} = \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ \end{bmatrix} \end{equation} Now if I apply the equation you kindly provided, the eigen values I get are (-0.5000, -0.5000, 0.5000, 0.5000) which turns the matrix to be indefinite, am I right? $\endgroup$ Jun 27 at 18:56
  • 2
    $\begingroup$ Yes, the "symmetrized" matrix is indefinite. $\endgroup$
    – prubin
    Jun 27 at 21:16
  • $\begingroup$ Thank you for your answer! $\endgroup$ Jun 28 at 1:59

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.