A new third-order family of nonlinear solvers for multiple roots

In this paper, a new family of third-order methods for finding multiple roots of nonlinear equations has been introduced. This family requires one-function and two-derivative evaluation per iteration. The family contains several known third-order methods, as special cases. Some examples are presented to show the performance of the presented family.     

A family of simultaneous methods for the determination of polynomial complex zeros

Using the development of a rational function by elementary fractions, a family of methods for the simultaneous determination of polynomial complex zeros is derived. All the methods of the family are cubically convergent for simple zeros. The known simultaneous procedures of the third order are included. The presented class of iteration functions is suitable for the parallel inclusion of polynomial complex zeros by circular regions. The family of methods, defined in complex circular arithmetic, gives a new interval method with cubic convergence. Numerical example is given.     

3D-line clipping algorithms — a comparative study

Some well-known line-polyhedron intersection methods are summed up and new accelerating modifications presented. Results of comparison of known and newly developed methods are included. New methods use the fact that each line can be described as the intersection of two planes.     

A combined approach to the solution to the general one-dimensional cutting stock problem

In this article a combined method for the solution to the general one-dimensional cutting stock problem (G1D-CSP) is proposed. The main characteristic of G1D-CSP lies in that all stock lengths can be different. The new approach combines two existing methods: sequential heuristic procedure (SHP) and branch-and-bound. The algorithm based on the proposed method leads to almost optimal solutions, which are substantially better than the solutions of known methods at the expense of slightly increased time complexity, which is still low. So, the new method is suitable for all sizes of the problem. A comparison with the SHP is presented.     

Process Optimization under Insufficient Experimental Information in the Phase of Service

The existing methods of process optimization under uncertain initial information are based on the assumption that in the phase of service known are the exact values of all parameters, which in the phase of design were regarded as partially uncertain. This assumption is too rigid and in practice often is not true. The paper presented new flexibility conditions and a new two-phase problem of optimization with the assumption that in the phase of service the precise values are known only for part of the uncertain parameters. An algorithm was developed to solve the two-phase problem for the case of insufficient experimental information in the process service phase.__________Translated from Avtomatika i Telemekhanika, No. 8, 2005, pp. 3–21.Original Russian Text Copyright © 2005 by Volin, Ostrovskii.     

基于核空间中最优变换和聚类中心的鉴别特征提取

应用统计学习理论中的核化原理,可以将许多线性特征提取算法推广至非线性特征提取算法.提出了基于核化原理的最优变换与聚类中心算法,即通过非线性变换,将数据映射到高维核空间,应用最优变换算法,实现原空间数据的非线性特征提取,而求解过程却借助"核函数",回避了复杂非线性变换的具体表达形式.新算法可提取稳健的非线性鉴别特征,从而解决复杂分布数据的模式分类问题.大量数值实验表明新算法比传统的最优变换与聚类中心算法更有效,甚至优于经典的核Fisher判别分析.     

General variational approach to the interpolation problem

The Talmi and Gilat variational approach to the interpolation problem in arbitrary dimension is presented together with the corresponding physical model. The connection of this approach to some known spline methods is demonstrated and new interpolation functions are derived for one-, two- and three-dimensional cases. They are designed to be flexible through the use of meaningful parameters and to give good approximations of both the function itself and its derivatives as well.     

A cyclic block-tridiagonal solver

A simple algorithm for solving a cyclic block-tridiagonal system of equations is presented. Introducing a special form of a new variable, the system is split into two block-tridiagonal systems, which can be solved by known methods. Implementation details of the algorithm are discussed and numerical examples of diagonal and random generated systems are presented.     

A unified framework for the construction of various matrix multisplitting iterative methods for large sparse system of linear equations

A unified framework for the construction of various synchronous and asynchronous parallel matrix multisplitting iterative methods, suitable to the SIMD and MIMD multiprocessor systems, respectively, is presented, and its convergence theory is established under rather weak conditions. These afford general method models and systematical convergence criterions for studying the parallel iterations in the sense of matrix multisplitting. In addition, how the known parallel matrix multisplitting iterative methods can be classified into this new framework, and what novel ones can be generated by it are shown in detail.     

Ideal state reconstructor for deterministic digital control systems

A new state reconstructor for deterministic digital control systems is presented which is ideal in the following sense: if the plant parameters are known exactly, the output of the new state reconstructor will exactly equal the true state of the plant, not just approximate it. Furthermore, this ideal state reconstructor adds no additional states or eigenvalues to the system, nor does it affect the plant equation for the system in any way; it affects only the measurement equation. While there are countless ways of choosing the ideal state reconstructor parameters, two distinct methods are described here. An example is presented which illustrates the procedures for completely designing the ideal state reconstructor using both methods.     

Some fourth-order nonlinear solvers with closed formulae for multiple roots

In this paper, we present six new fourth-order methods with closed formulae for finding multiple roots of nonlinear equations. The first four of them require one-function and three-derivative evaluation per iteration. The last two require one-function and two-derivative evaluation per iteration. Several numerical examples are given to show the performance of the presented methods compared with some known methods.     

基于粗糙集理论的属性约简算法研究

数据挖掘是近年来数据库领域中出现的一个新兴研究热点,它是从大量数据中获取知识。进行数据挖掘的方法很多,粗糙集方法便是其中的主要方法之一。属性约简算法是基于粗糙集理论的数据挖掘模型中的关键步骤,同时也是粗糙集理论研究中的一个研究重点。通过对粗糙集理论的属性约简算法的深入研究,本文提出了一种改进的属性约简启发式算法。该算法建立在可辨识矩阵计算基础上。改进算法基于Hu的算法与Jelonek算法,在计算可辨识矩阵的基础上,保证最终能够找到决策信息系统的一个约简,同时较Jelonek算法相比,运算时间明显减少。     

