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