- Title
- Solving the canonical dual of box-and integer-constrained nonconvex quadratic programs via a deterministic direct search algorithm
- Creator
- Gao, David; Watson, Layne; Easterling, David; Thacker, William; Billups, Stephen
- Date
- 2013
- Type
- Text; Journal article
- Identifier
- http://researchonline.federation.edu.au/vital/access/HandleResolver/1959.17/62283
- Identifier
- vital:4844
- Identifier
-
https://doi.org/10.1080/10556788.2011.641125
- Identifier
- ISSN:1055-6788
- Abstract
- This paper presents a massively parallel global deterministic direct search method (VTDIRECT) for solving nonconvex quadratic minimization problems with either box or1 integer constraints. Using the canonical dual transformation, these well-known NP-hard problems can be reformulated as perfect dual stationary problems (with zero duality gap). Under certain conditions, these dual problems are equivalent to smooth concave maximization over a convex feasible space. Based on a perturbation method proposed by Gao, the integer programming problem is shown to be equivalent to a continuous unconstrained Lipschitzian global optimization problem. The parallel algorithm VTDIRECT is then applied to solve these dual problems to obtain global minimizers. Parallel performance results for several nonconvex quadratic integer programming problems are reported. © 2013 Copyright Taylor and Francis Group, LLC.
- Relation
- Optimization Methods and Software Vol. 28, no. 2 (2013), p. 313-326
- Rights
- Copyright 2013 Taylor and Francis Group, LLC.
- Rights
- This metadata is freely available under a CCO license
- Subject
- 0102 Applied Mathematics; 0103 Numerical and Computational Mathematics; 0802 Computation Theory and Mathematics; Algorithm VTDIRECT; Canonical duality theories; Direct search algorithm; Direct search methods; Dual problem; Dual transformation; Duality gap; Global minimizers; Global optimization problems; Integer constraints; Integer programming problems; Lipschitzian; Nonconvex quadratic minimization; Nonconvex quadratic programs; Parallel performance; Perturbation method; Quadratic integer programming; Stationary problem; Computational complexity; Global optimization; Problem solving
- Reviewed
- Hits: 6626
- Visitors: 6496
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|