On the exactness of semidefinite relaxation for nonlinear optimization over graphs: Part II

This work is concerned with finding a global optimization technique for a broad class of nonlinear optimization problems, including quadratic and polynomial optimizations. The main objective of this two-part paper is to investigate how the (hidden) structure of a given real/complex-valued optimization makes the problem easy to solve. To this end, three conic relaxations are proposed and it is proved that some or all of these relaxations are exact if the optimization is highly structured. More precisely, the structure of the optimization is mapped into a generalized weighted graph, where each edge is associated with a weight set extracted from the coefficients of the optimization. In Part I of the paper, it is shown that the relaxations are all exact for general graphs in the real-valued case and for acyclic graphs in the complex-valued case, provided the weight sets satisfy some sign definiteness conditions. In this part of the paper, the complex-valued case is further studied, and three structural properties are derived for the generalized weighted graph, each of which guarantees the exactness of some of the proposed relaxations. It is also shown that this result holds true if the graph can be decomposed as a union of edge-disjoint subgraphs, where each subgraph has one of the derived structural properties. As an application of this paper, it is finally proved that a broad class of optimization problems for power networks are polynomial-time solvable due to the passivity of transmission lines and transformers.