Title:Achieving SDP Tightness Through SOCP Relaxation with Cycle-Based SDP Feasibility Constraints for AC OPF

Abstract:In this paper, we show that the standard semidefinite programming (SDP) relaxation of altering current optimal power flow (AC OPF) can be equivalently reformulated as second-order cone programming (SOCP) relaxation with maximal clique- and cycle-based SDP feasibility constraints. The formulation is based on the positive semi-definite (PSD) matrix completion theorem, which states that if all sub-matrices corresponding to maximal cliques in a chordal graph are PSD, then the partial matrix related to the chordal graph can be completed as a full PSD matrix. Existing methods in [1] first construct a chordal graph through Cholesky factorization. In this paper, we identify maximal cliques and minimal chordless cycles first. Enforcing the submatrices related to the maximal cliques and cycles PSD will guarantee a PSD full matrix. Further, we conduct chordal relaxation for the minimal chordless cycles by adding virtual lines and decompose each chordless cycle to 3-node cycles. Thus, the entire graph consists of trees, maximal cliques, and 3-node cycles. The submatrices related to the maximal cliques and 3-node cycles are enforced to be PSD to achieve a full PSD matrix. As majority power grids having the size of maximal cliques limited to 4-node, this graph decomposition method results in a low-rank full PSD matrix. The proposed method significantly reduces computing time for SDP relaxation of AC OPF and can handle power systems with thousands of buses.