I've encountered a problem where I need to check many (approximately $10^4$-$10^5$) minimum trace solutions subject to two trace inequality constraints. I've written this problem as an SDP and my gut feeling is that the Dual problem might be the best way to approach it. Nevertheless, I am looking for advice on solving this problem as efficient as possible.
Some context: I'd like to check if there exists a solution a solution with:
$tr(X)<P\in\mathbb{R}_+$
subject to:
$tr(A_iX) = b_i$ for i=1,2 with $A_i\succeq0$, and $b_i>0$
$X\succeq0$
My solution was to solve the following SDP and check if the trace of the minimizer was less than $P$,
min $tr(X)$
subject to:
$tr(A_iX)=b_i$ for i=1,2
$X\succeq 0$
My current understanding is that the problem is guaranteed to have a solution when $A_1$ and $A_2$ are not multiples of each other. However, I am interested in obtaining the solution as fast as possible. To this end, I've formulated the dual problem
max $y_1b_1 + y_2b_2$
subject to:
$I-y_1A_1 - y_2A_2\succeq 0$
Because of the idendity matrix and the semi-positive definite matrices, $A_i$, the semi-positive definite constraint simplifies to $\bar{\lambda}(y_1A_1 + y_2A_2) \leq 1$ (where $\bar{\lambda}$ denotes the largest eigenvalue.)
Hence, I arrive at the following dual problem:
max $y_1b_1 + y_2b_2$
subject to:
$\bar{\lambda}(y_1A_1 + y_2A_2) \leq 1$
Again, this is a semi-definite program that I would like to solve even faster. As I assume there is no duality gap for my problem, it suffices to check if the optimal cost function value of the above Dual is lower or equal than $P$. Using this observation, I thought of a alternative problem to solve that might be easier:
min $\bar{\lambda}(y_1A_1 + y_2A_2)$
subject to:
$y_1b_1 + y_2b_2 = P$. (plus possibly non-negative constraints on $y_i$)
Here, the linear equality constraint forces the dual cost to equal $P$ while simultaneously finding the smallest maximum eigenvalue for the matrix sum. When this smallest maximum eigenvalue is smaller than 1, I can infer that the dual problem as an optimal cost larger than $P$.
The remaining question is, are any of these problems easy to solve and how? My gut feeling tells me that the constrained eigenvalue minimization should be doable, but I have no clue on how to actually do this.
Any tips, recommendations and alternative solutions are welcome :)