Descent Direction Stochastic Approximation Algorithm with Adaptive Step Sizes

A stochastic approximation (SA) algorithm with new adaptive step sizes for solving unconstrained minimization problems in noisy environment is proposed. New adaptive step size scheme uses ordered statistics of fixed number of previous noisy function values as a criterion for accepting good and rejecting bad steps. The scheme allows the algorithm to move in bigger steps and avoid steps proportional to $1/k$ when it is expected that larger steps will improve the performance. An algorithm with the new adaptive scheme is defined for a general descent direction. The almost sure convergence is established. The performance of new algorithm is tested on a set of standard test problems and compared with relevant algorithms. Numerical results support theoretical expectations and verify efficiency of the algorithm regardless of chosen search direction and noise level. Numerical results on problems arising in machine learning are also presented. Linear regression problem is considered using real data set. The results suggest that the proposed algorithm shows promise.     

An enhanced finite difference time domain method for two dimensional Maxwell's equations

An enhanced finite-difference time-domain (FDTD) algorithm is built to solve the transverse electric two-dimensional Maxwell's equations with inhomogeneous dielectric media where the electric fields are discontinuous across the dielectric interface. The new algorithm is derived based upon the integral version of the Maxwell's equations as well as the relationship between the electric fields across the interface. To resolve the instability issue of Yee's scheme (staircasing) caused by discontinuous permittivity across the interface, our algorithm revises the permittivities and makes some corrections to the scheme for the cells around the interface. It is also an improvement over the contour-path effective permittivity algorithm by including some extra terms in the formulas. The scheme is validated in solving the scattering of a dielectric cylinder with exact solution from Mie theory and is then compared with the above contour-path method, the usual staircasing and the volume-average method. The numerical results demonstrate that the new algorithm has achieved significant improvement in accuracy over other methods. Furthermore, the algorithm has a simple structure and can be merged into current FDTD software packages easily. The C++ source code for this paper is provided as supporting information for public access.     

Particle swarm with equilibrium strategy of selection for multi-objective optimization

A new ranking scheme based on equilibrium strategy of selection is proposed for multi-objective particle swarm optimization (MOPSO), and the preference ordering is used to identify the “best compromise” in the ranking stage. This scheme increases the selective pressure, especially when the number of objectives is very large. The proposed algorithm has been compared with other multi-objective evolutionary algorithms (MOEAs). The experimental results indicate that our algorithm produces better convergence performance.     

基于分段常值水平集的抛物型方程的参数识别算法

研究了线性抛物型方程不连续参数的识别算法.根据原有算法对于加噪观测数据计算不收敛的问题,本文基于分段常值水平集方法,根据水平集函数和优化过程的特点,修正原有Uzawa型算法中的带有总变差(TV)正则化的极小化模型和对常值向量的极小化模型,并且利用分裂Bregman迭代算法处理TV范数的优越性,构造一种新的参数识别算法格式.数值实验结果显示,新算法具有计算时间短、精度高、抗噪性强的优点.     

An Improved Linearity-Preserving Cell-Centered Scheme for Nonlinear Diffusion Problems on General Meshes

In this paper, we suggest a new vertex interpolation algorithm to improve an existing cell-centered finite volume scheme for nonlinear diffusion problems on general meshes. The new vertex interpolation algorithm is derived by applying a special limit procedure to the well-known MPFA-O method. Since the MPFA-O method for 3D cases has been addressed in some studies, the new vertex interpolation algorithm can be extended to 3D cases naturally. More interesting is that the solvability of the corresponding local system is proved under some assumptions. Additionally, we modify the edge flux approximation by an edge-based discretization of diffusion coefficient, and thus the improved scheme is free of the so-called numerical heat-barrier issue suffered by many existing cell-centered or hybrid schemes. The final scheme allows arbitrary continuous or discontinuous diffusion coefficients and can be applicable to arbitrary star-shaped polygonal meshes. A second-order convergence rate for the approximate solution and a first-order accuracy for the flux are observed in numerical experiments. In the comparative experiments with some existing vertex interpolation algorithms, the new algorithm shows obvious improvement on highly distorted meshes.     

The convergence of a new parallel algorithm for the Navier–Stokes equations

This paper deals with the convergence and stability of a new parallel algorithm and the error estimates for a particular case of the new parallel algorithm, which is used to solve the incompressible nonstationary Navier–Stokes equations. The theoretical results show that the scheme is (at least) conditionally stable and convergent.     

A fast non-iterative numerical algorithm to predict unsteady partial cavitation on hydrofoils

A new algorithm to predict partial sheet cavity behavior on hydrofoils is proposed. The proposed algorithm models the unsteady partial cavitation using Boundary Element Method (BEM). In the proposed method the spatial iterative scheme is removed by means of a new approach determining the instantaneous cavity length. This iterative scheme is required in conventional algorithms to obtain the cavity length at each time step. Performance of the new algorithm for various unsteady cavitating flows with different reduced frequencies, cavitation numbers, hydrofoil geometries and inflow conditions are investigated. Comparison between the obtained results using the proposed method and those of conventional ones indicates that the present algorithm works well with sufficient accuracy. Moreover, it is shown that the proposed method is computationally more efficient than the conventional one for unsteady sheet cavitation analysis on hydrofoils.     

