Canonical Dual Solutions for Fixed Cost Quadratic Programs

David Yang Gao (), Ning Ruan () and Hanif D. Sherali
Additional contact information
David Yang Gao: University of Ballarat
Ning Ruan: Virginia Tech
Hanif D. Sherali: Virginia Tech

A chapter in Optimization and Optimal Control, 2010, pp 139-156 from Springer

Abstract: Summary This chapter presents a canonical dual approach for solving a mixed-integer quadratic minimization problem with fixed cost terms. We show that this well-known NP-hard problem in $$\mathbb{R}^{2n}$$ can be transformed into a continuous concave maximization dual problem over a convex feasible subset of $$\mathbb{R}^{2n}$$ with zero duality gap. The resulting canonical dual problem can be solved easily, under certain conditions, by traditional convex programming methods. Both existence and uniqueness of global optimal solutions are discussed. Application to a decoupled mixed-integer problem is illustrated and analytic solutions for both a global minimizer and a global maximizer are obtained. Examples for both decoupled and general nonconvex problems are presented. Furthermore, we discuss connections between the proposed canonical duality theory approach and the classical Lagrangian duality approach. An open problem is proposed for future study.

Keywords: canonical duality; Lagrangian duality; global optimization; mixed-integer programming; fixed-charge objective function (search for similar items in EconPapers)
Date: 2010
References: Add references at CitEc
Citations: View citations in EconPapers (1)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-0-387-89496-6_7

Ordering information: This item can be ordered from
http://www.springer.com/9780387894966

DOI: 10.1007/978-0-387-89496-6_7

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().