Perfect duality theory and complete solutions to a class of global optimization problems*

*This article is dedicated to Professor Gilbert Strang on the occasion of his 70th birthday. The main results of this article has been presented at the International Conference on Nonsmooth/Nonconvex Mechanics, Aristotle University of Thessaloniki (A.U.Th.), July 5–6, 2002 (keynote lecture), and the Second International Conference on Optimization and Control with Applications, August 18–22, 2002, Yellow Mountains, Anhui, China (plenary lecture).

Abstract

This article presents a complete set of solutions for a class of global optimization problems. These problems are directly related to numericalization of a large class of semilinear nonconvex partial differential equations in nonconvex mechanics including phase transitions, chaotic dynamics, nonlinear field theory, and superconductivity. The method used is the so-called canonical dual transformation developed recently. It is shown that, by this method, these difficult nonconvex constrained primal problems in can be converted into a one-dimensional canonical dual problem, i.e. the perfect dual formulation with zero duality gap and without any perturbation. This dual criticality condition leads to an algebraic equation which can be solved completely. Therefore, a complete set of solutions to the primal problems is obtained. The extremality of these solutions are controlled by the triality theory discovered recently [D.Y. Gao (2000). Duality Principles in Nonconvex Systems: Theory, Methods and Applications, Vol. xviii, p. 454. Kluwer Academic Publishers, Dordrecht/Boston/London.]. Several examples are illustrated including the nonconvex constrained quadratic programming. Results show that these problems can be solved completely to obtain all KKT points and global minimizers.

Keywords:

• Duality
• Triality theory
• Global optimization
• Nonconvex variations
• Canonical dual transformation
• Nonconvex mechanics
• Critical point theory
• Semilinear equations
• NP-hard problems
• Quadratic programming
• Mathematics Subject Classifications 2000: 49N15
• 49M37
• 90C26
• 90C20

Acknowledgments

The author is sincerely grateful to Professor R. Greechie at Louisiana Tech University for his important comments and very valuable suggestions on the draft of this article, which will also affect to the style of the author's future publications.

Detailed remarks and important comments from Professor Alex Rubinov at Ballarat University, and from Professor C.J. Goh at University of Western Australia are highly appreciated, which improved definitely the quality of this article.

Notes

*This article is dedicated to Professor Gilbert Strang on the occasion of his 70th birthday. The main results of this article has been presented at the International Conference on Nonsmooth/Nonconvex Mechanics, Aristotle University of Thessaloniki (A.U.Th.), July 5–6, 2002 (keynote lecture), and the Second International Conference on Optimization and Control with Applications, August 18–22, 2002, Yellow Mountains, Anhui, China (plenary lecture).

¹Since the Hamiltonian H(x, y^*) = ⟨ Λ x ; y^* ⟩ − L(x, y^*) − F^*(Λ^* y^*)+ U^*(y^*) associated with the super Lagrangian L(x, y^*) is convex, this might be the reason that why most people prefer the convex Hamiltonian H(x, y^*) instead of the super-Lagrangian L(x, y^*) in dynamic systems.