Global Convergence Analysis of Non-Crossover Genetic Algorithm and Its Application to Optimization

Selection, crossover, and mutation are three main operators of the canonical genetic algorithm (CGA). This paper presents a new approach to the genetic algorithm. This new approach applies only to mutation and selection operators. The paper proves that the search process of the non-crossover genetic algorithm (NCGA) is an ergodic homogeneous Markov chain. The proof of its convergence to global optimum is presented. Some nonlinear multi-modal optimization problems are applied to test the efficacy of the NCGA. NP-hard traveling salesman problem (TSP) is cited here as the benchmark problem to test the efficiency of the algorithm. The simulation result shows that NCGA achieves much faster convergence speed than CGA in terms of CPU time. The convergence speed per epoch of NCGA is also faster than that of CGA.

Maneuvering Angle Rigid Formations With Global Convergence Guarantees

Angle rigid multi-agent formations can simultaneously undergo translational,rotational,and scaling maneuvering,therefore combining the maneuvering capabilities of both distance and bearing rigid formations.However,maneuvering angle rigid formations in 2D or 3D with global convergence guarantees is shown to be a challenging problem in the existing literature even when relative position measurements are available.Motivated by angle-induced linear equations in 2D triangles and 3D tetrahedra,this paper aims to solve this challenging problem in both 2D and3D under a leader-follower framework.For the 2D case where the leaders have constant velocities,by using local relative position and velocity measurements,a formation maneuvering law is designed for the followers governed by double-integrator dynamics.When the leaders have time-varying velocities,a sliding mode formation maneuvering law is proposed by using the same measurements.For the 3D case,to establish an angle-induced linear equation for each tetrahedron,we assume that all the followers'coordinate frames share a common Z direction.Then,a formation maneuvering law is proposed for the followers to globally maneuver Z-weakly angle rigid formations in 3D.The extension to Lagrangian agent dynamics and the construction of the desired rigid formations by using the minimum number of angle constraints are also discussed.Simulation examples are provided to validate the effectiveness of the proposed algorithms.

GLOBAL CONVERGENCE OF A TRUST REGION ALGORITHM USING INEXACT GRADIENT FOR EQUALITY-CONSTRAINED OPTIMIZATION

A trust-region algorithm is presented for a nonlinear optimization problem of equality-constraints. The characterization of the algorithm is using inexact gradient information. Global convergence results are demonstrated where the gradient values are obeyed a simple relative error condition.

Projection type neural network and its convergence analysis

Projection type neural network for optimization problems has advantages over other networks for fewer parameters , low searching space dimension and simple structure. In this paper, by properly constructing a Lyapunov energy function, we have proven the global convergence of this network when being used to optimize a continuously differentiable convex function defined on a closed convex set. The result settles the extensive applicability of the network. Several numerical examples are given to verify the efficiency of the network.

A GLOBALLY AND SUPERLINEARLY CONVERGENT TRUST REGION METHOD FOR LC^1 OPTIMIZATION PROBLEMS

A new trust region algorithm for solving convex LC 1 optimization problem is presented.It is proved that the algorithm is globally convergent and the rate of convergence is superlinear under some reasonable assumptions.

Stability,Convergence of Harmonious Particle Swarm Optimizer and Its Application

Particle swarm optimizer （PSO）, a new evolutionary computation algorithm, exhibits good performance for optimization problems, although PSO can not guarantee convergence of a global minimum, even a local minimum. However, there are some adjustable parameters and restrictive conditions which can affect performance of the algorithm. The sufficient conditions for asymptotic stability of an acceleration factor and inertia weight are deduced in this paper. The value of the inertia weight w is enhanced to （ - 1, 1）. Furthermore a new adaptive PSO algorithm--harmonious PSO （HPSO） is proposed and proved that HPSO is a global search algorithm. Finally it is focused on a design task of a servo system controller. Considering the existence of model uncertainty and noise from sensors, HPSO are applied to optimize the parameters of fuzzy PID controller. The experiment results demonstrate the efficiency of the methods.

A VARIATIONAL IMAGE SMOOTHING MODEL WITH GLOBAL CONVERGENCE

A new smoothing method is proposed. The smoothing process adapts to image characteristics and is good at preserving local image structures. More importantly, in the theory under the conditions weaker than those in the original Kaanov method an approximal sequence of solutions to the variational problems can be constructed and the global convergence can be proved. And the conditions in the papers of Schno¨rr(1994) and Heers, et al (2001) are discussed. Numerical solutions of the model are given.

A GLOBALLY CONVERGENT QP-FREE ALGORITHM FOR INEQUALITY CONSTRAINED MINIMAX OPTIMIZATION

Although QP-free algorithms have good theoretical convergence and are effective in practice,their applications to minimax optimization have not yet been investigated.In this article,on the basis of the stationary conditions,without the exponential smooth function or constrained smooth transformation,we propose a QP-free algorithm for the nonlinear minimax optimization with inequality constraints.By means of a new and much tighter working set,we develop a new technique for constructing the sub-matrix in the lower right corner of the coefficient matrix.At each iteration,to obtain the search direction,two reduced systems of linear equations with the same coefficient are solved.Under mild conditions,the proposed algorithm is globally convergent.Finally,some preliminary numerical experiments are reported,and these show that the algorithm is promising.

GLOBAL CONVERGENCE OF TRUST REGION ALGORITHM FOR EQUALITY AND BOUND CONSTRAINED NONLINEAR OPTIMIZATION

