A Newton Acceleration of the Weiszfeld Algorithm for Minimizing the Sum of Euclidean Distances

The Weiszfeld algorithm for continuous location problems can be considered as an iteratively reweighted least squares method. It generally exhibits linear convergence. In this paper, a Newton algorithm with similar simplicity is proposed to solve a continuous multifacility location problem with the Euclidean distance measure. Similar to the Weiszfeld algorithm, the main computation can be solving a weighted least squares problem at each iteration. A Cholesky factorization of a symmetric positive definite band matrix, typically with a small band width (e.g., a band width of two for a Euclidean location problem on a plane) is performed. This new algorithm can be regarded as a Newton acceleration to the Weiszfeld algorithm with fast global and local convergence. The simplicity and efficiency of the proposed algorithm makes it particularly suitable for large-scale Euclidean location problems and parallel implementation. Computational experience suggests that the proposed algorithm often performs well in the absence of the linear independence or strict complementarity assumption. In addition, the proposed algorithm is proven to be globally convergent under similar assumptions for the Weiszfeld algorithm. Although local convergence analysis is still under investigation, computation results suggest that it is typically superlinearly convergent.     

A smoothing Levenberg-Marquardt algorithm for solving a class of stochastic linear complementarity problem

In this paper, it is considered for a class of stochastic linear complementarity problems (SLCPs) with finitely many elements. A smoothing Levenberg-Marquardt algorithm is proposed for solving the SLCP. Under suitable conditions, the global convergence and local quadratic convergence of the proposed algorithm is given. Some numerical results are reported in this paper, which confirms the good theoretical properties of the proposed algorithm.     

Projected quasi-Newton algorithm with trust region for constrained optimization

In Ref. 1, Nocedal and Overton proposed a two-sided projected Hessian updating technique for equality constrained optimization problems. Although local two-step Q-superlinear rate was proved, its global convergence is not assured. In this paper, we suggest a trust-region-type, two-sided, projected quasi-Newton method, which preserves the local two-step superlinear convergence of the original algorithm and also ensures global convergence. The subproblem that we propose is as simple as the one often used when solving unconstrained optimization problems by trust-region strategies and therefore is easy to implement.This research was supported in part by the National Natural Science Foundation of China.     

Performance analysis of a distributed fixed-step power control algorithm via window concept in cellular mobile systems

In cellular mobile systems, the received carrier-to-interference ratio (CIR) can be maintained within the desirable range provided that the path gain remains approximately constant over a number of consecutive power control steps. However, when channels suffer short-term fading, it is not clear whether existing power control algorithms remain convergent. This paper proposes a distributed fixed-step power control algorithm with binary feedback via window concept for cellular mobile systems. The essence of the proposed algorithm is that the power control step size can be regulated by window size. The performance of the proposed scheme is analyzed in short-term fading channels. A sufficient condition for system stability is derived using a simple received CIR model and a power control window. It is shown herein that the bound of the received CIR of each user varies as a function of the target CIR, the size of the power control step and the link gain. The analysis and simulation results show that if the step size is properly set according to the window size, the proposed algorithm can achieve a small convergence region and a fast convergence rate.     

Adaptive brainstorm optimisation with multiple strategies

Brainstorm optimisation (BSO) algorithm is a recently developed swarm intelligence algorithm inspired by the human problem-solving process. BSO has been shown to be an efficient method for creating better ideas to deal with complex problems. The original BSO suffers from low convergence and is easily trapped in local optima due to the improper balance between global exploration and local exploitation. Motivated by the memetic framework, an adaptive BSO with two complementary strategies (AMBSO) is proposed in this study. In AMBSO, a differential-based mutation technique is designed for global exploration improvement and a sub-gradient strategy is integrated for local exploitation enhancement. To dynamically trigger the appropriate strategy, an adaptive selection mechanism based on historical effectiveness is developed. The proposed algorithm is tested on 30 benchmark functions with various properties, such as unimodal, multimodal, shifted and rotated problems, in dimensions of 10, 30 and 50 to verify their scalable performance. Six state-of-the-art optimisation algorithms are included for comparison. Experimental results indicate the effectiveness of AMBSO in terms of solution quality and convergence speed.     

An effective adaptive trust region algorithm for nonsmooth minimization

In this paper, an adaptive trust region algorithm that uses Moreau–Yosida regularization is proposed for solving nonsmooth unconstrained optimization problems. The proposed algorithm combines a modified secant equation with the BFGS update formula and an adaptive trust region radius, and the new trust region radius utilizes not only the function information but also the gradient information. The global convergence and the local superlinear convergence of the proposed algorithm are proven under suitable conditions. Finally, the preliminary results from comparing the proposed algorithm with some existing algorithms using numerical experiments reveal that the proposed algorithm is quite promising for solving nonsmooth unconstrained optimization problems.     

