Systems of quadratic equations: Efficient solution algorithms and conditions for solvability
- Creators
- Dvijotham, Krishnamurthy
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
- Eprint ID
- 66087
- DOI
- 10.1109/ALLERTON.2015.7447121
- Resolver ID
- CaltechAUTHORS:20160412-123332219
- Department of Energy (DOE)
- 11376437
- Defense Threat Reduction Agency (DTRA)
- Skotech
- Created
-
2016-04-12Created from EPrint's datestamp field
- Updated
-
2021-11-10Created from EPrint's last_modified field