Novel shortcut strategies in copositivity detection: Decomposition for quicker positive certificates

Johannes Zischg and Immanuel Bomze

Operations Research Perspectives, 2025, vol. 14, issue C

Abstract: Copositivity is a property of symmetric matrices which is NP-hard to check. Nevertheless, it plays a crucial role in tight bounds for conic approaches of several hard optimization problems. In this paper, we present novel promising shortcut strategies to exploit favorable instances in a systematic way, using decomposition strategies based upon the idea to allow for overlapping, smaller blocks, profiting from a beneficial sign structure of the entries of the given matrix. The working hypothesis of this approach is the common empirical observation in the community that for detection of copositivity, a negative certificate is easier to obtain than a positive one. First empirical results on carefully orchestrated randomly generated instances seem to corroborate our approach.

Keywords: Nonconvex quadratic optimization; Copositive optimization; Decomposition (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S2214716024000289
Full text for ScienceDirect subscribers only

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:eee:oprepe:v:14:y:2025:i:c:s2214716024000289

DOI: 10.1016/j.orp.2024.100324

Access Statistics for this article

Operations Research Perspectives is currently edited by Rubén Ruiz Garcia

More articles in Operations Research Perspectives from Elsevier
Bibliographic data for series maintained by Catherine Liu ().