Systems of quadratic equations: Efficient solution algorithms and conditions for solvability

We study multivariate systems of quadratic equations of the form F (x) = s where F : R^n → R^n and F_i a quadratic function of x for i = 1; : : : ; n. These types of equations arise across a variety of applications including sensor network localization, power systems and matrix factorization. In general, solving systems of quadratic equations is a challenging task, and in its most general form is NP-hard. In this paper, we approach this problem from a different perspective: We characterize domains over which the problem can be solved efficiently. For any such domain, we develop an efficient algorithm that terminates with: a) a solution in the domain, or b) a certificate of non-existence of the solution in the domain. Further, we derive conditions on s that guarantee the existence of a solution in the domain. We show how this result can be used to construct convex inner approximations to the feasible set of a Quadratically Constrained Quadratic Program (QCQP). Finally, we illustrate the results on simple examples from these application domains.