A new algorithm for concave quadratic programming

Research output: Contribution to journalArticleScientificpeer-review

Abstract

The main outcomes of the paper are divided into two parts. First, we present a new dual for quadratic programs, in which, the dual variables are affine functions, and we prove strong duality. Since the new dual is intractable, we consider a modified version by restricting the feasible set. This leads to a new bound for quadratic programs. We demonstrate that the dual of the bound is a semi-definite relaxation of quadratic programs. In addition, we probe the relationship between this bound and the well-known bounds in the literature. In the second part, thanks to the new bound, we propose a branch and cut algorithm for concave quadratic programs. We establish that the algorithm enjoys global convergence. The effectiveness of the method is illustrated for numerical problem instances.
Original languageEnglish
Pages (from-to)655-681
JournalJournal of Global Optimization
Volume75
DOIs
Publication statusPublished - Nov 2019
Externally publishedYes

Keywords

  • non-convex quadratic programming
  • duality
  • semi-definite relaxation
  • bound
  • branch and cut method
  • concave quadratic programming

Fingerprint

Dive into the research topics of 'A new algorithm for concave quadratic programming'. Together they form a unique fingerprint.

Cite this