Your selections:

10Ruan, Ning
5Zhou, Xiaojun
3Chen, Yi
3Yang, Chunhua
3Zhu, Jinghao
2Fang, Shucherng
2Hanoun, Samer
2Latorre, Vittorio
2Li, Chaojie
2Nahavandi, Saeid
1Ali, Elaf
1Bhatti, Asim
1Billups, Stephen
1Easterling, David
1Jin, Zhong
1Khan, Burhan
1Morales-Silva, Daniel
1Pardalos, Panos
1Santos, Hugo

Show More

Show Less

140102 Applied Mathematics
130103 Numerical and Computational Mathematics
12Canonical duality theory
6Canonical duality theories
50802 Computation Theory and Mathematics
5Canonical duality
4Maximization problem
4Perturbation method
3Convex set
3Dual problem
3Duality theory
3Global minimizers
3Global optimal solutions
3Integer programming
3Optimization
3Problem solving
3Scheduling
3Set theory
3Triality

Show More

Show Less

Format Type

Advances in canonical duality theory with applications to global optimization

**Authors:**Gao, David**Date:**2008**Type:**Text , Conference proceedings**Relation:**FOCAPO 2008, Boston, June 29th-July 02, Published in Proceedings of the Fifth International Conference Foundations of Computer-Aided Process Operations pg. 73-82 p. 73-81**Full Text:**false**Reviewed:**

Global optimal solutions to nonconvex euclidean distance geometry problems

**Authors:**Ruan, Ning , Gao, David**Date:**2012**Type:**Text , Conference paper**Relation:**20th International Symposium on Mathematical Theory of Networks and Systems**Full Text:**false**Reviewed:****Description:**This paper presents a canonical dual approach for solving nonconvex minimization problems in Euclidean distance geometry. The variant of this problem arises extensively in engineering and science, including computational biology, sensor network communications, database analysis, information technology, and global optimization. Due to the nonconvexity, most of these problems are NP-hard and traditional convex optimization methods can not be used directly for finding global optimal solutions. We first show that this type of nonconvex problems can be transferred to a concave maximization problem over a convex set. Then a general analytical solution is proposed by using the canonical duality theory. Applications are illustrated by network localization and minimization of Rosenbrock function. Furthermore, by using a perturbed canonical dual approach, a class of Euclidean distance problems can be converted to a unified concave maximization dual problem with zero duality gap, which can be solved by well-developed convex minimization methods.

An efficient classification using support vector machines

- Ruan, Ning, Chen, Yi, Gao, David

**Authors:**Ruan, Ning , Chen, Yi , Gao, David**Date:**2013**Type:**Text , Conference paper**Relation:**Proceedings of 2013 Science and Information Conference, SAI 2013 p. 585-589**Full Text:**false**Reviewed:****Description:**Support vector machine (SVM) is a popular method for classification in data mining. The canonical duality theory provides a unified analytic solution to a wide range of discrete and continuous problems in global optimization. This paper presents a canonical duality approach for solving support vector machine problem. It is shown that by the canonical duality, these nonconvex and integer optimization problems are equivalent to a unified concave maximization problem over a convex set and hence can be solved efficiently by existing optimization techniques. © 2013 The Science and Information Organization.

Canonical primal-dual algorithm for solving fourth-order polynomial minimization problems

- Zhou, Xiaojun, Gao, David, Yang, Chunhua

**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.

Canonical dual solutions for fixed cost quadratic programs

- Gao, David, Ruan, Ning, Sherali, Hanif

**Authors:**Gao, David , Ruan, Ning , Sherali, Hanif**Date:**2010**Type:**Text , Book chapter**Relation:**Optimization and Optimal Control p. 139-156**Full Text:**false**Reviewed:****Description:**This chapter presents a canonical dual approach for solving 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 R2n with zero duality gap. The resulting canonical dual problem can be solved easily, under certain conditions, by traditional convex programming methods. Both existence and uniqueness of global optimal solutions are discussed. Application to a decoupled mixed-integer problem is illustrated and analytic solutions for both a global minimizer and a global maximizer are obtained. Examples for both decoupled and general nonconvex problems are presented. Furthermore, we discuss connections between the proposed canonical duality theory approach and the classical Lagrangian duality approach. An open problem is proposed for future study.

