A linear programming-based optimization algorithm for solving nonlinear programming problems

In this paper a linear programming-based optimization algorithm called the Sequential Cutting Plane algorithm is presented. The main features of the algorithm are described, convergence to a Karush–Kuhn–Tucker stationary point is proved and numerical experience on some well-known test sets is showed. The algorithm is based on an earlier version for convex inequality constrained problems, but here the algorithm is extended to general continuously differentiable nonlinear programming problems containing both nonlinear inequality and equality constraints. A comparison with some existing solvers shows that the algorithm is competitive with these solvers. Thus, this new method based on solving linear programming subproblems is a good alternative method for solving nonlinear programming problems efficiently. The algorithm has been used as a subsolver in a mixed integer nonlinear programming algorithm where the linear problems provide lower bounds on the optimal solutions of the nonlinear programming subproblems in the branch and bound tree for convex, inequality constrained problems.     

强收敛的球松弛CQ算法及其应用

为了求解分裂可行问题,Yu等提出了一个球松弛CQ算法。由于该算法只需计算到闭球上的投影,同时不需要计算有界线性算子的范数,该算法是容易实现的。但是球松弛CQ算法在无穷维Hilbert空间中仅仅具有弱收敛性。首先构造了一个强收敛的球松弛CQ算法。在较弱的条件下,证明了算法的强收敛性。其次将该算法应用到一类闭凸集上的投影问题上。最后,数值试验验证了该算法的有效性。     

一种改进的蚁群算法及其在TSP中的应用

蚁群算法是一种求解复杂组合优化问题的新的拟生态算法,也是一种基于种群的启发式仿生进化算法,属于随机搜索算法的一种,并用于较好地解决TSP问题.然而此算法也有它自己的缺陷,如易于陷入局部优化、搜索时间长等.通过对基本蚁群算法的介绍及相关因素的分析,提出了一种改进的蚁群算法,用于解决TSPLAB问题的10个问题,并与参考文献中的F-W、NCSOM、ASOM算法进行比较,计算机仿真结果表明了改进算法的有效性.如利用改进的蚁群算法解决lin105问题,其最优解为14382.995933(已知最优解为14379),相对误差是0.0209%,计算出的最小值几乎接近于已知最优解.     

Implicitly restarted projection algorithm for solving optimization problems

An algorithm for solving the problem of minimizing a quadratic function subject to ellipsoidal constraints is introduced. This algorithm is based on the impHcitly restarted Lanczos method to construct a basis for the Krylov subspace in conjunction with a model trust region strategy to choose the step. The trial step is computed on the small dimensional subspace that lies inside the trust region.

One of the main advantages of this algorithm is the way that the Krylov subspace is terminated. We introduce a terminationcondition that allows the gradient to be decreased on that subspace.

A convergence theory for this algorithm is presented. It is shown that this algorithm is globally convergent and it shouldcope quite well with large scale minimization problems. This theory is sufficiently general that it holds for any algorithm that projects the problem on a lower dimensional subspace.     

Gaussian kernel approximation algorithm for feedforward neural network design

A Gaussian kernel approximation algorithm for a feedforward neural network is presented. The approach used by the algorithm, which is based on a constructive learning algorithm, is to create the hidden units directly so that automatic design of the architecture of neural networks can be carried out. The algorithm is defined using the linear summation of input patterns and their randomized input weights. Hidden-layer nodes are defined so as to partition the input space into homogeneous regions, where each region contains patterns belonging to the same class. The largest region is used to define the center of the corresponding Gaussian hidden nodes. The algorithm is tested on three benchmark data sets of different dimensionality and sample sizes to compare the approach presented here with other algorithms. Real medical diagnoses and a biological classification of mushrooms are used to illustrate the performance of the algorithm. These results confirm the effectiveness of the proposed algorithm.     

A simulated annealing technique for multi-objective simulation optimization

In this paper, we present a simulated annealing algorithm for solving multi-objective simulation optimization problems. The algorithm is based on the idea of simulated annealing with constant temperature, and uses a rule for accepting a candidate solution that depends on the individual estimated objective function values. The algorithm is shown to converge almost surely to an optimal solution. It is applied to a multi-objective inventory problem; the numerical results show that the algorithm converges rapidly.     

A multiple local search algorithm for continuous dynamic optimization

Many real-world optimization problems are dynamic (time dependent) and require an algorithm that is able to track continuously a changing optimum over time. In this paper, we propose a new algorithm for dynamic continuous optimization. The proposed algorithm is based on several coordinated local searches and on the archiving of the optima found by these local searches. This archive is used when the environment changes. The performance of the algorithm is analyzed on the Moving Peaks Benchmark and the Generalized Dynamic Benchmark Generator. Then, a comparison of its performance to the performance of competing dynamic optimization algorithms available in the literature is done. The obtained results show the efficiency of the proposed algorithm.     

Numerical algorithm for solving diffusion-type equations on the basis of multigrid methods

A new numerical algorithm based on multigrid methods is proposed for solving equations of the parabolic type. Theoretical error estimates are obtained for the algorithm as applied to a two-dimensional initial-boundary value model problem for the heat equation. The good accuracy of the algorithm is demonstrated using model problems including ones with discontinuous coefficients. As applied to initial-boundary value problems for diffusion equations, the algorithm yields considerable savings in computational work compared to implicit schemes on fine grids or explicit schemes with a small time step on fine grids. A parallelization scheme is given for the algorithm.     

Application of the dual active set algorithm to quadratic network optimization