计算椭圆曲线上多标量乘的快速算法

椭圆曲线密码体制最主要的运算就是椭圆曲线上的标量乘和多标量乘,在各种密码协议中起到了核心作用.文中设计了多个整数的一种新的联合带符号二进制表示的编码算法,它每次最多处理相邻的两列,因此在实现上是简单而快速的;在此基础上提出了计算椭圆曲线上多标量乘的一个新算法,并对这个算法进行了分析,最后将新算法和已有多标量乘算法进行了比较,指出新算法在一般情况下(m3时)效率可提高7%～15%.     

Efficient two-step derivative-free iterative methods with memory and their dynamics

In this paper, we present a family of three-parameter derivative-free iterative methods with and without memory for solving nonlinear equations. The convergence order of the new method without memory is four requiring three functional evaluations. Based on the new fourth-order method without memory, we present a family of derivative-free methods with memory. Using three self-accelerating parameters, calculated by Newton interpolatory polynomials, the convergence order of the new methods with memory are increased from 4 to 7.0174 and 7.5311 without any additional calculations. Compared with the existing methods with memory, the new method with memory can obtain higher convergence order by using relatively simple self-accelerating parameters. Numerical comparisons are made with some known methods by using the basins of attraction and through numerical computations to demonstrate the efficiency and the performance of the presented methods.     

UNIFIED DECISION COMBINATION FRAMEWORK

Pattern recognition researchers are discovering that a judicious combination of classifiers, generally outperforms a single one. In this paper, we present a unified framework for decision combination. By looking at the combination problem from this new perspective, we gain an intuitive, perhaps better understanding of some of the known algorithms. A new parameterized combination method (pooled ranking figure of merit) is presented which is shown to be equivalent to three of the standard combination methods. Furthermore, our new decision combination method provides newer combination methods that provide interesting tradeoffs. These ideas are supported by simulation experiments.     

A new solution for path planning in partially known or unknown environment for nonholonomic mobile robots

This paper presents the theoretical analysis of different methods, which can be used in online path generation for mobile robots with nonholonomic constraints in a partially known workspace. Then the new method is introduced which works very fast and gives the optimal path in a complex environment. The algorithm of the presented method is based on A¹ graph searching with the nodes placed in the discretized configuration space. This paper is focused on the analysis of different heuristic cost functions and introduces a new statement of this function. The presented method is equipped with the procedures of fast path replanning — very useful in partially known workspaces. The series of simulation tests and experimental results of online control for car-like robot are also discussed.     

A truly meshless pre- and post-processor for meshless analysis methods

In recent years, meshless methods have been developed to eliminate the known drawbacks in finite element methods. Generating the input file for a meshless method and interpreting the output obtained can be difficult without graphical pre-processing and post-processing support. Unfortunately, most existing pre- and post-processing techniques are based on using an underlying finite element mesh or finite difference grid. Since meshless methods have neither, new approaches are required for providing this support for meshless methods. In this paper, a pre-processor and a post-processor are presented for the meshless method using node-based and pixel-based approaches as opposed to an element-based approach. Pre-processing supports for automated generation of nodes, support domains, and sub-domains along with local refining are also included. An extensive example is presented to demonstrate the effectiveness of the given pre-processor and post-processor.     

Solving the quadratic assignment problem with clues from nature

This paper describes a new evolutionary approach to solving quadratic assignment problems. The proposed technique is based loosely on a class of search and optimization algorithms known as evolution strategies (ES). These methods are inspired by the mechanics of biological evolution and have been applied successfully to a variety of difficult problems, particularly in continuous optimization. The combinatorial variant of ES presented here performs very well on the given test problems as compared with the standard 2-Opt heuristic and results with simulated annealing and tabu search. Extensions for practical applications in factory layout are described.     

Affine Structure and Motion from Points,Lines and Conics

In this paper several new methods for estimating scene structure and camera motion from an image sequence taken by affine cameras are presented. All methods can incorporate both point, line and conic features in a unified manner. The correspondence between features in different images is assumed to be known.Three new tensor representations are introduced describing the viewing geometry for two and three cameras. The centred affine epipoles can be used to constrain the location of corresponding points and conics in two images. The third order, or alternatively, the reduced third order centred affine tensors can be used to constrain the locations of corresponding points, lines and conics in three images. The reduced third order tensors contain only 12 components compared to the 16 components obtained when reducing the trifocal tensor to affine cameras.A new factorization method is presented. The novelty lies in the ability to handle not only point features, but also line and conic features concurrently. Another complementary method based on the so-called closure constraints is also presented. The advantage of this method is the ability to handle missing data in a simple and uniform manner. Finally, experiments performed on both simulated and real data are given, including a comparison with other methods.     

A Newton-based heuristic algorithm for multi-objective flexible job-shop scheduling problem

We propose a new hierarchical heuristic algorithm for multi-objective flexible job-shop scheduling problems. The proposed method is an adaptation of the Newton’s method for continuous multi-objective unconstrained optimization problems, belonging to the class of multi-criteria descent methods. Numerical experiments with the proposed method are presented. The potential of the proposed method is demonstrated by comparing the obtained results with the known results of existing methods that solve the same test instances.