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.
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.
Double well potential function and its optimization in the n-dimensional real space - Part I
- Authors: Fang, Shucherng , Gao, David , Lin, Gang-Xuan , Sheu, Ruey-Lin , Xing, Wenxun
- Date: 2017
- Type: Text , Journal article
- Relation: Journal of Industrial and Management Optimization Vol. 13, no. 3 (2017), p. 1291-1305
- Full Text: false
- Reviewed:
- Description: A special type of multi-variate polynomial of degree 4, called the double well potential function, is studied. It is derived from a discrete approx imation of the generalized Ginzburg-Landau functional, and we are interested in understanding its global minimum solution and all local non-global points. The main difficulty for the model is due to its non-convexity. In Part I of the paper, we first characterize the global minimum solution set, whereas the study for local non-global optimal solutions is left for Part II. We show that, the dual of the Lagrange dual of the double well potential problem is a linearly constrained convex minimization problem, which, under a designated nonlin ear transformation, can be equivalently mapped to a portion of the original double well potential function containing the global minimum. In other words, solving the global minimum of the double well potential function is essentially a convex minimization problem, despite of its non-convex nature. Numerical examples are provided to illustrate the important features of the problem and the mapping in between.
Double well potential function and its optimization in the N-dimensional real space -- Part I
- Authors: Fang, Shucherng , Gao, David , Lin, Gang-Xuan , Sheu, Ruey-Lin , Xing, Wenxun
- Date: 2017
- Type: Text , Journal article
- Relation: Journal of Industrial and Management Optimization Vol. 13, no. 3 (2017), p. 1291-1305
- Full Text: false
- Reviewed:
- Description: A special type of multi-variate polynomial of degree 4, called the double well potential function, is studied. It is derived from a discrete approximation of the generalized Ginzburg-Landau functional, and we are interested in understanding its global minimum solution and all local non-global points. The main difficulty for the model is due to its non-convexity. In Part I of the paper, we first characterize the global minimum solution set, whereas the study for local non-global optimal solutions is left for Part II. We show that, the dual of the Lagrange dual of the double well potential problem is a linearly constrained convex minimization problem, which, under a designated nonlinear transformation, can be equivalently mapped to a portion of the original double well potential function containing the global minimum. In other words, solving the global minimum of the double well potential function is essentially a convex minimization problem, despite of its non-convex nature. Numerical examples are provided to illustrate the important features of the problem and the mapping in between.