Global optimization for nonconvex optimization problems

Abstract

Duality is one of the most successful ideas in modern science [46] [91]. It is essential in natural phenomena, particularly, in physics and mathematics [39] [94] [96]. In this thesis, we consider the canonical duality theory for several classes of optimization problems.The first problem that we consider is 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.The second problem that we consider is a nonconvex quadratic-exponential optimization problem. By using the canonical duality theory, the nonconvex primal problem in n-dimensional space can be converted into a one-dimensional canonical dual problem, which is either a concave maximization or a convex minimization problem with zero duality gap. Several examples are solved so as to illustrate the applicability of the theory developed.The third problem that we consider is quadratic minimization problems subjected to either box or integer constraints. Results show that these nonconvex problems can be converted into concave maximization dual problems over convex feasible spaces without duality gap and the Boolean integer programming problem is actually equivalent to a critical point problem in continuous space. These dual problems can be solved under certain conditions. Both existence and uniqueness of the canonical dual solutions are presented. A canonical duality algorithm is presented and applications are illustrated.The fourth problem that we consider is a quadratic discrete value selection problem subjected to inequality constraints. The problem is first transformed into a quadratic 0-1 integer programming problem. The dual problem is thus constructed by using the canonical duality theory. Under appropriate conditions, this dual problem is a maximization problem of a concave function over a convex continuous space. Theoretical results show that the canonical duality theory can either provide a global optimization solution, or an optimal lower bound approximation to this NP-hard problem. Numerical simulation studies, including some relatively large scale problems, are carried out so as to demonstrate the effectiveness and efficiency of the canonical duality method. An open problem for understanding NP-hard problems is proposed.The fifth problem that we consider is a mixed-integer quadratic minimization problem with fixed cost terms. We show that this well-known NP-hard problem in R2n can be transformed into a continuous concave maximization dual problem over a convex feasible subset of Rn with zero duality gap. We also discuss connections between the proposed canonical duality theory approach and the classical Lagrangian duality approach. The resulting canonical dual problem can be solved under certain conditions, by traditional convex programming methods. Conditions for the existence and uniqueness of global optimal solutions are presented. An application to a decoupled mixed-integer problem is used to illustrate the derivation of analytic solutions for globally minimizing the objective function. Numerical examples for both decoupled and general mixed-integral problems are presented, and an open problem is proposed for future study.The sixth problem that we consider is a general nonconvex quadratic minimization problem with nonconvex constraints. By using the canonical dual transformation, the nonconvex primal problem can be converted into a canonical dual problem (i.e., either a concave maximization problem with zero duality gap). Illustrative applications to quadratic minimization with multiple quadratic constraints, box/integer constraints, and general nonconvex polynomial constraints are discussed, along with insightful connections to classical Lagrangian duality. Conditions for ensuring the existence and uniqueness of global optimal solutions are presented. Several numerical examples are solved.The seventh problem that we consider is a general nonlinear algebraic system. By using the least square method, the nonlinear system of m quadratic equations in n-dimensional space is first formulated as a nonconvex optimization problem. We then prove that, by using the canonical duality theory, this nonconvex problem is equivalent to a concave maximization problem in Rm, which can be solved by well-developed convex optimization techniques. Both existence and uniqueness of global optimal solutions are discussed, and several illustrative examples are presented.The eighth problem that we consider is a general sensor network localization problem. It is shown that by the canonical duality theory, this nonconvex minimization problem is equivalent to a concave maximization problem over a convex set in a symmetrical matrix space, and hence can be solved by combining a perturbation technique with existing optimization techniques. Applications are illustrated and results show that the proposed method is potentially a powerful one for large-scale sensor network localization problems.