IST Lunch Bunch

In this talk, we consider an arbitrary real or complex-valued optimization problem whose variable is a positive semi-definite (PSD) matrix. The objective is to investigate under what conditions this optimization has a low-rank (e.g., rank 1 or 2) solution. The motivation is that a broad class of optimization problems, including polynomial optimization, can be cast as a rank-constrained matrix optimization.  To solve the problem, the structure of the optimization is mapped into a generalized weighted graph, where each edge is associated with a real/complex weight set. The notion of "sign definite real/complex set" is introduced, based on which we show that the existence of a low-rank solution can be related to the topology of the graph characterizing the optimization as well as the sign definiteness of its weight sets. As a by-product of this result, several classes of optimizations are shown to be polynomial-time solvable. In particular, when the underlying graph of the optimization is acyclic, bipartite or weakly cyclic, the optimization will not be NP-hard under mild conditions. As an application, we demonstrate that optimization over a power network can be mapped into a generalized weighted graph, where each weight set is naturally sign definite due to the physics of power systems. This result improves upon our previous result on zero duality gap for the optimal power flow problem, and can be readily applied to abstract optimizations (e.g. max cut) as well as optimization over other physical systems.