How to determine the existence of a solution to a system of homogenous quadratic inequalities and linear equalities?

Question

Let $M_1, \ldots, M_K$ be positive definite real symmetric matrices of dimension $n$. Let $R$ be an $m \times n$ matrix with $m < n$. Assume $R$ has full row rank. Fix $d\in\mathbb{R}^m$. Consider the system of inequalities/equalities for $x\in \mathbb{R}^n$: $$ x^T M_k x \leq 1, \quad (k=1,\ldots K) $$ $$ Rx=d $$ Is there an efficient algorithm to determine whether a solution exists?

Answer 1

This problem can be solved by convex optimization. Define $F(x) = \|Rx-d\|^2$ be the objective function, and let $\Phi:=\{x: x^T M_k x \leq 1, k=1,\ldots K\}$. Consider the problem $$ (P) \qquad \min_x F(x) : x\in \Phi $$ The existence of a solution to the original problem above is equivalent to $\min_x F(x)=0$. This is minimization of a convex function $F$ over a convex domain $\Phi$. Since also $\Phi$ is non-empty ($0\in\Phi$) we can initialize any convex optimizer at $x_0=0$ and compute the global minimum for $F$ to determine $\min F=0$.