A NEW STEPSIZE FOR THE STEEPEST DESCENT METHOD

The steepest descent method is the simplest gradient method for optimization. It is well known that exact line searches along each steepest descent direction may converge very slowly. An important result was given by Barzilar and Borwein, which is proved to be superlinearly convergent for convex quadratic in two dimensional space, and performs quite well for high dimensional problems. The BB method is not monotone, thus it is not easy to be generalized for general nonlinear functions unless certain non-monotone techniques being applied. Therefore, it is very desirable to find stepsize formulae which enable fast convergence and possess the monotone property. Such a stepsize αk for the steepest descent method is suggested in this paper. An algorithm with this new stepsize in even iterations and exact line search in odd iterations is proposed. Numerical results are presented, which confirm that the new method can find the exact solution within 3 iteration for two dimensional problems. The new method is very efficient for small scale problems. A modified version of the new method is also presented, where the new technique for selecting the stepsize is used after every two exact line searches. The modified algorithm is comparable to the Barzilar-Borwein method for large scale problems and better for small scale problems.     

COMBINATION OF GLOBAL AND LOCAL APPROXIMATION SCHEMES FOR HARMONIC MAPS INTO SPHERES

It is well understood that a good way to discretize a pointwise length constraint in partial differential equations or variational problems is to impose it at the nodes of a triangulation that defines a lowest order finite element space. This article pursues this approach and discusses the iterative solution of the resulting discrete nonlinear system of equations for a simple model problem which defines harmonic maps into spheres. An iterative scheme that is globally convergent and energy decreasing is combined with a locally rapidly convergent approximation scheme. An explicit example proves that the local approach alone may lead to ill-posed problems; numerical experiments show that it may diverge or lead to highly irregular solutions with large energy if the starting value is not chosen carefully. The combination of the global and local method defines a reliable algorithm that performs very efficiently in practice and provides numerical approximations with low energy.     

A new sequential systems of linear equations algorithm of feasible descent for inequality constrained optimization

Based on a new efficient identification technique of active constraints introduced in this paper, a new sequential systems of linear equations （SSLE） algorithm generating feasible iterates is proposed for solving nonlinear optimization problems with inequality constraints. In this paper, we introduce a new technique for constructing the system of linear equations, which recurs to a perturbation for the gradients of the constraint functions. At each iteration of the new algorithm, a feasible descent direction is obtained by solving only one system of linear equations without doing convex combination. To ensure the global convergence and avoid the Maratos effect, the algorithm needs to solve two additional reduced systems of linear equations with the same coefficient matrix after finite iterations. The proposed algorithm is proved to be globally and superlinearly convergent under some mild conditions. What distinguishes this algorithm from the previous feasible SSLE algorithms is that an improving direction is obtained easily and the computation cost of generating a new iterate is reduced. Finally, a preliminary implementation has been tested.     

A GENERALIZED PROJECTION-SUCCESSIVE LINEAREQUATIONS ALGORITHM FOR NONLINEARLY EQUALITy AND INEQUALITY CONSTRAINED OPTIMIZATION AND ITS RATE OF CONVERGENCE

In this paper, a new superlinearly convergent algorithm is presented for optimization problems with general nonlineer equality and inequality Constraints, Comparing with other methods for these problems, the algorithm has two main advantages. First, it doesn‘t solve anyquadratic programming (QP), and its search directions are determined by the generalized projection technique and the solutions of two systems of linear equations. Second, the sequential points generated by the algoritbh satisfy all inequity constraints and its step-length is computed by the straight line search,The algorithm is proved to possesa global and auperlinear convergence.     

An algorithm for solving new trust region subproblem with conic model

The new trust region subproblem with the conic model was proposed in 2005, and was divided into three different cases. The first two cases can be converted into a quadratic model or a convex problem with quadratic constraints, while the third one is a nonconvex problem. In this paper, first we analyze the nonconvex problem, and reduce it to two convex problems. Then we discuss some dual properties of these problems and give an algorithm for solving them. At last, we present an algorithm for solving the new trust region subproblem with the conic model and report some numerical examples to illustrate the efficiency of the algorithm.     