求解混合流水线调度问题的离散人工蜂群算法

本文给出了一种离散的人工蜂群算法(HDABC)用于求解混合流水车间调度(HFS)问题。采用工件排序的编码方式,并设计了四种邻域结构。雇佣蜂依次分派到解集中每个解,采用结合问题特征的局部搜索策略完成挖掘搜索工作。跟随蜂随机选择两个解并挑选较优者作为当前解,完成进一步的探优过程。侦察蜂采用三种策略跳出局部极小。通过34个同构并行机HFS问题和2个异构并行机HFS实际调度问题的实验,并与当前文献中的典型算法对比,验证了本文提出的算法无论在算法时间还是在求解质量上,都具备良好的性能。     

求解约束优化问题的一个对偶算法

１．引言 考虑下述形式的不等式约束优化问题：其中 ＝０,１,…,ｍ,是连续可微函数．求解（１．１）的数值方法有很多,传统方法有乘子法,序列一次规划方法,等等（见 Ｂｅｒｔｓｅｋａｓ（１９８２）, Ｈａｎ（１９７６, １９７７））．近年来对求解（１．１）的原始－对偶算法的研究已成为非线性规划领域的新的热点,如ＥＩ－Ｂａｋｒｙ,Ｔａｐｉａ,Ｔｓｕｃｈｉｙａ　＆　Ｚｈａｎｇ（１９９６）,Ｙａｍａｓｈｉｔａ（１９９２,１９９６,１９９７）等;尽管这些原始－对偶算法具有好的收敛性质和计算效果,但其算法结构相对…     

A FEASIBLE SEMISMOOTH GAUSS-NEWTON METHOD FOR SOLVING A CLASS OF SLCPS

In this paper, we consider a class of the stochastic linear complementarity problems (SLCPs) with finitely many elements. A feasible semismooth damped Gauss-Newton algorithm for the SLCP is proposed. The global and local quadratic convergence of the proposed algorithm are obtained under suitable conditions. Some numerical results are reported in this paper, which confirm the good theoretical properties of the proposed algorithm.     

A recursive quadratic programming algorithm that uses differentiable exact penalty functions

In this paper, a recursive quadratic programming algorithm for solving equality constrained optimization problems is proposed and studied. The line search functions used are approximations to Fletcher's differentiable exact penalty function. Global convergence and local superlinear convergence results are proved, and some numerical results are given.     

A regularization smoothing method for second-order cone complementarity problem

In this paper, the second-order cone complementarity problem is studied. Based on the Fischer–Burmeister function with a perturbed parameter, which is also called smoothing parameter, a regularization smoothing Newton method is presented for solving the sequence of regularized problems of the second-order cone complementarity problem. Under proper conditions, the global convergence and local superlinear convergence of the proposed algorithm are obtained. Moreover, the local superlinear convergence is established without strict complementarity conditions. Preliminary numerical results suggest the effectiveness of the algorithm.     

含有等式约束非线性规划的全局优化算法

针对含有多个等式约束的非线性规划问题,提出一个全局优化算法.该方法基于可行集策略把改进的模拟退火方法与确定的局部算法方法相结合.对算法的收敛性进行了证明,数值结果表明算法的有效性及正确性.     

A hybrid glowworm swarm optimization algorithm to solve constrained multimodal functions optimization

In this paper, a novel hybrid glowworm swarm optimization (HGSO) algorithm is proposed. The HGSO algorithm embeds predatory behaviour of artificial fish swarm algorithm (AFSA) into glowworm swarm optimization (GSO) algorithm and combines the GSO with differential evolution on the basis of a two-population co-evolution mechanism. In addition, to overcome the premature convergence, the local search strategy based on simulated annealing is applied to make the search of GSO approach the true optimum solution gradually. Finally, several benchmark functions show that HGSO has faster convergence efficiency and higher computational precision, and is more effective for solving constrained multi-modal function optimization problems.     

求解非线性互补问题的一类光滑Broyden-like方法

非线性互补问题可以等价地转换为光滑方程组来求解. 基于一种新的非单调线搜索准则, 提出了求解非线性互补问题等价光滑方程组的一类新的非单调光滑 Broyden-like 算法.在适当的假设条件下, 证明了该算法的全局收敛性与局部超线性收敛性. 数值实验表明所提出的算法是有效的.     

混合变异粒子群优化算法及其应用

