EXACTNESS OF SEMIDEFINITE RELAXATIONS FOR NONLINEAR OPTIMIZATION PROBLEMS WITH UNDERLYING GRAPH STRUCTURE

This work is concerned with finding a global optimization technique for a broad class of nonlinear optimization problems, including quadratic and polynomial optimization problems. The main objective of this paper is to investigate how the (hidden) structure of a given real/complex-valued optimization problem makes it easy to solve. To this end, three conic relaxations are proposed. Necessary and sufficient conditions are derived for the exactness of each of these relaxations, and it is shown that these conditions are satisfied if the optimization problem is highly structured. More precisely, the structure of the optimization problem is mapped into a generalized weighted graph, where each edge is associated with a weight set extracted from the coefficients of the optimization problem. In the real-valued case, it is shown that the relaxations are all exact if each weight set is sign definite and in addition a condition is satisfied for each cycle of the graph. It is also proved that if some of these conditions are violated, the relaxations still provide a low-rank solution for weakly cyclic graphs. In the complex-valued case, the notion of sign definite complex sets is introduced for complex weight sets. It is then shown that the relaxations are exact if each weight set is sign definite (with respect to complex numbers) and the graph is acyclic. Three other structural properties are derived for the generalized weighted graph in the complex case, each of which guarantees the exactness of some of the proposed relaxations. This result is also generalized to graphs that can be decomposed as a union of edge-disjoint subgraphs, where each subgraph has certain structural properties. As an application, it is proved that a relatively large class of real and complex optimization problems over power networks are polynomial-time solvable (with an arbitrary accuracy) due to the passivity of transmission lines and transformers.