SOME STRONGLY POLYNOMIALLY SOLVABLE CONVEX QUADRATIC PROGRAMS WITH BOUNDED VARIABLES

Summary: In this paper, we study convex quadratic optimization problems with indicator variables and sparse matrix. By using a graphical representation of the support of the matrix, we prove that if the graph is a path, the associated problem can be solved in polynomial time. This allows us to construct a compact extended formulation for the closure of the convex hull of the mixed-integer convex problem's epigraph. Furthermore, we propose a novel decomposition method for a class of sparse strictly diagonally dominant matrices, inspired by inference problems with graphical models, leveraging the efficient algorithm for the path case. Our computational experiments demonstrate the effectiveness of the proposed method compared to state-of-the-art mixed-integer optimization solvers.