为改善粒子群优化算法在解决复杂优化问题时收敛质量不高的不足,提出了一种改进的粒子群优化算法,即混合变异粒子群优化算法(HMPSO).HMPSO算法采用了带有随机因子的惯性权重取值更新策略,降低了标准粒子群优化算法中由于粒子飞行速度过大而错过最优解的概率,从而加速了算法的收敛速度.此外,通过混合变异进化环节的引入,缓解了...     

Optimal Scaling of a Gradient Method for Distributed Resource Allocation

We consider a class of weighted gradient methods for distributed resource allocation over a network. Each node of the network is associated with a local variable and a convex cost function; the sum of the variables (resources) across the network is fixed. Starting with a feasible allocation, each node updates its local variable in proportion to the differences between the marginal costs of itself and its neighbors. We focus on how to choose the proportional weights on the edges (scaling factors for the gradient method) to make this distributed algorithm converge and on how to make the convergence as fast as possible.We give sufficient conditions on the edge weights for the algorithm to converge monotonically to the optimal solution; these conditions have the form of a linear matrix inequality. We give some simple, explicit methods to choose the weights that satisfy these conditions. We derive a guaranteed convergence rate for the algorithm and find the weights that minimize this rate by solving a semidefinite program. Finally, we extend the main results to problems with general equality constraints and problems with block separable objective function.The authors are grateful to Professor Paul Tseng and the anonymous referee for their valuable comments that helped us to improve the presentation of this paper.Communicated by P. Tseng     

A Novel Bat Algorithm based on Cross Boundary Learning and Uniform Explosion Strategy

Population-based algorithms have been used in many real-world problems. Bat algorithm(BA) is one of the states of the art of these approaches. Because of the super bat,on the one hand, BA can converge quickly; on the other hand, it is easy to fall into local optimum. Therefore, for typical BA algorithms, the ability of exploration and exploitation is not strong enough and it is hard to find a precise result. In this paper, we propose a novel bat algorithm based on cross boundary learning(CBL) and uniform explosion strategy(UES),namely BABLUE in short, to avoid the above contradiction and achieve both fast convergence and high quality. Different from previous opposition-based learning, the proposed CBL can expand the search area of population and then maintain the ability of global exploration in the process of fast convergence. In order to enhance the ability of local exploitation of the proposed algorithm, we propose UES, which can achieve almost the same search precise as that of firework explosion algorithm but consume less computation resource. BABLUE is tested with numerous experiments on unimodal, multimodal, one-dimensional, high-dimensional and discrete problems, and then compared with other typical intelligent optimization algorithms.The results show that the proposed algorithm outperforms other algorithms.     

Distributed Stochastic Algorithm for Global Optimization in Networked System

This paper studies the distributed optimization problem, whose aim is to find the global minimizer of the sum of multiple agents’ local nonconvex objective functions in a networked system. To solve such a distributed global optimization problem, we propose a distributed stochastic algorithm and we give detailed analysis of the global convergence of the proposed algorithm.     

Harris Hawks optimization with information exchange

The basic Harris Hawks optimization algorithm cannot take full advantage of the information sharing capability of the Harris Hawks while cooperatively searching for prey, and it is difficult to balance the exploration and development capacities of this algorithm. These factors limit the Harris Hawks optimization algorithm, such as in terms of premature convergence and ease of falling into a local optimum. To this end, an improved Harris Hawks optimization algorithm based on information exchange is proposed to optimize the continuous function and its application to engineering problems. First, an individual Harris Hawk obtains information from the shared area of cooperative foraging and the location area of collaborators, thereby realizing information exchange and sharing. Second, a nonlinear escaping energy factor with chaos disturbance is designed to better balance the local searching and the global searching of the algorithm. Finally, a numerical experiment is conducted with four benchmark test functions and five CEC-2017 real-parameter numerical optimization problems as well as seven practical engineering problems. The results show that the proposed algorithm outperforms the basic Harris Hawks optimization algorithm and other intelligence optimization algorithms in terms of the convergence rate, solution accuracy, and robustness.     

QP-Free,Truncated Hybrid Methods for Large-Scale Nonlinear Constrained Optimization

1.IntroductionInthispaperweconsiderthefollowingnonlinearprogrammingproblemminimizef(x)subjecttogj(x)2o,jEJ={1,...,m}.(1'1)Extensionstoproblemincludingalsoequalityconstraintswillbepossible.Thefunctionf:W-Rlandgj:Rn-R',jEJaretwicecontinuouslydifferentiable.Inpaxticular,weapplyQP-free(withoutquadraticprogrammingsubproblems),truncatedhybridmethodsforsolvingthelarge-scaJenonlinearprogrammingproblems,inwhichthenumberofvariablesandthenumberofconstraiotsin(1.1)aregreat.Wediscussthecase,wheresecon…