1
$\begingroup$

I’m faced with the problem of maximizing a Rayleigh quotient:

$$\max_h \,\, \frac{h^t H h}{||h||^2}$$

Which is equivalent to solving

$$\max_h \,\, h^t H h $$ $$ s.t. ||h||^2=k >0, k \in \mathbb{R} $$

My matrix $H \in \mathbb{R}^{n \times n}$ is symmetric, but it is not positive semidefinite.

Now, the methods that I've seen for solving this sort of problem _assume_ that the matrix is symmetric and positive semidefinite (PSD). But, they seem to never use the PSD property anywhere. For example, consider the derivation given on the wikipedia page under the section "Special case of covariance matrices". Especially look at the section "Formulation using Lagrange multipliers". It seems to use the property that eigenvectors can be chosen to be orthogonal, but this is a property of symmetric matrices, and does not require PSDness.

So, I'm wondering - to maximize the Rayleigh quotient, must the matrix in the numerator be PSD? or is symmetric/Hermitian sufficient?

Related: Maximum of a generalized Rayleigh quotient

$\endgroup$
  • 1
    $\begingroup$ The problem of maximising the Rayleigh quotient for any matrix $H$ is well-defined, you do not need symmetric or positive-definite. If $H$ is symmetric, then there are nice results that the minimum and maximum coincide with the maximum and minimum eigenvalues of $H$. I can’t think of much you would need positive-definiteness for, unless you were going to divide by $x^t H x$, like in the question you linked. $\endgroup$ – Joppy Sep 24 '18 at 17:10
  • $\begingroup$ okay, so the method on the wikipedia page, used in solving the maximization problem needn't point out that the matrix is positive semidefinite? The question says "Being a positive semi-definite matrix, $M$ has non-negative eigenvalues, and orthogonal (or othogonalisable) eigenvectors, which can be demonstrated as follow" $\endgroup$ – Candic3 Sep 25 '18 at 6:07
  • 1
    $\begingroup$ The eigenvalues being positive is not important. The fact that all the eigenvalues are real and the matrix is diagonalisable is very important, and the matrix being symmetric guarantees this. $\endgroup$ – Joppy Sep 25 '18 at 7:24
  • $\begingroup$ okay, thanks got it! $\endgroup$ – Candic3 Sep 25 '18 at 14:22
1
$\begingroup$

You do not need to assume $H$ is positive semidefinite.

Maximizing $x^THx$ (over the unit sphere) is equivalent to maximizing $x^T(H+cI)x$, and you can choose $c$ so $H+cI$ is positive semidefinite.

$\endgroup$
  • $\begingroup$ I see. That's very good. But I'm wondering if the solution method of using Lagrange multipliers (that is, the maximizer corresponds to the eigenvector with the largest eigenvalue) is only true if $H$ is PSD, or can $H$ be symmetric. Related question - does saying that two optimization problems are equivalent mean that a solution to one gives a solution to the other? $\endgroup$ – Candic3 Sep 25 '18 at 6:27
  • 1
    $\begingroup$ @Candic3: equivalent means a solution to one is a solution to the other. (The values of the solutions do differ.) $\endgroup$ – Chris Godsil Sep 25 '18 at 11:48
  • $\begingroup$ Meaning, the minimizer is the same, okay got it. (however the value of the objective function might be different). $\endgroup$ – Candic3 Sep 25 '18 at 14:22

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.