带扩散项四阶抛物方程的一类本性并行差分格式

给出逼近带扩散项四阶抛物方程一组非对称差分格式,对此组非对称格式重新组合,得到了一类新的具有并行本性的算法.随后,利用矩阵法证明了算法的绝对稳定性.最后给出数值实验.     

带漂移的单侧正规化回火分数阶扩散方程的Crank-Nicolson拟紧格式

基于已有的针对单侧正规化回火分数阶扩散方程的三阶拟紧算法,将该算法的思想应用于带漂移的单侧正规化回火分数阶扩散方程的数值模拟,并结合Crank-Nicolson方法导出数值格式.证明了数值格式的稳定性与收敛性,且数值格式的时间收敛阶和空间收敛阶分别是二阶和三阶.通过数值试验验证了数值格式的有效性和理论结果.     

随机微分方程欧拉格式算法分析

首先给出了线性随机微分方程的欧拉格式算法,然后给出了非线性随机微分方程变步长的欧拉格式算法,接着讨论了其对初值的连续依赖性和收敛性.     

Cahn-Hilliard方程的新型二阶稳定化半隐有限元方法

基于Crank-Nicolson/Adams-Bashforth离散,一种新型的二阶稳定化半隐有限元格式被建立用来求解Cahn-Hilliard方程.在此格式中,通过添加一个新型的二阶稳定项,得到一个满足离散的能量耗散定律的线性系统.空间离散考虑Galerkin有限元方法,从而获得时空全离散格式.算法的稳定性被考虑,同时给出相应的误差估计.理论结果表明,所提出的算法具有二阶精度.最后,数值算例验证所提算法的有效性.     

一维非线性Schrödinger 方程的两个无条件收敛的守恒紧致差分格式

本文对一维非线性 Schrödinger 方程给出两个紧致差分格式, 运用能量方法和两个新的分析技 巧证明格式关于离散质量和离散能量守恒, 而且在最大模意义下无条件收敛. 对非线性紧格式构造了 一个新的迭代算法, 证明了算法的收敛性, 并在此基础上给出一个新的线性化紧格式. 数值算例验证 了理论分析的正确性, 并通过外推进一步提高了数值解的精度.     

一维非线性Schrdinger方程的两个无条件收敛的守恒紧致差分格式

本文对一维非线性Schrdinger方程给出两个紧致差分格式,运用能量方法和两个新的分析技巧证明格式关于离散质量和离散能量守恒,而且在最大模意义下无条件收敛.对非线性紧格式构造了一个新的迭代算法,证明了算法的收敛性,并在此基础上给出一个新的线性化紧格式.数值算例验证了理论分析的正确性,并通过外推进一步提高了数值解的精度.     

对流占优扩散方程的特征线楔形基无网格法

本文研究了一维对流占优扩散方程的初边值问题.利用特征线法与楔形基无网格法,获得了特征线楔形基无网格显格式与隐格式算法.数值实验表明算法具有精度高、计算简单等优点.     

半无界非线性热传导方程的Laguerre拟谱方法

以Laguerre-Gauss-Radau节点为配置点,利用拟谱方法求数值解,逼近半无界非线性热传导方程非齐次Neumann边界条件的正确解.给出算法格式和相应的数值例子,表明所提算法格式的有效性和高精度.这里所用方法也可用于求解其他非线性问题.     

一类新的(2n-1)点二重动态逼近细分

利用正弦函数构造了一类新的带有形状参数ω的(2n-1)点二重动态逼近细分格式.从理论上分析了随n值变化时这类细分格式的C~k连续性和支集长度;算法的一个特色是随着细分格式中参数ω的取值不同,相应生成的极限曲线的表现张力也有所不同,而且这一类算法所对应的静态算法涵盖了Chaikin,Hormann,Dyn,Daniel和Hassan的算法.文末附出大量数值实例,在给定相同的初始控制顶点,且极限曲线达到同一连续性的前提下和现有几种算法做了比较,数值实例表明这类算法生成的极限曲线更加饱满,表现力更强.     

自适应隐式有限差分方法求解美式期权定价问题

本文针对美式期权的定价问题设计了基于有限差分方法的预估-校正数值算法.该算法采用显式离散格式先对自由边界条件进行预估,再对经过变量替换后的关于期权价格的偏微分方程采用隐式格式离散,并用Fourier方法分析了此离散格式的稳定性.接下来,引入基于Richardson外推法的后验误差指示子.这个后验误差指示子能够在给定的误差阈值范围内,针对期权价格和自由边界找到合适的网格划分.最后,通过设计多组数值实验并与Fazio^[1]采用显式离散格式算得的数值结果相比较,验证了所提算法的有效性,稳定性和收敛性.     

Hybrid Flow-Shop: a Memetic Algorithm Using Constraint-Based Scheduling for Efficient Search

The paper considers the hybrid flow-shop scheduling problem with multiprocessor tasks. Motivated by the computational complexity of the problem, we propose a memetic algorithm for this problem in the paper. We first describe the implementation details of a genetic algorithm, which is used in the memetic algorithm. We then propose a constraint programming based branch-and-bound algorithm to be employed as the local search engine of the memetic algorithm. Next, we present the new memetic algorithm. We lastly explain the computational experiments carried out to evaluate the performance of three algorithms (genetic algorithm, constraint programming based branch-and-bound algorithm, and memetic algorithm) in terms of both the quality of the solutions produced and the efficiency. These results demonstrate that the memetic algorithm produces better quality solutions and that it is very efficient.     

