- Title
- Global optimal solutions to nonconvex euclidean distance geometry problems
- Creator
- Ruan, Ning; Gao, David
- Date
- 2012
- Type
- Text; Conference paper
- Identifier
- http://researchonline.federation.edu.au/vital/access/HandleResolver/1959.17/161414
- Identifier
- vital:12492
- Abstract
- This paper presents a canonical dual approach for solving nonconvex minimization problems in Euclidean distance geometry. The variant of this problem arises extensively in engineering and science, including computational biology, sensor network communications, database analysis, information technology, and global optimization. Due to the nonconvexity, most of these problems are NP-hard and traditional convex optimization methods can not be used directly for finding global optimal solutions. We first show that this type of nonconvex problems can be transferred to a concave maximization problem over a convex set. Then a general analytical solution is proposed by using the canonical duality theory. Applications are illustrated by network localization and minimization of Rosenbrock function. Furthermore, by using a perturbed canonical dual approach, a class of Euclidean distance problems can be converted to a unified concave maximization dual problem with zero duality gap, which can be solved by well-developed convex minimization methods.
- Relation
- 20th International Symposium on Mathematical Theory of Networks and Systems
- Rights
- This metadata is freely available under a CCO license
- Subject
- 0805 Distributed Computing; Duality theory; Nonconvex programming; Global optimization; Database analysis; Canonical duality theory
- Reviewed
- Hits: 661
- Visitors: 620
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|