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

@article{8da6a8b3533740a68cdbd15476eaa2aa,
title = "Copositivity-based approximations for mixed-integer fractional quadratic optimization",
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.",
keywords = "copositive optimization, fractional quadratic optimization, mixed-integer polynomial optimization, POSITIVE CONE, SEMIDEFINITE, REPRESENTATION, COMPLEXITY, BINARY, GRAPH",
author = "Amaral, {Paula Alexandra} and Bomze, {Immanuel M.}",
note = "Sem PDF. This paper has been supported by Fundacao para a Ciencia e a Tecnologia (Portuguese Foundation for Science and Technology) through PEst-OE/MAT/UI0297/2014 (CMA).",
year = "2015",
month = "4",
language = "English",
volume = "11",
pages = "225--238",
journal = "Pacific Journal Of Optimization",
issn = "1348-9151",
publisher = "YOKOHAMA PUBL",
number = "2(SI)",

}

Copositivity-based approximations for mixed-integer fractional quadratic optimization. / Amaral, Paula Alexandra; Bomze, Immanuel M.

In: Pacific Journal Of Optimization, Vol. 11, No. 2(SI), 04.2015, p. 225-238.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Copositivity-based approximations for mixed-integer fractional quadratic optimization

AU - Amaral, Paula Alexandra

AU - Bomze, Immanuel M.

N1 - Sem PDF. This paper has been supported by Fundacao para a Ciencia e a Tecnologia (Portuguese Foundation for Science and Technology) through PEst-OE/MAT/UI0297/2014 (CMA).

PY - 2015/4

Y1 - 2015/4

N2 - 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.

AB - 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.

KW - copositive optimization

KW - fractional quadratic optimization

KW - mixed-integer polynomial optimization

KW - POSITIVE CONE

KW - SEMIDEFINITE

KW - REPRESENTATION

KW - COMPLEXITY

KW - BINARY

KW - GRAPH

M3 - Article

VL - 11

SP - 225

EP - 238

JO - Pacific Journal Of Optimization

JF - Pacific Journal Of Optimization

SN - 1348-9151

IS - 2(SI)

ER -