A NEW NONMONOTONE TRUST REGION ALGORITHM FOR SOLVING UNCONSTRAINED OPTIMIZATION PROBLEMS

Based on the nonmonotone line search technique proposed by Gu and Mo （Appl. Math. Comput. 55, （2008） pp. 2158-2172）, a new nonmonotone trust region algorithm is proposed for solving unconstrained optimization problems in this paper. The new algorithm is developed by resetting the ratio ρk for evaluating the trial step dk whenever acceptable. The global and superlinear convergence of the algorithm are proved under suitable conditions. Numerical results show that the new algorithm is effective for solving unconstrained optimization problems.     

ERROR ESTIMATES FOR THE RECURSIVE LINEARIZATION OF INVERSE MEDIUM PROBLEMS

This paper is devoted to the mathematical analysis of a general recursive linearization algorithm for solving inverse medium problems with multi-frequency measurements. Under some reasonable assumptions, it is shown that the algorithm is convergent with error estimates. The work is motivated by our effort to analyze recent significant numerical results for solving inverse medium problems. Based on the uncertainty principle, the recursive linearization allows the nonlinear inverse problems to be reduced to a set of linear problems and be solved recursively in a proper order according to the measurements. As an application, the convergence of the recursive linearization algorithm [Chen, Inverse Problems 13（1997）, pp.253-282] is established for solving the acoustic inverse scattering problem.     

非线性不等式约束最优化快速收敛的可行信赖域算法

In this paper,by combining the trust region technique with the generalized gradient projection.a new trust region algorithm with feasible iteration points is presented for nonlinear inequality constrained optimization,and its trust region is a general compact set containing the origion as an inteior point.No penalty function is used in the algorithm,and it is feasible descent .Under suitable assumptions,the algorithm is proved to possess global and strong convergence as well as superlinear and quadratic convergence.Some numerical results are reported.     

COMPUTATION OF CONTINUOUS WAVELET TRANSFORM AT DYADIC SCALES BY SUBDIVISION SCHEME

A new algorithm to compute continuous wavelet transforms at dyadic scales is proposed here. Our approach has a similar implementation with the standard algorithme a trous and can coincide with it in the one dimensional lower order spline case.Our algorithm can have arbitrary order of approximation and is applicable to the multidimensional case.We present this algorithm in a general case with emphasis on splines anti quast in terpolations.Numerical examples are included to justify our theorerical discussion.     

A Level Set Representation Method for N-Dimensional Convex Shape and Applications

In this work,we present a new method for convex shape representation,which is regardless of the dimension of the concerned objects,using level-set approaches.To the best of our knowledge,the proposed prior is the first one which can work for high dimensional objects.Convexity prior is very useful for object completion in computer vision.It is a very challenging task to represent high dimensional convex objects.In this paper,we first prove that the convexity of the considered object is equivalent to the convexity of the associated signed distance function.Then,the second order condition of convex functions is used to characterize the shape convexity equivalently.We apply this new method to two applications:object segmentation with convexity prior and convex hull problem(especially with outliers).For both applications,the involved problems can be written as a general optimization problem with three constraints.An algorithm based on the alternating direction method of multipliers is presented for the optimization problem.Numerical experiments are conducted to verify the effectiveness of the proposed representation method and algorithm.     

Low dimensional simplex evolution: a new heuristic for global optimization

This paper presents a new heuristic for global optimization named low dimensional simplex evolution (LDSE). It is a hybrid evolutionary algorithm. It generates new individuals following the Nelder-Mead algorithm and the individuals survive by the rule of natural selection. However, the simplices therein are real-time constructed and low dimensional. The simplex operators are applied selectively and conditionally. Every individual is updated in a framework of try-try-test. The proposed algorithm is very easy to use. Its efficiency has been studied with an extensive testbed of 50 test problems from the reference (J Glob Optim 31:635–672, 2005). Numerical results show that LDSE outperforms an improved version of differential evolution (DE) considerably with respect to the convergence speed and reliability.     

