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

Antonio Frangioni (), Claudio Gentile () and James Hungerford ()
Additional contact information
Antonio Frangioni: Dipartimento di Informatica, Università di Pisa, 56127 Pisa, Italy;
Claudio Gentile: Istituto di Analisi dei Sistemi ed Informatica “Antonio Ruberti,” Consiglio Nazionale delle Ricerche, 00185 Rome, Italy;
James Hungerford: RaceTrac Petroleum, Inc., Atlanta, Georgia 30339

Mathematics of Operations Research, 2020, vol. 45, issue 1, 15–33

Abstract: We study the problem of decomposing the Hessian matrix of a mixed integer convex quadratic program (MICQP) 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 semicontinuous 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 semidefinite programming 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 with respect to 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 (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/moor.2018.0969 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:45:y:2020:i:1:p:15-33

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().