A distributed algorithm for nonconvex quadratically constrained programs

This paper considers nonconvex quadratically constrained programs over undirected connected graphs. We focus on problems whose quadratic constraint forms have sparse hessians, i.e., each constraint only involves a small subset of variables. We present both centralized and distributed treatment of the problem, where the centralized method is used as a benchmark with which we compare the performance of the proposed distributed algorithm. Towards this objective, we derive a lower bound on the optimal value of the problem using a semidefinite relaxation. Then, we develop a decentralized algorithm based on proximal gradient ADMM that exploits the structure of the constraints to distribute the computations among the graph nodes. Indeed, the proposed algorithm does away with a central node. Each node updates its local variables via solving a simple subproblem, then communicate with its immediate neighbors. An application of this work is the AC optimal power flow problem in power networks for which we provide preliminary numerical results to validate our findings.