A dynamic clustering based differential evolution algorithm for global optimization

A dynamic clustering based differential evolution algorithm (CDE) for global optimization is proposed to improve the performance of the differential evolution (DE) algorithm. With population evolution, CDE algorithm gradually changes from exploring promising areas at the early stages to exploiting solution with high precision at the later stages. Experiments on 28 benchmark problems, including 13 high dimensional functions, show that the new method is able to find near optimal solutions efficiently. Compared with other existing algorithms, CDE improves solution accuracy with less computational effort.     

Scale factor local search in differential evolution

This paper proposes the scale factor local search differential evolution (SFLSDE). The SFLSDE is a differential evolution (DE) based memetic algorithm which employs, within a self-adaptive scheme, two local search algorithms. These local search algorithms aim at detecting a value of the scale factor corresponding to an offspring with a high performance, while the generation is executed. The local search algorithms thus assist in the global search and generate offspring with high performance which are subsequently supposed to promote the generation of enhanced solutions within the evolutionary framework. Despite its simplicity, the proposed algorithm seems to have very good performance on various test problems. Numerical results are shown in order to justify the use of a double local search instead of a single search. In addition, the SFLSDE has been compared with a standard DE and three other modern DE based metaheuristic for a large and varied set of test problems. Numerical results are given for relatively low and high dimensional cases. A statistical analysis of the optimization results has been included in order to compare the results in terms of final solution detected and convergence speed. The efficiency of the proposed algorithm seems to be very high especially for large scale problems and complex fitness landscapes.     

Differential evolution algorithms using hybrid mutation

Differential evolution (DE) has gained a lot of attention from the global optimization research community. It has proved to be a very robust algorithm for solving non-differentiable and non-convex global optimization problems. In this paper, we propose some modifications to the original algorithm. Specifically, we use the attraction-repulsion concept of electromagnetism-like (EM) algorithm to boost the mutation operation of the original differential evolution. We carried out a numerical study using a set of 50 test problems, many of which are inspired by practical applications. Results presented show the potential of this new approach.     

Self-adaptive randomized and rank-based differential evolution for multimodal problems

Differential Evolution (DE) is a widely used successful evolutionary algorithm (EA) based on a population of individuals, which is especially well suited to solve problems that have non-linear, multimodal cost functions. However, for a given population, the set of possible new populations is finite and a true subset of the cost function domain. Furthermore, the update formula of DE does not use any information about the fitness of the population. This paper presents a novel extension of DE called Randomized and Rank-based Differential Evolution (R2DE) and its self-adaptive version SAR2DE to improve robustness and global convergence speed on multimodal problems by introducing two multiplicative terms in the DE update formula. The first term is based on a random variate of a Cauchy distribution, which leads to a randomization. The second term is based on ranking of individuals, so that R2DE exploits additional information provided by the population fitness. In extensive experiments conducted with a wide range of complexity settings, we show that the proposed heuristics lead to an overall improvement in robustness and speed of convergence compared to several global optimization techniques, including DE, Opposition based Differential Evolution (ODE), DE with Random Scale Factor (DERSF) and the self-adaptive Cauchy distribution based DE (NSDE).     

Differential evolution for sequencing and scheduling optimization

This paper presents a stochastic method based on the differential evolution (DE) algorithm to address a wide range of sequencing and scheduling optimization problems. DE is a simple yet effective adaptive scheme developed for global optimization over continuous spaces. In spite of its simplicity and effectiveness the application of DE on combinatorial optimization problems with discrete decision variables is still unusual. A novel solution encoding mechanism is introduced for handling discrete variables in the context of DE and its performance is evaluated over a plethora of public benchmarks problems for three well-known NP-hard scheduling problems. Extended comparisons with the well-known random-keys encoding scheme showed a substantially higher performance for the proposed. Furthermore, a simple slight modification in the acceptance rule of the original DE algorithm is introduced resulting to a more robust optimizer over discrete spaces than the original DE.     

