Based on the useful comments I reformulated my problem - hopefully it's more clear now.
Let $A,B \in \mathbb{R}^{d \times d}$ be symmetric positive-semidefinite matrices, $x \in \mathbb{R}^d$ and $||\cdot||^2$ the quadratic $l_2$-Norm.
Now I'm interested in those $x$, for which $||Ax||^2 \leq ||Bx||^2$. However, I'm not looking for the solution of this quadratic problem per se, but I need to characterize the set of $x$, for which $||Ax||^2 \leq ||Bx||^2$ holds, in terms of linear constraints, i.e. I'm looking for $G \in \mathbb{R}^{k\times d}$ and $b \in \mathbb{R}^k$, such that the set $$\lbrace x: G x \leq b \rbrace$$ is equal to or an approximation of the set $$\lbrace x: ||Ax||^2 \leq ||Bx||^2 \rbrace.$$ $k$ (the number of linear constraints / number of rows of $G$) may be arbitrary.
In geometrical terms (if I'm not mistaken), the solution of my initial problem is an intersection of ellipsoids, which I'm trying to characterize via a polyhedron.
Some additional information (not sure if these are helpful in any way):
- $Q := A^T A - B^T B$ is indefinite, but the trace of $Q$ is equal to zero (I tried to use this in combination with diagonalization of $A$ and $B$, which gives a quadratic inequality with a sum constraint for the eigenvalues - but how to procede from there?).
- $A^T A$ and $B^T B$ are not simultaneously diagonalizable
Any thoughts? Are there any established procedures for this kind of approximation?