A new paper among MINOA Partners: University of Pisa, CNR-IASI, and MAIOR.

Abstract. We study the problem of decomposing the Hessian matrix of a Mixed-Integer Convex Quadratic Program into the sum of positive semidefinite 2×2 matrices. Solving this problem enables the use of Perspective Reformulation techniques for obtaining strong lower bounds for MICQPs with semi-continuous variables but a nonseparable objective function. An explicit formula is derived for constructing 2×2 decompositions when the underlying matrix is Weakly Scaled Diagonally Dominant, and necessary and sufficient conditions are given for the decomposition to be unique. For matrices lying outside this class, two exact SDP approaches and an efficient heuristic are developed for finding approximate decompositions. We present preliminary results on the bound strength of a 2×2 Perspective Reformulation for the Portfolio Optimization Problem, showing that for some classes of instances the use of 2×2 matrices can significantly improve the quality of the bound w.r.t. the best previously known approach, although at a possibly high computational cost.

Keywords. Mixed-Integer Quadratic Programming, Matrix Decomposition, Scaled Diagonal Dominance, Semicontinuous variables, Portfolio Optimization.

Cite as: A. Frangioni, C. Gentile, J. Hungerford, Decompositions of Semidefinite Matrices and the Perspective Reformulation of Nonseparable Quadratic Programs, Mathematics of Operations Research, to appear, 2018.