Complete solutions and triality theory to a nonconvex optimization problem with double-well potential in Rn

- Morales-Silva, Daniel, Gao, David

**Authors:**Morales-Silva, Daniel , Gao, David**Date:**2013**Type:**Text , Journal article**Relation:**Numerical Algebra, Control and Optimization Vol. 3, no. 2 (2013), p. 271-282**Full Text:****Reviewed:****Description:**The main purpose of this research note is to show that the triality theory can always be used to identify both global minimizer and the biggest local maximizer in global optimization. An open problem left on the double- min duality is solved for a nonconvex optimization problem with double-well potential in ℝn, which leads to a complete set of analytical solutions. Also a convergency theorem is proved for linear perturbation canonical dual method, which can be used for solving global optimization problems with multiple so- lutions. The methods and results presented in this note pave the way towards the proof of the triality theory in general cases.

**Authors:**Morales-Silva, Daniel , Gao, David**Date:**2013**Type:**Text , Journal article**Relation:**Numerical Algebra, Control and Optimization Vol. 3, no. 2 (2013), p. 271-282**Full Text:****Reviewed:****Description:**The main purpose of this research note is to show that the triality theory can always be used to identify both global minimizer and the biggest local maximizer in global optimization. An open problem left on the double- min duality is solved for a nonconvex optimization problem with double-well potential in ℝn, which leads to a complete set of analytical solutions. Also a convergency theorem is proved for linear perturbation canonical dual method, which can be used for solving global optimization problems with multiple so- lutions. The methods and results presented in this note pave the way towards the proof of the triality theory in general cases.

Global optimal trajectory in Chaos and NP-Hardness

- Latorre, Vittorio, Gao, David

**Authors:**Latorre, Vittorio , Gao, David**Date:**2016**Type:**Text , Journal article**Relation:**International Journal of Bifurcation and Chaos Vol. 26, no. 8 (2016), p. 1-14**Full Text:****Reviewed:****Description:**This paper presents an unconventional theory and method for solving general nonlinear dynamical systems. Instead of the direct iterative methods, the discretized nonlinear system is first formulated as a global optimization problem via the least squares method. A newly developed canonical duality theory shows that this nonconvex minimization problem can be solved deterministically in polynomial time if a global optimality condition is satisfied. The so-called pseudo-chaos produced by linear iterative methods are mainly due to the intrinsic numerical error accumulations. Otherwise, the global optimization problem could be NP-hard and the nonlinear system can be really chaotic. A conjecture is proposed, which reveals the connection between chaos in nonlinear dynamics and NP-hardness in computer science. The methodology and the conjecture are verified by applications to the well-known logistic equation, a forced memristive circuit and the Lorenz system. Computational results show that the canonical duality theory can be used to identify chaotic systems and to obtain realistic global optimal solutions in nonlinear dynamical systems. The method and results presented in this paper should bring some new insights into nonlinear dynamical systems and NP-hardness in computational complexity theory. © 2016 World Scientific Publishing Company.

**Authors:**Latorre, Vittorio , Gao, David**Date:**2016**Type:**Text , Journal article**Relation:**International Journal of Bifurcation and Chaos Vol. 26, no. 8 (2016), p. 1-14**Full Text:****Reviewed:****Description:**This paper presents an unconventional theory and method for solving general nonlinear dynamical systems. Instead of the direct iterative methods, the discretized nonlinear system is first formulated as a global optimization problem via the least squares method. A newly developed canonical duality theory shows that this nonconvex minimization problem can be solved deterministically in polynomial time if a global optimality condition is satisfied. The so-called pseudo-chaos produced by linear iterative methods are mainly due to the intrinsic numerical error accumulations. Otherwise, the global optimization problem could be NP-hard and the nonlinear system can be really chaotic. A conjecture is proposed, which reveals the connection between chaos in nonlinear dynamics and NP-hardness in computer science. The methodology and the conjecture are verified by applications to the well-known logistic equation, a forced memristive circuit and the Lorenz system. Computational results show that the canonical duality theory can be used to identify chaotic systems and to obtain realistic global optimal solutions in nonlinear dynamical systems. The method and results presented in this paper should bring some new insights into nonlinear dynamical systems and NP-hardness in computational complexity theory. © 2016 World Scientific Publishing Company.

