Canonical Dual Algorithms for Global Optimization with Applications
- Authors: Zhou, Xiaojun
- Date: 2014
- Type: Text , Thesis
- Full Text:
- Description: Canonical duality theory provides a unified framework which can transform a nonconvex primal minimization problem to a canonical dual maximization problem over a convex domain without duality gap. But the global optimality is guaranteed by a certain positive definite condition and such condition is not always satisfied. The goal of this thesis aims to explore possible techniques that can be used to solve global optimization problems based on the canonical duality theory. Firstly, an algorithmic framework for canonical duality theory is established, which shows that the canonical dual algorithms can be developed in four aspects under the positive definite condition explicitly or implicitly, namely, (i) minimizing the primal problem, (ii) maximizing the canonical dual problem, (iii) solving a nonlinear equation caused by total complementary function, and (iv) solving a nonlinear equation caused by canonical dual function. Secondly, we show that if there exists a critical point of the canonical dual problem in the positive definite domain, by solving an equivalent semidefinite programming (SDP) problem, the corresponding global solution to the primal problem can be obtained easily via off-the-shelf software packages. A specific canonical dual algorithm is given for each problem, including sum of fourth-order polynomials minimization, nonconvex quadratically constrained quadratic program (QCQP), and boolean quadratic program (BQP). Thirdly, we propose a canonical primal-dual algorithm framework based on the total complementary function. Convergence analysis is discussed from the perspective of variational inequalities (VIs) and contraction methods. Specific canonical primal-dual algorithms for sum of fourth-order polynomials minimization is given as well. And a real-world application to the sensor network localization problem is illustrated. Next, a canonical sequential reduction approach is proposed to recover the approximate or global solution for the BQP problem. By fixing some previously known components, the original problem can be reduced sequentially to a lower dimension one. This approach is successfully applied to the well-known maxcut problem. Finally, we discuss the canonical dual approach applied to continuous time constrained optimal control. And it shows that the optimal control law for the n-dimensional constrained linear quadratic regulator can be achieved precisely via one-dimensional canonical dual variable, and for the optimal control problem with concave cost functional, an approximate solution can be obtained by introducing a linear perturbation term.
- Description: PhD
State transition algorithm for constrained optimization problems
- Authors: Han, Jie , Dong, Tianxue , Zhou, Xiaojun , Yang, Chunhua , Gui, Weihua
- Date: 2014
- Type: Text , Conference proceedings
- Full Text: false
- Description: In this study, a population-based continuous state transition algorithm (STA) is investigated into continuous constrained optimization problems. After an analysis of the advantages and disadvantages of two well-known constraint-handling techniques, penalty function method and feasibility preference method, a two-stage strategy is proposed for constrained STA, in which, the feasibility preference method is adopted in the early stage of an iteration process whilst it is changed to the penalty function method in the later stage. Several benchmark tests are given to evaluate the performance of the proposed method, and the experimental results show that the constrained STA with a two-stage strategy outperforms other single strategy in terms of both global search ability and solution precision.
A comparative study of state transition algorithm with harmony search and artificial bee colony
- Authors: Zhou, Xiaojun , Gao, David , Yang, Chunhua
- Date: 2013
- Type: Text , Journal article
- Relation: Advances in Intelligent Systems and Computing Vol. 212, no. (2013), p. 651-659
- Full Text: false
- Reviewed:
- Description: We focus on a comparative study of three recently developed nature-inspired optimization algorithms, including state transition algorithm, harmony search and artificial bee colony. Their core mechanisms are introduced and their similarities and differences are described. Then, a suit of 27 well-known benchmark problems are used to investigate the performance of these algorithms and finally we discuss their general applicability with respect to the structure of optimization problems. © Springer-Verlag Berlin Heidelberg 2013.
- Description: 2003011220
State transition algorithm for traveling salesman problem
- Authors: Yang, Chunhua , Tang, Xiaolin , Zhou, Xiaojun , Gui, Weihua
- Date: 2012
- Type: Text , Conference proceedings
- Full Text:
- Description: Discrete version of state transition algorithm is proposed in order to solve the traveling salesman problem. Three special operators for discrete optimization problem named swap, shift and symmetry transformations are presented. Convergence analysis and time complexity of the algorithm are also considered. To make the algorithm simple and efficient, no parameter adjusting is suggested in current version. Experiments are carried out to test the performance of the strategy, and comparisons with simulated annealing and ant colony optimization have demonstrated the effectiveness of the proposed algorithm. The results also show that the discrete state transition algorithm consumes much less time and has better search ability than its counterparts, which indicates that state transition algorithm is with strong adaptability. © 2012 Chinese Assoc of Automati.
A discrete state transition algorithm for traveling salesman problem
- Authors: Yang, Chunhua , Tang, Xiaolin , Zhou, Xiaojun , Gui, Weihua
- Date: 2013
- Type: Text , Journal article
- Relation: Kongzhi Lilun Yu Yingyong/Control Theory and Applications Vol. 30, no. 8 (2013), p. 1040-1046
- Full Text: false
- Reviewed:
- Description: A discrete version of state transition algorithm is proposed to solve the traveling salesman problem. Three special operators named swap, shift and symmetry transformations are presented for discrete optimization problem. Convergence analysis and time complexity of the algorithm are also considered. To make the algorithm efficient, a parametric study is investigated. Experiments are carried out to test its performance, and comparisons with simulated annealing and ant colony optimization have demonstrated the effectiveness of the proposed algorithm. The results also show that the discrete state transition algorithm consumes much less time and has better search ability than other traditional combinatorial optimization methods, indicating that state transition algorithm has strong adaptability.
- Description: C1
Optimal design of water distribution networks by a discrete state transition algorithm
- Authors: Zhou, Xiaojun , Gao, David , Simpson, Angus
- Date: 2016
- Type: Text , Journal article
- Relation: Engineering Optimization Vol. 48, no. 4 (2016), p. 603-628
- Full Text: false
- Reviewed:
- Description: In this study it is demonstrated that, with respect to model formulation, the number of linear and nonlinear equations involved in water distribution networks can be reduced to the number of closed simple loops. Regarding the optimization technique, a discrete state transition algorithm (STA) is introduced to solve several cases of water distribution networks. Firstly, the focus is on a parametric study of the 'restoration probability and risk probability' in the dynamic STA. To deal effectively with head pressure constraints, the influence is then investigated of the penalty coefficient and search enforcement on the performance of the algorithm. Based on the experience gained from training the Two-Loop network problem, a discrete STA has successfully achieved the best known solutions for the Hanoi, triple Hanoi and New York network problems. © 2015 Taylor & Francis.
A BMI approach to guaranteed cost control of discrete-time uncertain system with both state and input delays
- Authors: Zhou, Xiaojun , Dong, Tianxue , Tang, Xiaolin , Yang, Chunhua , Gui, Weihua
- Date: 2015
- Type: Text , Journal article
- Relation: Optimal Control Applications and Methods Vol. 36, no. 6 (2015), p. 844-852
- Full Text: false
- Reviewed:
- Description: In this study, the guaranteed cost control of discrete time uncertain system with both state and input delays is considered. Sufficient conditions for the existence of a memoryless state feedback guaranteed cost control law are given in the bilinear matrix inequality form, which needs much less auxiliary matrix variables and storage space. Furthermore, the design of guaranteed cost controller is reformulated as an optimization problem with a linear objective function, bilinear, and linear matrix inequalities constraints. A nonlinear semi-definite optimization solver - PENLAB is used as a solution technique. A numerical example is given to demonstrate the effectiveness of the proposed method. Copyright © 2014 John Wiley & Sons, Ltd.
Discrete state transition algorithm for unconstrained integer optimization problems
- Authors: Zhou, Xiaojun , Gao, David , Yang, Chunhua , Gui, Weihua
- Date: 2016
- Type: Text , Journal article
- Relation: Neurocomputing Vol. 173, no. (2016), p. 864-874
- Full Text:
- Reviewed:
- Description: A recently new intelligent optimization algorithm called discrete state transition algorithm is considered in this study, for solving unconstrained integer optimization problems. Firstly, some key elements for discrete state transition algorithm are summarized to guide its well development. Several intelligent operators are designed for local exploitation and global exploration. Then, a dynamic adjustment strategy "risk and restoration in probability" is proposed to capture global solutions with high probability. Finally, numerical experiments are carried out to test the performance of the proposed algorithm compared with other heuristics, and they show that the similar intelligent operators can be applied to ranging from traveling salesman problem, boolean integer programming, to discrete value selection problem, which indicates the adaptability and flexibility of the proposed intelligent elements. (C) 2015 Elsevier B.V. All rights reserved.
An improved simplex-based adaptive evolutionary digital filter and its application for fault detection of rolling element bearings
- Authors: Xiao, Huifang , Shao, Yimin , Zhou, Xiaojun , Wilcox, Steven
- Date: 2014
- Type: Text , Journal article
- Relation: Measurement: Journal of the International Measurement Confederation Vol. 55, no. (2014), p. 25-32
- Full Text: false
- Reviewed:
- Description: The de-noising performance and convergence behavior of the adaptive evolutionary digital filter (EDF) are restricted by the factors of constant evolutionary coefficients and taking the reciprocal of average energy of residual signal as the fitness function. In this paper, an improved adaptive evolutionary digital filter based on the simplex method (EDF-SM) is proposed to overcome the shortcomings of the original EDF. A new evolutionary rule was constructed by introducing the simplex-based mutating method and by then combining this with the original cloning and mating methods. The reciprocal of sample entropy was taken as the fitness function and variable evolutionary coefficients were employed. Numerical examples show that the proposed EDF-SM exhibits a higher convergence rate and a better de-noising behavior than the other EDFs. The effectiveness of the proposed method in discovering fault characteristics and detecting faults of rolling element bearings is supported using an experimental test. © 2014 Elsevier Ltd. All rights reserved.
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.
Model modification in scheduling of batch chemical processes
- 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.
A multiobjective state transition algorithm for single machine scheduling
- Authors: Zhou, Xiaojun , Hanoun, Samer , Gao, David , Nahavandi, Saeid
- 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. 79-88
- Full Text: false
- Reviewed:
- Description: In this paper, a discrete state transition algorithm is introduced to solve a multiobjective single machine job shop scheduling problem. In the proposed approach, a non-dominated sort technique is used to select the best from a candidate state set, and a Pareto archived strategy is adopted to keep all the non-dominated solutions. Compared with the enumeration and other heuristics, experimental results have demonstrated the effectiveness of the multiobjective state transition algorithm. © Springer International Publishing Switzerland 2015.
Stable trajectory of logistic map
- Authors: Li, Chaojie , Zhou, Xiaojun , Gao, David
- Date: 2014
- Type: Text , Journal article
- Relation: Nonlinear Dynamics Vol. 78, no. 1 (2014), p. 209-217
- Full Text: false
- Reviewed:
- Description: In this paper, the stable trajectory of Logistic Map has been investigated by canonical duality theory from the perspective of global optimization. Numerical result of our method shows that it totally differs from traditional chaotic solution solved by Euler method. In addition, we have applied our method to three well-known standard benchmarks in global optimization. Numerical simulations are given to illustrate the effectiveness of the main results.
Global solutions to a class of CEC benchmark constrained optimization problems
- Authors: Zhou, Xiaojun , Gao, David , Yang, Chunhua
- Date: 2016
- Type: Text , Journal article
- Relation: Optimization Letters Vol. 10, no. 3 (2016), p. 457-472
- Full Text:
- Reviewed:
- Description: This paper aims to solve a class of CEC benchmark constrained optimization problems that have been widely studied by nature-inspired optimization algorithms. Based on canonical duality theory, these challenging problems can be reformulated as a unified canonical dual problem over a convex set, which can be solved deterministically to obtain global optimal solutions in polynomial time. Applications are illustrated by some well-known CEC benchmark problems, and comparisons with other methods have demonstrated the effectiveness of the proposed approach. © 2014, Springer-Verlag Berlin Heidelberg.
A particle swarm optimization algorithm with variable random functions and mutation
- Authors: Zhou, Xiaojun , Yang, Chunhua , Gui, Weihua , Dong, Tianxue
- Date: 2014
- Type: Text , Journal article
- Relation: Zidonghua Xuebao/Acta Automatica Sinica Vol. 40, no. 7 (2014), p. 1339 - 1347
- Full Text: false
- Reviewed:
- Description: The convergence analysis of the standard particle swarm optimization (PSO) has shown that the changing of random functions, personal best and group best has the potential to improve the performance of the PSO. In this paper, a novel strategy with variable random functions and polynomial mutation is introduced into the PSO, which is called particle swarm optimization algorithm with variable random functions and mutation (PSO-RM). Random functions are adjusted with the density of the population so as to manipulate the weight of cognition part and social part. Mutation is executed on both personal best particle and group best particle to explore new areas. Experiment results have demonstrated the effectiveness of the strategy. Copyright © 2014 Acta Automatica Sinica. All rights reserved.