Optimization Online


Copositivity-based approximations for mixed-integer fractional quadratic optimization

Paula Alexandra Amaral (paca***at***fct.unl.pt)
Immanuel M. Bomze (immanuel.bomze***at***univie.ac.at)

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

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Nonlinear Optimization (Constrained Nonlinear Optimization )

Citation: Preprint NI14043-POP, Isaac Newton Institute for Mathematical Sciences, University of Cambridge UK, submitted

Download: [PDF]

Entry Submitted: 04/29/2014
Entry Accepted: 05/01/2014
Entry Last Modified: 11/18/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society