A study on concave optimization via canonical dual function

- Zhu, Jinghao, Tao, Shiming, Gao, David

**Authors:**Zhu, Jinghao , Tao, Shiming , Gao, David**Date:**2009**Type:**Text , Journal article**Relation:**Elsevier Vol. 224, no. 2 (2009), p. 459-464**Full Text:**false**Reviewed:****Description:**In this study we find a global minimizer of a concave function over a sphere. By introducing a differential equation, we obtain the invariant characteristics for a given optimization problem by constructing a canonical dual function. We present two theorems concerning the global optimality of an extrema of the optimization problem.

On the triality theory for a quartic polynomial optimization problem

**Authors:**Gao, David , Wu, Changzhi**Date:**2012**Type:**Text , Journal article**Relation:**Journal of Industrial and Management Optimization Vol. 8, no. 1 (2012), p. 229-242**Full Text:**false**Reviewed:****Description:**This paper presents a detailed proof of the triality theorem for a class of fourth-order polynomial optimization problems. The method is based on linear algebra but it solves an open problem on the double-min duality. Results show that the triality theory holds strongly in the tri-duality form for our problem if the primal problem and its canonical dual have the same dimension; otherwise, both the canonical min-max duality and the double-max duality still hold strongly, but the double-min duality holds weakly in a symmetrical form. Some numerical examples are presented to illustrate that this theory can be used to identify not only the global minimum, but also the local minimum and local maximum.

Canonical dual approach to solving the maximum cut problem

- Wang, Zhenbo, Fang, Shucherng, Gao, David, Xing, Wenxun

**Authors:**Wang, Zhenbo , Fang, Shucherng , Gao, David , Xing, Wenxun**Date:**2012**Type:**Text , Journal article**Relation:**Journal of Global Optimization Vol. , no. (2012), p. 1-11**Full Text:**false**Reviewed:****Description:**This paper presents a canonical dual approach for finding either an optimal or approximate solution to the maximum cut problem (MAX CUT). We show that, by introducing a linear perturbation term to the objective function, the maximum cut problem is perturbed to have a dual problem which is a concave maximization problem over a convex feasible domain under certain conditions. Consequently, some global optimality conditions are derived for finding an optimal or approximate solution. A gradient decent algorithm is proposed for this purpose and computational examples are provided to illustrate the proposed approach. © 2012 Springer Science+Business Media, LLC.

**Authors:**Santos, Hugo , Gao, David**Date:**2012**Type:**Text , Journal article**Relation:**International Journal of Non-Linear Mechanics Vol. 47, no. 2 (2012), p. 240-247**Full Text:**false**Reviewed:****Description:**This paper presents a canonical dual mixed finite element method for the post-buckling analysis of planar beams with large elastic deformations. The mathematical beam model employed in the present work was introduced by Gao in 1996, and is governed by a fourth-order non-linear differential equation. The total potential energy associated with this model is a non-convex functional and can be used to study both the pre- and the post-buckling responses of the beams. Using the so-called canonical duality theory, this non-convex primal variational problem is transformed into a dual problem. In a proper feasible space, the dual variational problem corresponds to a globally concave maximization problem. A mixed finite element method involving both the transverse displacement field and the stress field as approximate element functions is derived from the dual variational problem and used to compute global optimal solutions. Numerical applications are illustrated by several problems with different boundary conditions. © 2011 Elsevier Ltd. All rights reserved.

- Yuan, Y. B., Fang, Shucherng, Gao, David

**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.

Global optimization over a box via canonical dual function

- Zhu, Jinghao, Wang, Chao, Gao, David

