Global optimal solution to quadratic discrete programming problem with inequality constraints

Ning Ruan, David Yang Gao

Research output: Chapter in Book/Report/Conference proceedingChapter (Book)Researchpeer-review

Abstract

This paper presents a canonical dual method for solving a quadratic discrete value selection problem subjected to inequality constraints. By using a linear transformation, the problem is first reformulated as a standard quadratic 0–1 integer programming problem. Then, by the canonical duality theory, this challenging problem is converted to a concave maximization over a convex feasible set in continuous space. It is proved that if this canonical dual problem has a solution in its feasible space, the corresponding global solution to the primal problem can be obtained directly by a general analytical form. Otherwise, the problem could be NP-hard. In this case, a quadratic perturbation method and an associated canonical primal-dual algorithm are proposed. Numerical examples are illustrated to demonstrate the efficiency of the proposed method and algorithm.
Original languageEnglish
Title of host publicationCanonical Duality Theory
Subtitle of host publicationUnified Methodology for Multidisciplinary Study
Place of PublicationCham Switzerland
PublisherSpringer
Chapter16
Pages315-338
Number of pages24
Edition1st
ISBN (Electronic)9783319580173
ISBN (Print)9783319580166
DOIs
Publication statusPublished - 2017
Externally publishedYes

Publication series

NameAdvances in Mechanics and Mathematics
PublisherSpringer
Volume37
ISSN (Print)1571-8689
ISSN (Electronic)1876-9896

Keywords

  • Canonical Dual Problem
  • Canonical Duality
  • Concave Maximization
  • Canonical Perturbation Method
  • Nonconvex Analysis

Cite this