改进种群多样性的双变异差分进化算法

差分进化算法(DE)是一种基于种群的启发式随机搜索技术,对于解决连续性优化问题具有较强的鲁棒性.然而传统差分进化算法存在种群多样性和收敛速度之间的矛盾,一种改进种群多样性的双变异差分进化算法(DADE),通过引入BFS-best机制(基于排序的可行解选取递减策略)改进变异算子"DE/current-to-best",将其与DE/rand/1构成双变异策略来改善DE算法中种群多样性减少的问题.同时,每个个体的控制参数基于排序自适应更新.最后,利用多个CEC2013标准测试函数对改进算法进行测试,实验结果表明,改进后的算法能有效改善种群多样性,较好地提高了算法的全局收敛能力和收敛速度.     

Cognitive learning in differential evolution and its application to model order reduction problem for single-input single-output systems

Differential evolution (DE) is a well known and simple population based probabilistic approach for global optimization over continuous spaces. It has reportedly outperformed a few evolutionary algorithms and other search heuristics like the particle swarm optimization when tested over both benchmark and real world problems. DE, like other probabilistic optimization algorithms, has inherent drawback of premature convergence and stagnation. Therefore, in order to find a trade-off between exploration and exploitation capability of DE algorithm, a new parameter namely, cognitive learning factor (CLF) is introduced in the mutation process. Cognitive learning is a powerful mechanism that adjust the current position of individuals by the means of some specified knowledge (previous experience of individuals). The proposed strategy is named as cognitive learning in differential evolution (CLDE). To prove the efficiency of various approaches of CLF in DE,?CLDE is tested over 25 benchmark problems. Further, to establish the wide applicability of CLF,?CLDE is applied to two advanced DE variants. CLDE is also applied to solve a well known electrical engineering problem called model order reduction problem for single input single output systems.     

Differential Evolution algorithm with Separated Groups for multi-dimensional optimization problems

The classical Differential Evolution (DE) algorithm, one of population-based Evolutionary Computation methods, proved to be a successful approach for relatively simple problems, but does not perform well for difficult multi-dimensional non-convex functions. A number of significant modifications of DE have been proposed in recent years, including very few approaches referring to the idea of distributed Evolutionary Algorithms. The present paper presents a new algorithm to improve optimization performance, namely DE with Separated Groups (DE-SG), which distributes population into small groups, defines rules of exchange of information and individuals between the groups and uses two different strategies to keep balance between exploration and exploitation capabilities. The performance of DE-SG is compared to that of eight algorithms belonging to the class of Evolutionary Strategies (Covariance Matrix Adaptation ES), Particle Swarm Optimization (Comprehensive Learning PSO and Efficient Population Utilization Strategy PSO), Differential Evolution (Distributed DE with explorative-exploitative population families, Self-adaptive DE, DE with global and local neighbours and Grouping Differential Evolution) and multi-algorithms (AMALGAM). The comparison is carried out for a set of 10-, 30- and 50-dimensional rotated test problems of varying difficulty, including 10- and 30-dimensional composition functions from CEC2005. Although slow for simple functions, the proposed DE-SG algorithm achieves a great success rate for more difficult 30- and 50-dimensional problems.     

基于种群自适应调整的多目标差分进化算法

为提高已有多目标进化算法在求解复杂多目标优化问题上的收敛性和解集分布性,提出一种基于种群自适应调整的多目标差分进化算法。该算法设计一个种群扩增策略,它在决策空间生成一些新个体帮助搜索更优的非支配解;设计了一个种群收缩策略,它依据对非支配解集的贡献程度淘汰较差的个体以减少计算负荷,并预留一些空间给新的带有种群多样性的扰动个体;引入精英学习策略,防止算法陷入局部收敛。通过典型的多目标优化函数对算法进行测试验证,结果表明所提算法相对于其他算法具有明显的优势,其性能优越,能够在保证良好收敛性的同时,使获得的Pareto最优解集具有更均匀的分布性和更广的覆盖范围,尤其适合于高维复杂多目标优化问题的求解。