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.
An efficient classification using support vector machines
- 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 dual approach to solving the maximum cut problem
- 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.
Canonical dual solutions for fixed cost quadratic programs
- 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.
Canonical dual solutions to nonconvex radial basis neural network optimization problem
- Authors: Latorre, Vittorio , Gao, David
- Date: 2014
- Type: Text , Journal article
- Relation: Neurocomputing Vol. 134, no. Special issue (2014), p. 189-197
- Full Text: false
- Reviewed:
- Description: Radial Basis Functions Neural Networks (RBFNNs) are tools widely used in regression problems. One of their principal drawbacks is that the formulation corresponding to the training with the supervision of both the centers and the weights is a highly non-convex optimization problem, which leads to some fundamental difficulties for the traditional optimization theory and methods. This paper presents a generalized canonical duality theory for solving this challenging problem. We demonstrate that by using sequential canonical dual transformations, the nonconvex optimization problem of the RBFNN can be reformulated as a canonical dual problem (without duality gap). Both global optimal solution and local extrema can be classified. Several applications to one of the most used Radial Basis Functions, the Gaussian function, are illustrated. Our results show that even for a one-dimensional case, the global minimizer of the nonconvex problem may not be the best solution to the RBFNNs, and the canonical dual theory is a promising tool for solving general neural networks training problems. © 2014 Elsevier B.V.
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.
Canonical duality for radial basis neural networks
- Authors: Latorre, Vittorio , Gao, David
- Date: 2013
- Type: Text , Journal article
- Relation: Advances in Intelligent Systems and Computing Vol. 212, no. (2013), p. 1189-1197
- Full Text: false
- Reviewed:
- Description: Radial Basis Function Neural Networks (RBF NN) are a tool largely used for regression problems. The principal drawback of this kind of predictive tool is that the optimization problem solved to train the network can be non-convex. On the other hand Canonical Duality Theory offers a powerful procedure to reformulate general non-convex problems in dual forms so that it is possible to find optimal solutions and to get deep insights into the nature of the challenging problems. By combining the canonical duality theory with the RBF NN, this paper presents a potentially useful method for solving challenging problems in real-world applications. © Springer-Verlag Berlin Heidelberg 2013. Proceedings of the Eighth International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA), 2013.
- Description: 2003011221
Postbuckling analysis of a nonlinear beam with axial functionally graded material
- Authors: Cai, Kun , Gao, David , Qin, Qing
- Date: 2014
- Type: Text , Journal article
- Relation: Journal of Engineering Mathematics Vol. 88, no. 1 (2014/10/01 2014), p. 121-136
- Full Text: false
- Reviewed:
- Description: The postbuckling analysis of a modified nonlinear beam composed of axial functionally graded material (FGM) is investigated by a canonical dual finite element method (CD-FEM). The governing equation of the axial FGM nonlinear beam is derived through a variational method. The CD-FEM is adopted to find the nonconvex postbuckling configurations of the beam according to Gao’s triality theory. Using duality transition, the original potential energy functional becomes a functional of deformation and dual stress fields. By variation of the mixed complementary energy, the coupling equations are derived to find deformation and dual stress fields. In FEM, matrices of a beam element depend on the gradient of material property (elastic modulus). To obtain general forms of matrices of a beam element, the graded elastic modulus is approximated by piecewise linear functions with respect to axial position. Numerical examples are presented to show the effects of graded elasticity on the postbuckling configurations of the beam.
Canonical duality theory and triality for solving general global optimization problems in complex systems
- Authors: Morales-Silva, Daniel , Gao, David
- Date: 2015
- Type: Text , Journal article
- Relation: Mathematics and Mechanics of Complex Systems Vol. 3, no. 2 (2015), p. 139-161
- Full Text:
- Reviewed:
- Description: General nonconvex optimization problems are studied by using the canonical duality-triality theory. The triality theory is proved for sums of exponentials and quartic polynomials, which solved an open problem left in 2003. This theory can be used to find the global minimum and local extrema, which bridges a gap between global optimization and nonconvex mechanics. Detailed applications are illustrated by several examples. © 2015 Mathematical Sciences Publishers.
On D.C. optimization problems
- Authors: Gao, David
- Date: 2017
- Type: Text , Book chapter
- Relation: Canonical duality theory: Unified methodology for multidisciplinary study Chapter 10 p. 203-221
- Full Text: false
- Reviewed:
Canonical duality theory for solving nonconvex/discrete constrained global optimization problems
- Authors: Ruan, Ning , Gao, David
- Date: 2017
- Type: Text , Book chapter
- Relation: Canonical duality theory: Unified methodology for multidisciplinary study Chapter 9 p. 187-201
- Full Text: false
- Reviewed:
- Description: This paper presents a canonical duality theory for solving general nonconvex/discrete constrained minimization problems. By using the canonical dual transformation, these challenging problems can be reformulated as a unified canonical dual problem (i.e., with zero duality gap) in continuous space, which can be solved easily to obtain global optimal solution. Some basic concepts and general theory in canonical systems are reviewed. Applications to Boolean least squares problems are illustrated.
Canonical duality method for solving Kantorovich mass transfer problem
- Authors: Lu, Xiaojun , Gao, David
- Date: 2017
- Type: Text , Book chapter
- Relation: Canonical duality theory: Unified methodology for multidisciplinary study Chapter 5 p. 105-126
- Full Text: false
- Reviewed:
- Description: This paper addresses analytical solution to the Kantorovich mass transfer problem . Through an ingenious approximation mechanism, the Kantorovich problem is first reformulated as a variational form, which is equivalent to a nonlinear differential equation with Dirichlet boundary. The existence and uniqueness of the solution can be demonstrated by applying the canonical duality theory. Then, using the canonical dual transformation, a perfect dual maximization problem is obtained, which leads to an analytical solution to the primal problem . Its global extremality for both primal and dual problems can be identified by a triality theory. In addition, numerical maximizers for the Kantorovich problem are provided under different circumstances. Finally, the theoretical results are verified by applications to Monge’s problem. Although the problem is addressed in one-dimensional space, the theory and method can be generalized to solve high-dimensional problems.