Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published September 2015 | public
Book Section - Chapter

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

Abstract

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.

Additional Information

© 2015 IEEE. We acknowledge support from Los Alamos National Lab through an DoE grant, DTRA through grant 11376437 and Skotech. We thank Steven Low and Misha Chertkov for relevant discussions.

Additional details

Created:
August 20, 2023
Modified:
October 18, 2023