**Authors:**Zhu, Jinghao , Wang, Chao , Gao, David**Date:**2011**Type:**Text , Journal article**Relation:**Journal of Computational and Applied Mathematics Vol. 235, no. 5 (January 2011), p. 1141-1147**Full Text:**false**Reviewed:****Description:**In this paper, we study global concave optimization by the canonical dual function. A differential flow on the dual feasible space is introduced. We show that the flow reaches a global minimizer of the concave function over a box. An example is illustrated.

- Gao, David, Ruan, Ning, Pardalos, Panos

**Authors:**Gao, David , Ruan, Ning , Pardalos, Panos**Date:**2012**Type:**Text , Book chapter**Relation:**Sensors: Theory, Algorithms, and applications optimization and its applications p. 37-56**Full Text:**false**Reviewed:****Description:**This chapter presents a canonical dual approach for solving 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 developed by the first author. Both global and local extremality properties of this analytical solution are identified by a triality theory. Application to sensor network localization problem is illustrated. Our results show when the problem is not uniquely localizable, the “optimal solution” obtained by the SDP method is actually a local maximizer of the total potential energy. However, by using a perturbed canonical dual approach, a class of Euclidean distance problems can be converted to a unified concave maximization dual problem with zero duality gap, which can be solved by well-developed convex minimization methods. This chapter should bridge an existing gap between nonconvex mechanics and global optimization.

Canonical duality theory and algorithm for solving challenging problems in network optimisation

**Authors:**Ruan, Ning , Gao, David**Date:**2012**Type:**Text , Conference paper**Relation:**19th International Conference on Neural Information Processing, ICONIP 2012 Vol. 7665 LNCS, p. 702-709**Full Text:****Reviewed:****Description:**This paper presents a canonical dual approach for solving a general nonconvex problem in network optimization. Three challenging problems, sensor network location, traveling salesman problem, and scheduling problem are listed to illustrate the applications of the proposed method. It is shown that by the canonical duality, these nonconvex and integer optimization problems are equivalent to unified concave maximization problem over a convex set and hence can be solved efficiently by existing optimization techniques. © 2012 Springer-Verlag.**Description:**2003010653

**Authors:**Ruan, Ning , Gao, David**Date:**2012**Type:**Text , Conference paper**Relation:**19th International Conference on Neural Information Processing, ICONIP 2012 Vol. 7665 LNCS, p. 702-709**Full Text:****Reviewed:****Description:**This paper presents a canonical dual approach for solving a general nonconvex problem in network optimization. Three challenging problems, sensor network location, traveling salesman problem, and scheduling problem are listed to illustrate the applications of the proposed method. It is shown that by the canonical duality, these nonconvex and integer optimization problems are equivalent to unified concave maximization problem over a convex set and hence can be solved efficiently by existing optimization techniques. © 2012 Springer-Verlag.**Description:**2003010653

Global minimizer of large scale stochastic rosenbrock function : canonical duality approach

**Authors:**Li, Chaojie , Gao, David**Date:**2012**Type:**Text , Conference paper**Relation:**19th International Conference on Neural Information Processing, ICONIP 2012 Vol. 7666 LNCS, p. 677-682**Full Text:****Reviewed:****Description:**Canonical duality theory for solving the well-known benchmark test problem of stochastic Rosenbrock function is explored by two canonical transformations. Global optimality criterion is analytically obtained, which shows that the stochastic disturbance of these parameters could be eliminated by a proper canonical dual transformation. Numerical simulations illustrate the canonical duality theory is potentially powerful for solving this benchmark test problem and many other challenging problems in global optimization and complex network systems. © 2012 Springer-Verlag.**Description:**2003010651

**Authors:**Li, Chaojie , Gao, David**Date:**2012**Type:**Text , Conference paper**Relation:**19th International Conference on Neural Information Processing, ICONIP 2012 Vol. 7666 LNCS, p. 677-682**Full Text:****Reviewed:****Description:**Canonical duality theory for solving the well-known benchmark test problem of stochastic Rosenbrock function is explored by two canonical transformations. Global optimality criterion is analytically obtained, which shows that the stochastic disturbance of these parameters could be eliminated by a proper canonical dual transformation. Numerical simulations illustrate the canonical duality theory is potentially powerful for solving this benchmark test problem and many other challenging problems in global optimization and complex network systems. © 2012 Springer-Verlag.**Description:**2003010651