This paper presents a trust region two phase model algorithm for solving the equality and bound constrained nonlinear optimization problem. A concept of substationary point is given. Under suitable assumptions,the global convergence of this algorithm is proved without assuming the linear independence of the gradient of active constraints. A numerical example is also presented.

A Note on Global Convergence Result for Conjugate Gradient Methods

We extend a results presented by Y.F. Hu and C.Storey (1991) [1] on the global convergence result for conjugate gradient methods with different choices for the parameter β k . In this note, the conditions given on β k are milder than that used by Y.F. Hu and C. Storey.

Global Convergence of Adaptive Generalized Predictive Controller Based on Least Squares Algorithm

Some papers on stochastic adaptive control schemes have established convergence algorithm using a least-squares parameters. With the popular application of GPC, global convergence has become a key problem in automatic control theory. However, now global convergence of GPC has not been established for algorithms in computing a least squares iteration. A generalized model of adaptive generalized predictive control is presented. The global convergebce is also given on the basis of estimating the parameters of GPC by least squares algorithm.

GLOBAL CONVERGENCE OF THE GENERAL THREE TERM CONJUGATE GRADIENT METHODS WITH THE RELAXED STRONG WOLFE LINE SEARCH

The global convergence of the general three term conjugate gradient methods with the relaxed strong Wolfe line search is proved.

A Descent Gradient Method and Its Global Convergence

Y Liu and C Storey(1992)proposed the famous LS conjugate gradient method which has good numerical results.However,the LS method has very weak convergence under the Wolfe-type line search.In this paper,we give a new descent gradient method based on the LS method.It can guarantee the sufficient descent property at each iteration and the global convergence under the strong Wolfe line search.Finally,we also present extensive preliminary numerical experiments to show the efficiency of the proposed method by comparing with the famous PRP^+method.

CONVERGENCE OF A MODIFIED SLP ALGORITHM FOR THE EXTENDED LINEAR COMPLEMENTARITY PROBLEM

A modified sequential linear programming algorithm is presented, whose subproblem is always solvable, for the extended linear complementarity problem (XLCP), the global convergence of the algorithm under assumption of X-row sufficiency or X-colunm monotonicity is proved. As a result, a sufficient condition for existence and boundedness of solution to the XLCP are obtained.

Convergence Analysis of Cuckoo Search by Creating Markov Chain

Cuckoo search(CS) has been used successfully for solving global optimization problems.From a theoretical point of view,the convergence of the CS is an important issue.In this paper,convergence analysis of CS was studied.The transition probability characteristics of the population to construct a Markov chain were analyzed.The homogeneity of the Markov chain was derived based on stochastic process theory.Then it was proved to be an absorbing state Markov chain.Consequently,the global convergence of CS was deduced based on conditions of convergence sequence and total probability formula,and the expected convergence time was given.Finally,a series of experiments were conducted.Experimental results were analyzed and it is observed that CS seems to perform better than PSO.

A CLASS OF TRUST REGION METHODS FOR LINEAR INEQUALITY CONSTRAINED OPTIMIZATION AND ITS THEORY ANALYSIS：I．ALGORITHM AND GLOBAL CONVERGENCE

A class of trust region methods for solving linear inequality constrained problems is proposed in this paper. It is shown that the algorithm is of global convergence.The algorithm uses a version of the two-sided projection and the strategy of the unconstrained trust region methods. It keeps the good convergence properties of the unconstrained case and has the merits of the projection method. In some sense, our algorithm can be regarded as an extension and improvement of the projected type algorithm.

Convergence Analysis of a Kind of Deterministic Discrete-Time PCA Algorithm

We proposed a generalized adaptive learning rate (GALR) PCA algorithm, which could be guaranteed that the algorithm’s convergence process would not be affected by the selection of the initial value. Using the deterministic discrete time (DDT) method, we gave the upper and lower bounds of the algorithm and proved the global convergence. Numerical experiments had also verified our theory, and the algorithm is effective for both online and offline data. We found that choosing different initial vectors will affect the convergence speed, and the initial vector could converge to the second or third eigenvectors by satisfying some exceptional conditions.

Global Convergence of Curve Search Methods for Unconstrained Optimization

In this paper we propose a new family of curve search methods for unconstrained optimization problems, which are based on searching a new iterate along a curve through the current iterate at each iteration, while line search methods are based on finding a new iterate on a line starting from the current iterate at each iteration. The global convergence and linear convergence rate of these curve search methods are investigated under some mild conditions. Numerical results show that some curve search methods are stable and effective in solving some large scale minimization problems.

CONVERGENCE ANALYSIS ON A CLASS OF CONJUGATE GRADIENT METHODS WITHOUTSUFFICIENT DECREASE CONDITION

Recently, Gilbert and Nocedal([3]) investigated global convergence of conjugate gradient methods related to Polak-Ribiere formular, they restricted beta(k) to non-negative value. [5] discussed the same problem as that in [3] and relaxed beta(k) to be negative with the objective function being convex. This paper allows beta(k) to be selected in a wider range than [5]. Especially, the global convergence of the corresponding algorithm without sufficient decrease condition is proved.

GLOBAL CONVERGENCE OF NONMONOTONIC TRUST REGION ALGORITHM FOR NONLINEAR OPTIMIZATION

A trust region algorithm for equality constrained optimization is given in this paper.The algorithm does not enforce strict monotonicity of the merit function for every iteration.Global convergence of the algorithm is proved under the same conditions of usual trust region method.