Global optimization for nonconvex optimization problems
Access Status
Authors
Date
2012Supervisor
Collection
Type
Education Level
Metadata
Show full item recordAbstract
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 fourthorder 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 quadraticexponential optimization problem. By using the canonical duality theory, the nonconvex primal problem in ndimensional space can be converted into a onedimensional 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 01 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 NPhard 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 NPhard problems is proposed.The fifth problem that we consider is a mixedinteger quadratic minimization problem with fixed cost terms. We show that this wellknown NPhard 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 mixedinteger problem is used to illustrate the derivation of analytic solutions for globally minimizing the objective function. Numerical examples for both decoupled and general mixedintegral 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 ndimensional 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 welldeveloped 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 largescale sensor network localization problems.
Department
Related items
Showing items related by title, author, creator and subject.

Tseng, Chien H. (1999)The design of envelopeconstrained (EC) filters is considered for the timedomain synthesis of filters for signal processing problems. The objective is to achieve minimal noise enhancement where the shape of the filter ...

Li, Bin (2011)In this thesis, we consider several types of optimal control problems with constraints on the state and control variables. These problems have many engineering applications. Our aim is to develop efficient numerical methods ...

Mardaneh, Elham (2010)Many industries are beginning to use innovative pricing techniques to improve inventory control, capacity utilisation, and ultimately the profit of the firm. In manufacturing, the coordination of pricing and production ...