Constrained global optimization of multivariate polynomials using Bernstein branch and prune algorithm

We propose an algorithm for constrained global optimization to tackle non-convex nonlinear multivariate polynomial programming problems. The proposed Bernstein branch and prune algorithm is based on the Bernstein polynomial approach. We introduce several new features in this proposed algorithm to make the algorithm more efficient. We first present the Bernstein box consistency and Bernstein hull consistency algorithms to prune the search regions. We then give Bernstein contraction algorithm to avoid the computation of Bernstein coefficients after the pruning operation. We also include a new Bernstein cut-off test based on the vertex property of the Bernstein coefficients. The performance of the proposed algorithm is numerically tested on 13 benchmark problems. The results of the tests show the proposed algorithm to be overall considerably superior to existing method in terms of the chosen performance metrics.     

Augmented Lagrangian algorithms for linear programming

We introduce new augmented Lagrangian algorithms for linear programming which provide faster global convergence rates than the augmented algorithm of Polyak and Treti'akov. Our algorithm shares the same properties as the Polyak-Treti'akov algorithm in that it terminates in finitely many iterations and obtains both primal and dual optimal solutions. We present an implementable version of the algorithm which requires only approximate minimization at each iteration. We provide a global convergence rate for this version of the algorithm and show that the primal and dual points generated by the algorithm converge to the primal and dual optimal set, respectively.     

An Extension of Least Angle Regression Based on the Information Geometry of Dually Flat Spaces

We extend the least angle regression algorithm using the information geometry of dually flat spaces. The extended least angle regression algorithm is used for estimating parameters in generalized linear regression, and it can be also used for selecting explanatory variables. We use the fact that a model manifold of an exponential family is a dually flat space. In estimating parameters, curves corresponding to bisectors in the Euclidean space play an important role. Originally, the least angle regression algorithm is used for estimating parameters and selecting explanatory variables in linear regression. It is an efficient algorithm in the sense that the number of iterations is the same as the number of explanatory variables. We extend the algorithm while keeping this efficiency. However, the extended least angle regression algorithm differs significantly from the original algorithm. The extended least angle regression algorithm reduces one explanatory variable in each iteration while the original algorithm increases one explanatory variable in each iteration. We show results of the extended least angle regression algorithm for two types of datasets. The behavior of the extended least angle regression algorithm is shown. Especially, estimates of parameters become smaller and smaller, and vanish in turn.     

A simulated annealing driven multi-start algorithm for bound constrained global optimization

A derivative-free simulated annealing driven multi-start algorithm for continuous global optimization is presented. We first propose a trial point generation scheme in continuous simulated annealing which eliminates the need for the gradient-based trial point generation. We then suitably embed the multi-start procedure within the simulated annealing algorithm. We modify the derivative-free pattern search method and use it as the local search in the multi-start procedure. We study the convergence properties of the algorithm and test its performance on a set of 50 problems. Numerical results are presented which show the robustness of the algorithm. Numerical comparisons with a gradient-based simulated annealing algorithm and three population-based global optimization algorithms show that the new algorithm could offer a reasonable alternative to many currently available global optimization algorithms, specially for problems requiring ‘direct search’ type algorithm.     

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     

A fast computational algorithm for the Legendre-Fenchel transform

We investigate a fast algorithm, introduced by Brenier, which computes the Legendre-Fenchel transform of a real-valued function. We generalize his work to boxed domains and introduce a parameter in order to build an iterative algorithm. The new approach of separating primal and dual spaces allows a clearer understanding of the algorithm and yields better numerical behavior. We extend known complexity results and give new ones about the convergence of the algorithm.     

Prime witnesses in the Shor algorithm and the Miller-Rabin algorithm

We prove that prime witnesses in the Miller-Rabin algorithm coincide with those in the Shor algorithm which satisfy the condition of Fermat’s little theorem. We describe the set of natural numbers, whose prime witnesses in the Miller-Rabin algorithm coincide with those in the Shor algorithm. We find all such numbers less than 100,000,000 and experimentally study the rate of increase of the ratio of the quantity of such numbers to the quantity of Carmichael numbers.     

An Algorithm for Global Optimization using the Taylor–Bernstein Form as Inclusion Function

We investigate the use of higher order inclusion functions in the Moore–Skelboe (MS) algorithm of interval analysis (IA) for unconstrained global optimization. We first propose an improvement of the Taylor–Bernstein (TB) form given in (Lin and Rokne (1996) 101) which has the property of higher order convergence. We make the improvement so that the TB form is more effective in practice. We then use the improved TB form as an inclusion function in a prototype MS algorithm and also modify the cut-off test and termination condition in the algorithm. We test and compare on several examples the performances of the proposed algorithm, the MS algorithm, and the MS algorithm with the Taylor model of Berz and Hoffstatter (1998; 97) as inclusion function. The results of these (preliminary) tests indicate that the proposed algorithm with the improved TB form as inclusion function is quite effective for low to medium dimension problems studied.     

Searching for a counterfeit coin with b-balance

We consider the classical problem of searching for a heavier coin in a set of n coins, n-1 of which have the same weight. The weighing device is b-balance which is the generalization of two-arms balance. The minimum numbers of weighings are determined exactly for worst-case sequential algorithm, average-case sequential algorithm, worst-case predetermined algorithm, average-case predetermined algorithm.We also investigate the above search model with additional constraint: each weighing is only allowed to use the coins that are still in doubt. We present a worst-case optimal sequential algorithm and an average-case optimal sequential algorithm requiring the minimum numbers of weighings.