How to find a positive semi-definite linear combination?

Question

Suppose we are given two explicit symmetric matrices $X$ and $Y$ and we'd like to find a non-zero real linear combination $aX+bY$ that is positive semi-definite (if possible).

Is there a way to go about this that is smarter than writing down all principal minors as a functions of a and b and seeing if you can make them simultaneously non-negative?

Answer 1

Charles Crawford, Algorithm 646: PDFIND: a routine to find a positive definite linear combination of two real symmetric matrices, ACM Transactions on Mathematical Software (TOMS), Volume 12, Issue 3, September 1986. Abstract:

PDFIND is a FORTRAN-77 implementation of an algorithm that finds a positive definite linear combination of two symmetric matrices, or determines that such a combination does not exist. The algorithm is designed to be independent of the data structures used to store the matrices. The user must provide a subroutine, CHLSKY, which acts as an interface between PDFIND and the matrix data structures. CHLSKY also provides the user control over the number of iterations of the algorithm. Implementations of CHLSKY are included which call LINPAC routines for full matrices as well as symmetric banded matrices.

C.R. Crawford and Y.S. Moon, Finding a positive definite linear combination of two Hermitian matrices, Linear Algebra and its Applications, Volume 51, June 1983. Abstract:

Let $A$ and $B$ be $n$-by-$n$ Hermitian matrices over the complex field. A result of Au-Yeung [1] and Stewart [8] states that if $x^*(A+iB)x\neq 0$ for all nonzero $n$-vectors $x$, then there is a linear combination of $A$ and $B$ which is positive definite. In this article we present an algorithm which finds such a linear combination in a finite number of steps. We also discuss the implementation of the algorithm in case $A$ and $B$ are real symmetric sparse matrices.

It looks like this second paper is available for free.