Adaptive stochastic approximation algorithm

In this paper, stochastic approximation (SA) algorithm with a new adaptive step size scheme is proposed. New adaptive step size scheme uses a fixed number of previous noisy function values to adjust steps at every iteration. The algorithm is formulated for a general descent direction and almost sure convergence is established. The case when negative gradient is chosen as a search direction is also considered. The algorithm is tested on a set of standard test problems. Numerical results show good performance and verify efficiency of the algorithm compared to some of existing algorithms with adaptive step sizes.     

ERROR ESTIMATES FOR SPARSE OPTIMAL CONTROL PROBLEMS BY PIECEWISE LINEAR FINITE ELEMENT APPROXIMATION

Optimization problems with L¹-control cost functional subject to an elliptic partial differential equation(PDE)are considered.However,different from the finite dimensiona l¹-regularization optimization,the resulting discretized L¹norm does not have a decoupled form when the standard piecewise linear finite element is employed to discretize the continuous problem.A common approach to overcome this difficulty is employing a nodal quadrature formula to approximately discretize the L¹-norm.In this paper,a new discretized scheme for the L¹-norm is presented.Compared to the new discretized scheme for L¹-norm with the nodal quadrature formula,the advantages of our new discretized scheme can be demonstrated in terms of the order of approximation.Moreover,finite element error estimates results for the primal problem with the new discretized scheme for the L¹-norm are provided,which confirms that this approximation scheme will not change the order of error estimates.To solve the new discretized problem,a symmetric Gauss-Seidel based majorized accelerated block coordinate descent(sGS-mABCD)method is introduced to solve it via its dual.The proposed sGS-mABCD algorithm is illustrated at two numerical examples.Numerical results not only confirm the finite element error estimates,but also show that our proposed algorithm is efficient.     

Convergence of hybrid viscosity and steepest-descent methods for pseudocontractive mappings and nonlinear Hammerstein equations

In this article, we first introduce an iterative method based on the hybrid viscosity approximation method and the hybrid steepest-descent method for finding a fixed point of a Lipschitz pseudocontractive mapping (assuming existence) and prove that our proposed scheme has strong convergence under some mild conditions imposed on algorithm parameters in real Hilbert spaces. Next, we introduce a new iterative method for a solution of a nonlinear integral equation of Hammerstein type and obtain strong convergence in real Hilbert spaces. Our results presented in this article generalize and extend the corresponding results on Lipschitz pseudocontractive mapping and nonlinear integral equation of Hammerstein type reported by some authors recently. We compare our iterative scheme numerically with other iterative scheme for solving non-linear integral equation of Hammerstein type to verify the efficiency and implementation of our new method.     

A staggered-grid numerical algorithm for the extended Boussinesq equations

A second-order accurate numerical scheme is developed to solve Nwogu’s extended Boussinesq equations. A staggered-grid system is introduced with the first-order spatial derivatives being discretized by the fourth-order accurate finite-difference scheme. For the time derivatives, the fourth-order accurate Adams predictor–corrector method is used. The numerical method is validated against available analytical solutions, other numerical results of Navier–Stokes equations, and experimental data for both 1D and 2D nonlinear wave transformation problems. It is shown that the new algorithm has very good conservative characteristics for mass calculation. As a result, the model can provide accurate and stable results for long-term simulation. The model has proven to be a useful modeling tool for a wide range of water wave problems.     

项目鲁棒调度的资源分配启发式算法研究

合理的资源配置是提高项目调度鲁棒性一种有效的方法。本文针对项目鲁棒调度问题,提出了Max-PRUA资源分配启发式算法,以期通过生成鲁棒性高的资源分配方案来提高调度计划的鲁棒性。本算法设计了最大化利用优先关系和不可避免弧传递资源的资源分配两项策略来传递最大资源量,以减少由额外约束传递的资源量,降低对项目调度鲁棒性的影响。为寻优最优资源分配方案,配合局部搜索算法,本算法构建了动态活动组GRA,通过对组内活动顺序重排以生成多种资源分配方案,以利于从解空间中寻优出最佳的鲁棒性方案。最后通过大量的仿真实验验证和与其它算法进行比较,结果表明本算法对于不同规模和不同因素影响的项目均有较好的适应性,生成的资源分配方案对调度计划鲁棒性影响较小,是一种有效的算法。     

A discrete particle swarm optimization for lot-streaming flowshop scheduling problem