A new algorithm, the dual active set algorithm, is presented for solving a minimization problem with equality constraints and bounds on the variables. The algorithm identifies the active bound constraints by maximizing an unconstrained dual function in a finite number of iterations. Convergence of the method is established, and it is applied to convex quadratic programming. In its implementable form, the algorithm is combined with the proximal point method. A computational study of large-scale quadratic network problems compares the algorithm to a coordinate ascent method and to conjugate gradient methods for the dual problem. This study shows that combining the new algorithm with the nonlinear conjugate gradient method is particularly effective on difficult network problems from the literature.     

An improved Monte Carlo factorization algorithm

Pollard's Monte Carlo factorization algorithm usually finds a factor of a composite integerN inO(N ^1/4) arithmetic operations. The algorithm is based on a cycle-finding algorithm of Floyd. We describe a cycle-finding algorithm which is about 36 percent faster than Floyd's (on the average), and apply it to give a Monte Carlo factorization algorithm which is similar to Pollard's but about 24 percent faster.     

求解Sylvester矩阵方程的一种改进的梯度方法

提出了一种改进的梯度迭代算法来求解Sylvester矩阵方程和Lyapunov矩阵方程.该梯度算法是通过构造一种特殊的矩阵分裂,综合利用Jaucobi迭代算法和梯度迭代算法的求解思路.与已知的梯度算法相比,提高了算法的迭代效率.同时研究了该算法在满足初始条件下的收敛性.数值算例验证了该算法的有效性.     

Numerical algorithm for solving mathematical programming problems with a smooth surface as a constraint

A numerical algorithm for minimizing a convex function on a smooth surface is proposed. The algorithm is based on reducing the original problem to a sequence of convex programming problems. Necessary extremum conditions are examined, and the convergence of the algorithm is analyzed.     

An algorithm for maximizing a convex function over a simple set

The problem of maximizing a convex function on a so-called simple set is considered. Based on the optimality conditions [19], an algorithm for solving the problem is proposed. This numerical algorithm is shown to be convergent. The proposed algorithm has been implemented and tested on a variety of test problems.     

遗传算法的物理解释

提出了一种理想化的模拟仿生搜索算法——扰动算法 ,以此方法为基础 ,分析了遗传算法的搜索过程和效率问题 ,阐明了遗传算法作为一种次优算法的有效性 .相对于遗传算法的生物解释 ,本文给出了相应的物理解释 .同时 ,本文为遗传算法、进化策略和模拟退火算法找到了一种统一的物理解释 ,揭示了这些重要的仿生类算法实质上的相似性 .     

自适应约束模糊C均值聚类算法

针对经典C均值聚类算法和模糊C均值聚类算法所存在的对初始聚类中心过分依赖以及需要预先知道实际聚类数目的问题,基于模糊C均值聚类算法提出了一种新算法:自适应约束模糊C均值(ACFCM)聚类算法,它在模糊C均值聚类算法的基础上,给目标函数加入了一个惩罚项,使得上述问题得以解决.并通过仿真实验证实了新算法的可行性和有效性.     

Componentwise adaptation for high dimensional MCMC

Summary  We introduce a new adaptive MCMC algorithm, based on the traditional single component Metropolis-Hastings algorithm and on our earlier adaptive Metropolis algorithm (AM). In the new algorithm the adaption is performed component by component. The chain is no more Markovian, but it remains ergodic. The algorithm is demonstrated to work well in varying test cases up to 1000 dimensions.     

A hybrid heuristic algorithm for the 2D variable-sized bin packing problem

In this paper, we consider the two-dimensional variable-sized bin packing problem (2DVSBPP) with guillotine constraint. 2DVSBPP is a well-known NP-hard optimization problem which has several real applications. A mixed bin packing algorithm (MixPacking) which combines a heuristic packing algorithm with the Best Fit algorithm is proposed to solve the single bin problem, and then a backtracking algorithm which embeds MixPacking is developed to solve the 2DVSBPP. A hybrid heuristic algorithm based on iterative simulated annealing and binary search (named HHA) is then developed to further improve the results of our Backtracking algorithm. Computational experiments on the benchmark instances for 2DVSBPP show that HHA has achieved good results and outperforms existing algorithms.     

QN THE CONVERGENCE ANALYSIS OF THE NONLINEAR ABS METHODS

In order to complete the convergence theory of nonlinear ABS algorithm, through a careful investigation to the algorithm structure, the author converts the nonlinear ABS algorithm into an inexact Newton method. Based on such equivalent variation, the Kantorovich type convergence of the ABS algorithm is established and the Convergence conditions of the algorithm that only depend on the initial conditions are obtained, which provides a useful basis for the choices of initial points of the ABS algorithm.     

关于解极大相关问题P-SOR算法的收敛性

对求解极大相关问题的P-SOR方法的收敛性做了进一步研究.得到了一些新的收敛条件.为了提高收敛到全局最大解的可能性,提出了一种新的初始向量选择策略.给出了P-SOR算法的对称形式(P-SSOR).还给出了一种算法精化策略.最后,用数值例子说明新方法的有效性.     

An alogrithm for monotonic global optimization problems ∗

We propose an algorithm to locate a global maximum of an increasing function subject to an increasing constraint on the cone of vectors with nonnegative coordinates. The algorithm is based on the outer approximation of the feasible set. We eastablish the con vergence of the algorithm and provide a number of numerical experiments. We also discuss the types of constraints and objective functions for which the algorithm is best suited