Copositivity-based approximations for mixed-integer fractional quadratic optimization

Paula Alexandra Amaral, Immanuel M. Bomze

Research output: Contribution to journalArticle

Abstract

We propose a copositive reformulation of the mixed-integer fractional quadratic problem (MIFQP) under general linear constraints. This problem class arises naturally in many applications, e.g., for optimizing communication or social networks, or studying game theory problems arising from genetics. It includes several APX-hard subclasses: the maximum cut problem, the k-densest subgraph problem and several of its variants, or the ternary fractional quadratic optimization problem (TFQP). Problems of this type arise when modelling density clustering problems with two voting options plus the possibility of an abstention, which is a criterion-based graph tri-partitioning problem. This paper adds to the rich evidence for the versatility of copositive optimization approaches, and hints at possible novel approximation strategies combining continuous and discrete optimization techniques in the domain of (fractional) polynomial Optimization.

Original languageEnglish
Pages (from-to)225-238
Number of pages14
JournalPacific Journal Of Optimization
Volume11
Issue number2(SI)
Publication statusPublished - Apr 2015

Keywords

  • copositive optimization
  • fractional quadratic optimization
  • mixed-integer polynomial optimization
  • POSITIVE CONE
  • SEMIDEFINITE
  • REPRESENTATION
  • COMPLEXITY
  • BINARY
  • GRAPH

Cite this