On the positive definiteness of a linear combination of matrices

The following recent paper: "An exact duality theory for semidefinite programming based on sums of squares" by I. Klep, and M. Schweighofer (both are on MO I think) addresses exactly your question: When is there a $\lambda \in \mathbb{R}^m$ such that $\sum_i \lambda_iA_i \succeq 0$.

If you want something simpler, then the following Lemma, cf. L.Lovasz lecture notes, Lemma 3.2, might be of help (notice $\succ$ instead of $\succeq$).

Lemma. Let $A_i$ be real symmetric matrices. Then, the set $P_+ := \lbrace\sum_i \lambda_i A_i \succ 0\rbrace$ is empty if and only if there exists a semidefinite matrix $X \neq 0$, such that $\mbox{trace}(A_iX) = 0$ for all $i$.

Without the strict $\succ$ relation, the situation gets trickier (we don't have a perfect Farkas Lemma for SDPs).


A straightforward reformulation is in terms of polynomial inequalities is by taking $n$ consecutive chief submatrices $M_{KK}(\lambda)$ for $K=(1,\dots,k)$, $1\leq k\leq n$ of the matrix $M(\lambda)=\sum_{j=1}^m \lambda_j A_j\in \mathbb{R}[\lambda_1,\dots,\lambda_m]^{n\times n}$. Then $P$ contains a positive definite matrix if and only if the basic open semialgebraic set

$\{y\in \mathbb{R}^m\mid \det M_{KK}(y) \gt 0, \ K=(1,\dots,k), 1\leq k\leq n\}$ is nonempty.

At least these kinds of conditions were used in papers by L.Khachiyan and L.Porkolab, such as "On the complexity of semidefinite programs", J. Global Optim. 10 (1997). E.g. when $m$ is fixed, one gets a strong polynomial-time algorithm for checking non-emptiness of $P$.