TY - CHAP

T1 - Canonical dual solutions to sum of fourth-order polynomials minimization problems with applications to sensor network localization

AU - Gao, David Yang

AU - Ruan, Ning

AU - Pardalos, Panos M.

N1 - Funding Information:
The work of David Gao and N. Ruan was supported by National Sleep Foundation NSF grant CCF-0514768, US Air Force Air Force Office of Scientific Research (AFOSR) grants FA9550-09-1-0285 and Air Force Office of Scientific Research (AFOSR) grants FA9550-10-1-0487.
Publisher Copyright:
© Springer Science+Business Media, LLC 2012.
Copyright:
Copyright 2016 Elsevier B.V., All rights reserved.

PY - 2012

Y1 - 2012

N2 - This chapter presents a canonical dual approach for solving a general sum of fourth-order polynomial minimization problem. This problem arises extensively in engineering and science, including database analysis, computational biology, sensor network communications, nonconvex mechanics, and ecology. We first show that this global optimization problem is actually equivalent to a discretized minimal potential variational problem in large deformation mechanics. Therefore, a general analytical solution is proposed by using the canonical duality theory developed by the first author. Both global and local extremality properties of this analytical solution are identified by a triality theory. Application to sensor network localization problem is illustrated. Our results show when the problem is not uniquely localizable, the “optimal solution” obtained by the SDP method is actually a local maximizer of the total potential energy. However, 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 convexminimizationmethods. This chapter should bridge an existing gap between nonconvex mechanics and global optimization.

AB - This chapter presents a canonical dual approach for solving a general sum of fourth-order polynomial minimization problem. This problem arises extensively in engineering and science, including database analysis, computational biology, sensor network communications, nonconvex mechanics, and ecology. We first show that this global optimization problem is actually equivalent to a discretized minimal potential variational problem in large deformation mechanics. Therefore, a general analytical solution is proposed by using the canonical duality theory developed by the first author. Both global and local extremality properties of this analytical solution are identified by a triality theory. Application to sensor network localization problem is illustrated. Our results show when the problem is not uniquely localizable, the “optimal solution” obtained by the SDP method is actually a local maximizer of the total potential energy. However, 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 convexminimizationmethods. This chapter should bridge an existing gap between nonconvex mechanics and global optimization.

KW - Canonical duality theory

KW - Global optimization

KW - Nonconvex programming

KW - Nonlinear algebraic equations

KW - Sensor network localization

KW - Triality

UR - http://www.scopus.com/inward/record.url?scp=84976498148&partnerID=8YFLogxK

U2 - 10.1007/978-0-387-88619-0_3

DO - 10.1007/978-0-387-88619-0_3

M3 - Chapter (Book)

AN - SCOPUS:84976498148

T3 - Springer Optimization and Its Applications

SP - 37

EP - 54

BT - Springer Optimization and Its Applications

PB - Springer

ER -