- Gao, David, Watson, Layne, Easterling, David, Thacker, William, Billups, Stephen

**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

On modeling and global solutions for d.c. optimization problems by canonical duality theory

**Authors:**Jin, Zhong , Gao, David**Date:**2017**Type:**Text , Journal article**Relation:**Applied Mathematics and Computation Vol. 296, no. (2017), p. 168-181**Full Text:****Reviewed:****Description:**This paper presents a canonical d.c. (difference of canonical and convex functions) programming problem, which can be used to model general global optimization problems in complex systems. It shows that by using the canonical duality theory, a large class of nonconvex minimization problems can be equivalently converted to a unified concave maximization problem over a convex domain, which can be solved easily under certain conditions. Additionally, a detailed proof for triality theory is provided, which can be used to identify local extremal solutions. Applications are illustrated and open problems are presented.**Description:**This paper presents a canonical d.c. (difference of canonical and convex functions) programming problem, which can be used to model general global optimization problems in complex systems. It shows that by using the canonical duality theory, a large class of nonconvex minimization problems can be equivalently converted to a unified concave maximization problem over a convex domain, which can be solved easily under certain conditions. Additionally, a detailed proof for triality theory is provided, which can be used to identify local extremal solutions. Applications are illustrated and open problems are presented. © 2016 Elsevier Inc.

**Authors:**Jin, Zhong , Gao, David**Date:**2017**Type:**Text , Journal article**Relation:**Applied Mathematics and Computation Vol. 296, no. (2017), p. 168-181**Full Text:****Reviewed:****Description:**This paper presents a canonical d.c. (difference of canonical and convex functions) programming problem, which can be used to model general global optimization problems in complex systems. It shows that by using the canonical duality theory, a large class of nonconvex minimization problems can be equivalently converted to a unified concave maximization problem over a convex domain, which can be solved easily under certain conditions. Additionally, a detailed proof for triality theory is provided, which can be used to identify local extremal solutions. Applications are illustrated and open problems are presented.**Description:**This paper presents a canonical d.c. (difference of canonical and convex functions) programming problem, which can be used to model general global optimization problems in complex systems. It shows that by using the canonical duality theory, a large class of nonconvex minimization problems can be equivalently converted to a unified concave maximization problem over a convex domain, which can be solved easily under certain conditions. Additionally, a detailed proof for triality theory is provided, which can be used to identify local extremal solutions. Applications are illustrated and open problems are presented. © 2016 Elsevier Inc.

Model modification in scheduling of batch chemical processes

- Zhou, Xiaojun, Gao, David, Yang, Chunhua

**Authors:**Zhou, Xiaojun , Gao, David , Yang, Chunhua**Date:**2015**Type:**Text , Conference paper**Relation:**3rd World Congress on Global Optimization in Engineering and Science, WCGO 2013; Anhui, China; 8th-12th July 2013 Vol. 95, p. 89-97**Full Text:**false**Reviewed:****Description:**This paper addresses the model modification in scheduling of batch chemical processes, which is widely used in current literatures. In the modified model, the capacity, storage constraints are modified and the allocation, sequence constraints are simplified. It is shown that the modified model can lead to fewer decision variables, fewer constraints, resulting in low computational complexity. Experimental results with two classical examples are given to demonstrate the effectiveness of the proposed formulation and approach. © Springer International Publishing Switzerland 2015.

Application of canonical duality theory to fixed point problem

**Authors:**Ruan, Ning , Gao, David**Date:**2015**Type:**Text , Conference paper**Relation:**3rd World Congress on Global Optimization in Engineering and Science, WCGO 2013; Anhui, China; 8th-12th July 2013 Vol. 95, p. 157-163**Full Text:**false**Reviewed:****Description:**In this paper, we study general fixed point problem. We first rewrite the original problem in the canonical framework. Then, we proposed a canonical transformation of this problem, which leads to a convex differentiable dual problem and new iteration method. An illustrative example is presented. © Springer International Publishing Switzerland 2015.

Are you sure you would like to clear your session, including search history and login status?