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.
Canonical primal-dual algorithm for solving fourth-order polynomial minimization problems
- Authors: Zhou, Xiaojun , Gao, David , Yang, Chunhua
- Date: 2014
- Type: Text , Journal article
- Relation: Applied Mathematics and Computation Vol. 227, no. (2014), p. 246-255
- Full Text: false
- Reviewed:
- Description: This paper focuses on implementation of a general canonical primal-dual algorithm for solving a class of fourth-order polynomial minimization problems. A critical issue in the canonical duality theory has been addressed, i.e., in the case that the canonical dual problem has no interior critical point in its feasible space Sa+, a quadratic perturbation method is introduced to recover the global solution through a primal-dual iterative approach, and a gradient-based method is further used to refine the solution. A series of test problems, including the benchmark polynomials and several instances of the sensor network localization problems, have been used to testify the effectiveness of the proposed algorithm. © 2013 Published by Elsevier Inc. All rights reserved.
Solving the canonical dual of box-and integer-constrained nonconvex quadratic programs via a deterministic direct search algorithm
- Authors: Gao, David , Watson, Layne , Easterling, David , Thacker, William , Billups, Stephen
- Date: 2013
- Type: Text , Journal article
- Relation: Optimization Methods and Software Vol. 28, no. 2 (2013), p. 313-326
- Full Text: false
- Reviewed:
- Description: This paper presents a massively parallel global deterministic direct search method (VTDIRECT) for solving nonconvex quadratic minimization problems with either box or1 integer constraints. Using the canonical dual transformation, these well-known NP-hard problems can be reformulated as perfect dual stationary problems (with zero duality gap). Under certain conditions, these dual problems are equivalent to smooth concave maximization over a convex feasible space. Based on a perturbation method proposed by Gao, the integer programming problem is shown to be equivalent to a continuous unconstrained Lipschitzian global optimization problem. The parallel algorithm VTDIRECT is then applied to solve these dual problems to obtain global minimizers. Parallel performance results for several nonconvex quadratic integer programming problems are reported. © 2013 Copyright Taylor and Francis Group, LLC.
- Description: 2003010580
Applying the canonical dual theory in optimal control problems
- Authors: Zhu, Jinghao , Wu, Dan , Gao, David
- Date: 2012
- Type: Text , Journal article
- Relation: Journal of global optimization Vol. 54, no. 2 (2012), p. 221-233
- Full Text: false
- Reviewed:
- Description: This paper presents some applications of the canonical dual theory in optimal control problems. The analytic solutions of several nonlinear and nonconvex problems are investigated by global optimizations. It turns out that the backward differential flow defined by the KKT equation may reach the globally optimal solution. The analytic solution to an optimal control problem is obtained via the expression of the co-state. Some examples are illustrated.
Global optimal solutions to a class of quadrinomial minimization problems with one quadratic constraint
- Authors: Yuan, Y. B. , Fang, Shucherng , Gao, David
- Date: 2012
- Type: Text , Journal article
- Relation: Journal of Global Optimization Vol. 52, no. 2 (2012), p. 195-209
- Full Text: false
- Reviewed:
- Description: This paper studies the canonical duality theory for solving a class of quadri- nomial minimization problems subject to one general quadratic constraint. It is shown that the nonconvex primal problem in Rn can be converted into a concave maximization dual problem over a convex set in R2 , such that the problem can be solved more efficiently. The existence and uniqueness theorems of global minimizers are provided using the triality theory. Examples are given to illustrate the results obtained. © 2011 Springer Science+Business Media, LLC.