Finding a feasible point under quadratic constraints

Lets say we have a Quadratically Constrained Quadratic Program which we would like to optimize. The first step for many methods requires one to first find a point in the feasible region.

How can I answer the question "Is the feasible region non-empty?" If the answer is yes, I would like a witness obviously. I'm assuming this is possible in polynomial time if the problem is convex?

-
I noticed a possible problem. The specific problem I was thinking of turned out not to be convex(my mistake), and the feasible set always would have had an empty interior. Both of those things seem to make it not possible in polynomial time. But I still would be interested in an answer to this question. – Tim Seguine Sep 28 '11 at 19:17

For feasibility, only the constraints matter, not the objective. One way to identify a feasible point (even if there exist no strictly feasible point), is to solve the feasibility problem $$\min \ 0 \quad \text{subject to your constraints}.$$ Usually, this is not a much better-behaved problem than the original problem. An alternative is to minimize the infeasibility residual $$\min \ \|\text{constraints}\|^2$$ (assuming equality constraints). This is typically a nonlinear least-squares problem. Depending on the form of your constraints it can be solved more or less efficiently. If your original problem was feasible, this last one is a zero-residual least-squares problem and Gauss-Newton should converge quadratically.
This looks pretty helpful, but considering my comment on my original post: Can this work efficiently even if the feasible set is not convex? The problem is this: satisfy a linear equation system in n dimensions(possibly overdetermined) with the extra constraint that the solutions lie on a hypersphere of radius $\sqrt{n}$. – Tim Seguine Nov 13 '11 at 15:04
@Tim Just to add to my previous comment, if your quadratic constraint were to stay within a hypersphere, then this constraint could be written $\|x\|_M^2 \leq r^2$ for some $r > 0$ and you could use the truncated conjugate gradient method (assuming your objective is convex). See jstor.org/pss/2157277 I hope this helps. – Dominique Dec 7 '11 at 13:50