Decompositions of Semidefinite Matrices and the Perspective Reformulation of Nonseparable Quadratic Programs

We study the problem of (approximately) decomposing the hessian matrix of a Mixed-Integer Convex Quadratic Program with semicontinuous variables as the sum of positive semidefinite 2x2 matrices. Solving this problem can enable the use of Perspective Reformulation techniques for obtaining strong lower bounds for the MICQP. We discuss two exact SDP approaches for finding an approximate decomposition, we characterize the set of matrices that have an exact decomposition, and we use the characterization to devise efficient heuristics for obtaining 2x2 decompositions. We present preliminary results on the bound strength for Portfolio Optimization problems, showing that for some classes of problems the use of 2x2 matrices can significantly improve the quality of the bound w.r.t.~the best previously known approach, although at a possibly high computational cost.