- Title
- Canonical dual solutions for fixed cost quadratic programs
- Creator
- Gao, David; Ruan, Ning; Sherali, Hanif
- Date
- 2010
- Type
- Text; Book chapter
- Identifier
- http://researchonline.federation.edu.au/vital/access/HandleResolver/1959.17/54641
- Identifier
- vital:4365
- Identifier
- ISBN:1931-6828
- Abstract
- 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 R2n can be transformed into a continuous concave maximization dual problem over a convex feasible subset of R2n 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.
- Publisher
- Springer
- Relation
- Optimization and Optimal Control p. 139-156
- Rights
- This metadata is freely available under a CCO license
- Subject
- Canonical duality; Lagrangian duality; Global optimization; Mixed-integer programming; Fixed-charge objective function
- Reviewed
- Hits: 774
- Visitors: 732
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|