Canonical Duality Theory for Global Optimization problems and applications
- Chen, Yi
- Authors: Chen, Yi
- Date: 2015
- Type: Text , Thesis , PhD
- Full Text:
- Description: The canonical duality theory is studied, through a discussion on a general global optimization problem and applications on fundamentally important problems. This general problem is a formulation of the minimization problem with inequality constraints, where the objective function and constraints are any convex or nonconvex functions satisfying certain decomposition conditions. It covers convex problems, mixed integer programming problems and many other nonlinear programming problems. The three main parts of the canonical duality theory are canonical dual transformation, complementary-dual principle and triality theory. The complementary-dual principle is further developed, which conventionally states that each critical point of the canonical dual problem is corresponding to a KKT point of the primal problem with their sharing the same function value. The new result emphasizes that there exists a one-to-one correspondence between KKT points of the dual problem and of the primal problem and each pair of the corresponding KKT points share the same function value, which implies that there is truly no duality gap between the canonical dual problem and the primal problem. The triality theory reveals insightful information about global and local solutions. It is shown that as long as the global optimality condition holds true, the primal problem is equivalent to a convex problem in the dual space, which can be solved efficiently by existing convex methods; even if the condition does not hold, the convex problem still provides a lower bound that is at least as good as that by the Lagrangian relaxation method. It is also shown that through examining the canonical dual problem, the hidden convexity of the primal problem is easily observable. The canonical duality theory is then applied to dealing with three fundamentally important problems. The first one is the spherically constrained quadratic problem, also referred to as the trust region subproblem. The canonical dual problem is onedimensional and it is proved that the primal problem, no matter with convex or nonconvex objective function, is equivalent to a convex problem in the dual space. Moreover, conditions are found which comprise the boundary that separates instances into “hard case” and “easy case”. A canonical primal-dual algorithm is developed, which is able to efficiently solve the problem, including the “hard case”, and can be used as a unified method for similar problems. The second one is the binary quadratic problem, a fundamental problem in discrete optimization. The discussion is focused on lower bounds and analytically solvable cases, which are obtained by analyzing the canonical dual problem with perturbation techniques. The third one is a general nonconvex problem with log-sum-exp functions and quartic polynomials. It arises widely in engineering science and it can be used to approximate nonsmooth optimization problems. The work shows that problems can still be efficiently solved, via the canonical duality approach, even if they are nonconvex and nonsmooth.
- Description: Doctor of Philosophy
- Authors: Chen, Yi
- Date: 2015
- Type: Text , Thesis , PhD
- Full Text:
- Description: The canonical duality theory is studied, through a discussion on a general global optimization problem and applications on fundamentally important problems. This general problem is a formulation of the minimization problem with inequality constraints, where the objective function and constraints are any convex or nonconvex functions satisfying certain decomposition conditions. It covers convex problems, mixed integer programming problems and many other nonlinear programming problems. The three main parts of the canonical duality theory are canonical dual transformation, complementary-dual principle and triality theory. The complementary-dual principle is further developed, which conventionally states that each critical point of the canonical dual problem is corresponding to a KKT point of the primal problem with their sharing the same function value. The new result emphasizes that there exists a one-to-one correspondence between KKT points of the dual problem and of the primal problem and each pair of the corresponding KKT points share the same function value, which implies that there is truly no duality gap between the canonical dual problem and the primal problem. The triality theory reveals insightful information about global and local solutions. It is shown that as long as the global optimality condition holds true, the primal problem is equivalent to a convex problem in the dual space, which can be solved efficiently by existing convex methods; even if the condition does not hold, the convex problem still provides a lower bound that is at least as good as that by the Lagrangian relaxation method. It is also shown that through examining the canonical dual problem, the hidden convexity of the primal problem is easily observable. The canonical duality theory is then applied to dealing with three fundamentally important problems. The first one is the spherically constrained quadratic problem, also referred to as the trust region subproblem. The canonical dual problem is onedimensional and it is proved that the primal problem, no matter with convex or nonconvex objective function, is equivalent to a convex problem in the dual space. Moreover, conditions are found which comprise the boundary that separates instances into “hard case” and “easy case”. A canonical primal-dual algorithm is developed, which is able to efficiently solve the problem, including the “hard case”, and can be used as a unified method for similar problems. The second one is the binary quadratic problem, a fundamental problem in discrete optimization. The discussion is focused on lower bounds and analytically solvable cases, which are obtained by analyzing the canonical dual problem with perturbation techniques. The third one is a general nonconvex problem with log-sum-exp functions and quartic polynomials. It arises widely in engineering science and it can be used to approximate nonsmooth optimization problems. The work shows that problems can still be efficiently solved, via the canonical duality approach, even if they are nonconvex and nonsmooth.
- Description: Doctor of Philosophy
Global solutions to nonconvex optimization of 4th-order polynomial and log-sum-exp functions
- Authors: Chen, Yi , Gao, David
- Date: 2016
- Type: Text , Journal article
- Relation: Journal of Global Optimization Vol. 64, no. 3 (2016), p. 417-431
- Full Text:
- Reviewed:
- Description: This paper presents a canonical dual approach for solving a nonconvex global optimization problem governed by a sum of 4th-order polynomial and a log-sum-exp function. Such a problem arises extensively in engineering and sciences. Based on the canonical duality–triality theory, this nonconvex problem is transformed to an equivalent dual problem, which can be solved easily under certain conditions. We proved that both global minimizer and the biggest local extrema of the primal problem can be obtained analytically from the canonical dual solutions. As two special cases, a quartic polynomial minimization and a minimax problem are discussed. Existence conditions are derived, which can be used to classify easy and relative hard instances. Applications are illustrated by several nonconvex and nonsmooth examples. © 2014, Springer Science+Business Media New York.
- Authors: Chen, Yi , Gao, David
- Date: 2016
- Type: Text , Journal article
- Relation: Journal of Global Optimization Vol. 64, no. 3 (2016), p. 417-431
- Full Text:
- Reviewed:
- Description: This paper presents a canonical dual approach for solving a nonconvex global optimization problem governed by a sum of 4th-order polynomial and a log-sum-exp function. Such a problem arises extensively in engineering and sciences. Based on the canonical duality–triality theory, this nonconvex problem is transformed to an equivalent dual problem, which can be solved easily under certain conditions. We proved that both global minimizer and the biggest local extrema of the primal problem can be obtained analytically from the canonical dual solutions. As two special cases, a quartic polynomial minimization and a minimax problem are discussed. Existence conditions are derived, which can be used to classify easy and relative hard instances. Applications are illustrated by several nonconvex and nonsmooth examples. © 2014, Springer Science+Business Media New York.
- «
- ‹
- 1
- ›
- »