Allerton 2015 Paper Abstract


Paper ThB3.5

Dvijotham, Krishnamurthy (California Institute of Technology)

Systems of Quadratic Equations: Efficient Solution Algorithms and Conditions for Solvability

Scheduled for presentation during the Regular Session "Optimization" (ThB3), Thursday, October 1, 2015, 11:50−12:10, Butternut

53rd Annual Allerton Conference on Communication, Control, and Computing, Sept 29-Oct 2, 2015, Allerton Park and Retreat Center, Monticello, IL, USA

This information is tentative and subject to change. Compiled on August 4, 2020

Keywords Optimization, Reliable and Robust Control, Cyber-Physical Systems


We study multivariate systems of quadratic equations of the formF (x)=s where F :Rn 􏰀→Rn and Fi 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 fac- torization. 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.



All Content © PaperCept, Inc..

This site is protected by copyright and trademark laws under US and International law.
All rights reserved. © 2002-2020 PaperCept, Inc.
Page generated 2020-08-04  07:49:04 PST  Terms of use