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

David Yang Gao, Ning Ruan, Panos M. Pardalos

Research output: Chapter in Book/Report/Conference proceedingChapter (Book)Researchpeer-review

12 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationSpringer Optimization and Its Applications
PublisherSpringer
Pages37-54
Number of pages18
DOIs
Publication statusPublished - 2012
Externally publishedYes

Publication series

NameSpringer Optimization and Its Applications
Volume61
ISSN (Print)1931-6828
ISSN (Electronic)1931-6836

Keywords

  • Canonical duality theory
  • Global optimization
  • Nonconvex programming
  • Nonlinear algebraic equations
  • Sensor network localization
  • Triality

Cite this