Solutions to quadratic minimization problems with box and integer constraints

David Yang Gao, Ning Ruan

Research output: Contribution to journalArticleResearchpeer-review

36 Citations (Scopus)

Abstract

This paper presents a canonical duality theory for solving quadratic minimization problems subjected to either box or integer constraints. Results show that under Gao and Strang's general global optimality condition, these well-known nonconvex and discrete problems can be converted into smooth concave maximization dual problems over closed convex feasible spaces without duality gap, and can be solved by well-developed optimization methods. Both existence and uniqueness of these canonical dual solutions are presented. Based on a second-order canonical dual perturbation, the discrete integer programming problem is equivalent to a continuous unconstrained Lipschitzian optimization problem, which can be solved by certain deterministic technique. Particularly, an analytical solution is obtained under certain condition. A fourth-order canonical dual perturbation algorithm is presented and applications are illustrated. Finally, implication of the canonical duality theory for the popular semi-definite programming method is revealed.

Original languageEnglish
Pages (from-to)463-484
Number of pages22
JournalJournal of Global Optimization
Volume47
Issue number3
DOIs
Publication statusPublished - Jul 2010
Externally publishedYes

Keywords

  • Canonical duality theory
  • Global optimization
  • Integer programming
  • Np-hard problems
  • Quadratic programming

Cite this