优势关系下决策表的下近似约简方法研究

研究了优势关系下不协调决策表的下近似约简问题,引入新的下近似约简的定义,证明新的下近似约简与文献[7]定义的下近似约简等价。给出新的下近似约简的判定定理和辨识矩阵,与文献[7]的辨识矩阵相比,计算新的下近似约简的辨识矩阵的时间复杂度要低。因此,可以利用新的辨识矩阵来求决策表的下近似约简．     

Symmetric orthogonal approximation to symmetric tensors with applications to image reconstruction

The main objective of this paper is to study an approximation of symmetric tensors by symmetric orthogonal decomposition. We propose and study an iterative algorithm to determine a symmetric orthogonal approximation and analyze the convergence of the proposed algorithm. Numerical examples are reported to demonstrate the effectiveness of the proposed algorithm. We also apply the proposed algorithm to represent correlated face images. We demonstrate better face image reconstruction results by combining principal components and symmetric orthogonal approximation instead of combining principal components and higher‐order SVD results.     

进化泛函网络多维函数逼近理论及学习算法

提出了一种用于多维函数逼近的进化策略修正泛函网络基函数系数的新算法,并给出了其算法学习过程.利用进化策略的自适应性来确定基函数前的系数,改进了泛函网络的参数通过解方程组来得到这一传统方法.仿真结果表明,这种新的逼近算法简单可行,能够逼近给定的函数到预先给定的精度,具有较快的收敛速度和良好的逼近性能.     

A combined direction stochastic approximation algorithm

The stochastic approximation problem is to find some root or minimum of a nonlinear function in the presence of noisy measurements. The classical algorithm for stochastic approximation problem is the Robbins-Monro (RM) algorithm, which uses the noisy negative gradient direction as the iterative direction. In order to accelerate the classical RM algorithm, this paper gives a new combined direction stochastic approximation algorithm which employs a weighted combination of the current noisy negative gradient and some former noisy negative gradient as iterative direction. Both the almost sure convergence and the asymptotic rate of convergence of the new algorithm are established. Numerical experiments show that the new algorithm outperforms the classical RM algorithm.     

An algorithm for the quadratic approximation

The quadratic approximation is a three dimensional analogue of the two dimensional Padé approximation. A determinantal expression for the polynomial coefficients of the quadratic approximation is given. A recursive algorithm for the construction of these coefficients is derived. The algorithm constructs a table of quadratic approximations analogous to the Padé table of rational approximations.     

A Benson type algorithm for nonconvex multiobjective programming problems

In this paper, an approximation algorithm for solving nonconvex multiobjective programming problems (NCMOPs) is presented. We modify Benson’s method using cones instead of hyperplanes. This algorithm uses an inner approximation and an outer approximation to generate (weakly) efficient solutions and (weakly \(\varepsilon \)-) nondominated points of NCMOPs. Some numerical examples are presented to clarify the proposed algorithm.     

A numerical method of structure-preserving model updating problem and its perturbation theory

A method is presented to update a special finite element (FE) analytical model, based on matrix approximation theory with spectral constraint. At first, the model updating problem is treated as a matrix approximation problem dependent on the spectrum data from vibration test and modal parameter identification. The optimal approximation is the first modified solution of FE model. An algorithm is given to preserve the sparsity of the model by multiple correction. The convergence of the algorithm is investigated and perturbation of the modified solution is analyzed. Finally, a numerical example is provided to confirm the convergence of the algorithm and perturbation theory.     

Discrete linearized least-squares rational approximation on the unit circle

We already generalized the Rutishauser—Gragg—Harrod—Reichel algorithm for discrete least-squares polynomial approximation on the real axis to the rational case. In this paper, a new method for discrete least-squares linearized rational approximation on the unit circle is presented. It generalizes the algorithms of Reichel—Ammar—Gragg for discrete least-squares polynomial approximation on the unit circle to the rationale case. The algorithm is fast in the sense that it requires order m computation time where m is the number of data points and is the degree of the approximant. We describe how this algorithm can be implemented in parallel. Examples illustrate the numerical behavior of the algorithm.     

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.     

Binary weighted essentially non-oscillatory (BWENO) approximation

Weighted essentially non-oscillatory (WENO) schemes have been mainly used for solving hyperbolic partial differential equations (PDEs). Such schemes are capable of high order approximation in smooth regions and non-oscillatory sharp resolution of discontinuities. The base of the WENO schemes is a non-oscillatory WENO approximation procedure, which is not necessarily related to PDEs. The typical WENO procedures are WENO interpolation and WENO reconstruction. The WENO algorithm has gained much popularity but the basic idea of approximation did not change much over the years. In this paper, we first briefly review the idea of WENO interpolation and propose a modification of the basic algorithm. New approximation should improve basic characteristics of the approximation and provide a more flexible framework for future applications. New WENO procedure involves a binary tree weighted construction that is based on key ideas of WENO algorithm and we refer to it as the binary weighted essentially non-oscillatory (BWENO) approximation. New algorithm comes in a rational and a polynomial version. Furthermore, we describe the WENO reconstruction procedure, which is usually involved in the numerical schemes for hyperbolic PDEs, and propose the new reconstruction procedure based on the described BWENO interpolation. The obtained numerical results show that the newly proposed procedures perform very well on the considered test examples.     

NURBS曲线曲面拟合数据点的迭代算法

