Are there any fast algorithms to determine if a linear matrix inequality (LMI) problem $Ax \leq b$ has a solution?
I am aware that linear programming and the simplex algorithm in particular may be used to solve linear optimization problems subject to LMI constraints ($\min(c^Tx) \text{ subject to: } Ax \leq b$) but I am curious if there are fast methods of proving that an LMI is solvable without necessarily finding a solution. For example, some criterion analogous to $\det(A) \neq 0$ for linear equality equations $Ax=b$.
Not meaningfully. Up until a logarithmic factor the algorithms must be the same speed.
To see why, we can append $c^T$ as a row to $A$, and $q$ to $b$. Then by solving whether $Ax \leq b$ you find whether $q$ is an achievable value for the minimization problem. Then you can try various $q$ in a binary search manner to approach the minimal value quickly.
This holds quite generally, usually. In a lot of cases in computer science the 'decision problem' (does a solution exist) is roughly as hard as the 'optimization problem' (find the optimal solution) because very often you can simply binary search for the optimal solution given a decider. This is also neat for computational complexity results however, since decision problems are easier to study but allow you to put bounds on the optimization problems we are often interested in.