We consider an n-job, m-machine lot-streaming problem in a flowshop with equal-size sublots where the objective is to minimize the total weighted earliness and tardiness. To solve this problem, we first propose a so-called net benefit of movement (NBM) algorithm, which is much more efficient than the existing linear programming model for obtaining the optimal starting and completion times of sublots for a given job sequence. A new discrete particle swarm optimization (DPSO) algorithm incorporating the NBM algorithm is then developed to search for the best sequence. The new DPSO improves the existing DPSO by introducing an inheritance scheme, inspired by a genetic algorithm, into particles construction. To verify the proposed DPSO algorithm, comparisons with the existing DPSO algorithm and a hybrid genetic algorithm (HGA) are made. Computational results show that the proposed DPSO algorithm with a two-point inheritance scheme is very competitive for the lot-streaming flowshop scheduling problem.     

求解二维浅水波方程的旋转混合格式北大核心CSCD

针对二维浅水波方程数值求解问题,构造了一种旋转通量混合格式.空间方向上,该算法利用浅水波方程通量函数的旋转不变性,在单元界面法线方向及单元界面切线方向上采用可消除红斑现象的HLL与满足热力学第二定律的熵稳定加权混合数值通量函数,时间方向上采用三阶强稳定Runge-Kutta法.数值结果表明,该混合格式对于二维浅水波方程数值求解具有分辨率高的良好特性.     

一种新型的三维半解析数值算法

在三维空间,结合有限元线法与有限层法的思想,构造了一种新型的半解析数值算法,数值结果表明该方法具有较高的精度,切实可行。     

一种灵活的基于身份的签名方案

在基于身份的密钥提取过程中,使密钥生成器在私钥中嵌入随机数,从而使得密钥提取具有较好的灵活性,使得用户对一个身份可具备多个私钥,这无疑会增加密钥使用的安全性;基于这种新的密钥提取思路,给出一个基于身份的签名体制,新的密钥提取方式使得它具有更好的安全性和灵活性;新的基于身份的签名体制中具有最少对运算,因此,与类似的方案相比,其具备较好的计算效率;新签名体制的安全性依赖于k-合谋攻击问题(k-CAAP)的困难性,其在适应性选择消息和ID攻击下具备强不可伪造性,并且其安全性证明具有紧规约性.     

A numerical approach for a semilinear parabolic equation with a nonlocal boundary condition

A semilinear reaction-diffusion problem with a nonlocal boundary condition is studied. This paper presents a new and very easy implementable numerical algorithm for computations. This is based on a suitable linearization in time and on the principle of linear superposition. Any method for the space discretization (FEM was taken in this analysis) can be chosen. The derived algorithm is implicit and it does not need any iteration scheme to get a solution with the nonlocal boundary condition. Stability analysis has been performed and the optimal error estimates have been derived. Numerical results have been compared with other known techniques.     

An algorithm for large scale 0–1 integer programming with application to airline crew scheduling

We present an approximation algorithm for solving large 0–1 integer programming problems whereA is 0–1 and whereb is integer. The method can be viewed as a dual coordinate search for solving the LP-relaxation, reformulated as an unconstrained nonlinear problem, and an approximation scheme working together with this method. The approximation scheme works by adjusting the costs as little as possible so that the new problem has an integer solution. The degree of approximation is determined by a parameter, and for different levels of approximation the resulting algorithm can be interpreted in terms of linear programming, dynamic programming, and as a greedy algorithm. The algorithm is used in the CARMEN system for airline crew scheduling used by several major airlines, and we show that the algorithm performs well for large set covering problems, in comparison to the CPLEX system, in terms of both time and quality. We also present results on some well known difficult set covering problems that have appeared in the literature.     

A CELL-CENTERED ALE METHOD WITH HLLC-2D RIEMANN SOLVER IN 2D CYLINDRICAL GEOMETRY

This paper presents a second-order direct arbitrary Lagrangian Eulerian (ALE) method for compressible flow in two-dimensional cylindrical geometry.This algorithm has half-face fluxes and a nodal velocity solver,which can ensure the compatibility between edge fluxes and the nodal flow intrinsically.In two-dimensional cylindrical geometry,the control vol-ume scheme and the area-weighted scheme are used respectively,which are distinguished by the discretizations for the source term in the momentum equation.The two-dimensional second-order extensions of these schemes are constructed by employing the monotone up-wind scheme of conservation law (MUSCL) on unstructured meshes.Numerical results are provided to assess the robustness and accuracy of these new schemes.     

A New Multichannel Recursive Least Squares Algorithm for Very Robust and Efficient Adaptive Filtering

In this paper, a new multichannel recursive least squares (MRLS) adaptive algorithm is presented which has a number of very interesting properties. The proposed computational scheme performs adaptive filtering via the use of a finite window, where the burdening past information is dropped directly by means of a generalized inversion lemma; consequently, the proposed algorithm has excellent tracking abilities and very low misjudgment. Moreover, the scheme presented here, due to its particular structure and to the proper choice of mathematical definitions behind it, is very robust; i.e., it is less sensitive in the finite precision numerical error generation and propagation. Also, the new algorithm can be parallelized via a simple technique and its parallel form and, when executed with four processors, is faster than all the already existing schemes that perform both infinite and finite window multichannel adaptive filtering. Finally, due to the particular structure of this scheme and to the intrinsic flexibility in the choice of the window length, the proposed algorithm can act as a full substitute of the infinite window MRLS ones.