本文推广了文献[1]的结果,将文献[1]中关于B样条曲线曲面拟合数据点的迭代算法推广至有理形式,给出了无需求解方程组反求控制点及权因子即可得到拟合NURBS曲线曲面的迭代方法．该算法和文献[1]的算法本质上是统一的,而后者恰是前者的一种退化形式．文章还给出了收敛性证明以及一些定性分析．文末的数值实例说明该算法简单实用．     

求解阵列天线自适应滤波问题的一种调比随机逼近算法

提出了求解阵列天线自适应滤波问题的一种调比随机逼近算法.每一步迭代中,算法选取调比的带噪负梯度方向作为新的迭代方向.相比已有的其他随机逼近算法,这个算法不需要调整稳定性常数,在一定程度上解决了稳定性常数选取难的问题.数值仿真实验表明,算法优于已有的滤波算法,且比经典Robbins-Monro （RM）算法具有更好的稳定性.     

Parameter estimation of ordinary differential equations

This paper addresses the development of a new algorithm forparameter estimation of ordinary differential equations. Here,we show that (1) the simultaneous approach combined with orthogonalcyclic reduction can be used to reduce the estimation problemto an optimization problem subject to a fixed number of equalityconstraints without the need for structural information to devisea stable embedding in the case of non-trivial dichotomy and(2) the Newton approximation of the Hessian information of theLagrangian function of the estimation problem should be usedin cases where hypothesized models are incorrect or only a limitedamount of sample data is available. A new algorithm is proposedwhich includes the use of the sequential quadratic programming(SQP) Gauss–Newton approximation but also encompassesthe SQP Newton approximation along with tests of when to usethis approximation. This composite approach relaxes the restrictionson the SQP Gauss–Newton approximation that the hypothesizedmodel should be correct and the sample data set large enough.This new algorithm has been tested on two standard problems.     

A 2.75-approximation algorithm for the unconstrained traveling tournament problem

A 2.75-approximation algorithm is proposed for the unconstrained traveling tournament problem, which is a variant of the traveling tournament problem. For the unconstrained traveling tournament problem, this is the first proposal of an approximation algorithm with a constant approximation ratio. In addition, the proposed algorithm yields a solution that meets both the no-repeater and mirrored constraints. Computational experiments show that the algorithm generates solutions of good quality.     

积分波动率二阶变差估计量分析:鞍点算法

本文利用鞍点逼近方法对Black-Scholes模型的积分波动率的二阶变差估计量的估计误差进行分析,得到了相对于中心极限定理更为精细的结果,并且给出了逼近的鞍点算法。结果表明鞍点逼近是中心极限定理的纠正。模拟结果表明鞍点算法给出的估计误差分布相对于正态逼近更合理。该结果在对积分波动率进行统计假设检验时是有意义的。     

An approximation algorithm for the traveling tournament problem

This paper describes the traveling tournament problem, a well-known benchmark problem in the field of tournament timetabling. We propose a new lower bound for the traveling tournament problem, and construct a randomized approximation algorithm yielding a feasible solution whose approximation ratio is less than 2+(9/4)/(n−1), where n is the number of teams. Additionally, we propose a deterministic approximation algorithm with the same approximation ratio using a derandomization technique. For the traveling tournament problem, the proposed algorithms are the first approximation algorithms with a constant approximation ratio, which is less than 2+3/4.     

The spline curve,a smooth interpolating function used in numerical design of ship-lines

It has been found that a numerical approximation of a ship-designer's spline results in a smooth interpolating function. An algorithm which computes the function coefficients is presented in Algol. Methods to vary the stiffnes of the spline are included. A test of fairness is described and finally a more elaborate algorithm which leads to a closer approximation is outlined.     

Nonconvex Stochastic Optimization for Model Reduction

In this paper a global stochastic optimization algorithm, which is almost surely (a.s.) convergent, is applied to the model reduction problem. The proposed method is compared with the balanced truncation and Hankel norm approximation methods by examples in step responses and in approximation errors as well. Simulation shows that the proposed algorithm provides better results.     

A trust region method for solving linearly constrained locally Lipschitz optimization problems

In this paper, we present a nonsmooth trust region method for solving linearly constrained optimization problems with a locally Lipschitz objective function. Using the approximation of the steepest descent direction, a quadratic approximation of the objective function is constructed. The null space technique is applied to handle the constraints of the quadratic subproblem. Next, the CG-Steihaug method is applied to solve the new approximation quadratic model with only the trust region constraint. Finally, the convergence of presented algorithm is proved. This algorithm is implemented in the MATLAB environment and the numerical results are reported.     

UPGMA clustering revisited: A weight-driven approach to transitive approximation

A new algorithm is proposed for generating min-transitive approximations of a given similarity matrix (i.e. a symmetric matrix with elements in the unit interval and diagonal elements equal to one). Different approximations are generated depending on the choice of an aggregation operator that plays a central role in the algorithm. If the maximum operator is chosen, then the approximation coincides with the min-transitive closure of the given similarity matrix. In case of the arithmetic mean, a transitive approximation is generated which is, on the average, as close to the given similarity matrix as the approximation generated by the UPGMA hierarchical clustering algorithm. The new algorithm also allows to generate approximations in a purely ordinal setting. As this new approach is weight-driven, the partition tree associated to the corresponding min-transitive approximation can be built layer by layer. Numerical tests carried out on synthetic data are used for comparing different approximations generated by the new algorithm with certain approximations obtained by classical methods.