混合层无粘稳定性分析的Legendre级数解

基于泛函分析中的不动点理论,采用不动点方法首次获得混合层无粘线性稳定性方程的显式Legendre级数解,该级数解在整个无界流动区域内一致有效．现有基于传统摄动法得到的无界流动区域一致有效解仅适用于长波扰动和中性扰动两种特殊情况,而使用不动点方法可以得到所有不稳定扰动波数的特征解．另外,在不动点方法框架下,扰动相速度和扰动增长率可根据方程的可解性条件来唯一确定．为了验证该方法的有效性,将该方法和现有文献中的数值计算结果相比较,对比结果表明该方法具有精度高、收敛快等优点．     

Solution of the least squares method problem of pairwise comparison matrices

The aim of the paper is to present a new global optimization method for determining all the optima of the Least Squares Method (LSM) problem of pairwise comparison matrices. Such matrices are used, e.g., in the Analytic Hierarchy Process (AHP). Unlike some other distance minimizing methods, LSM is usually hard to solve because of the corresponding nonlinear and non-convex objective function. It is found that the optimization problem can be reduced to solve a system of polynomial equations. Homotopy method is applied which is an efficient technique for solving nonlinear systems. The paper ends by two numerical example having multiple global and local minima. This research was supported in part by the Hungarian Scientific Research Fund, Grant No. OTKA K 60480.     

Modeling incompressible flows using a finite particle method

This paper describes the applications of a finite particle method (FPM) to modeling incompressible flow problems. FPM is a meshfree particle method in which the approximation of a field variable and its derivatives can be simultaneously obtained through solving a pointwise matrix equation. A set of basis functions is employed to obtain the coefficient matrix through a sequence of transformations. The finite particle method can be used to discretize the Navier–Stokes equation that governs fluid flows. The incompressible flows are modeled as slightly compressible via specially selected equations of state. Four numerical examples including the classic Poiseuille flow, Couette flow, shear driven cavity and a dam collapsing problem are presented with comparisons to other sources. The numerical examples demonstrate that FPM is a very attractive alternative for simulating incompressible flows, especially those with free surfaces, moving interfaces or deformable boundaries.     

Analysis of the Structured Total Least Squares Problem for Hankel/Toeplitz Matrices

The Structured Total Least Squares (STLS) problem is a natural extension of the Total Least Squares (TLS) approach when structured matrices are involved and a similarly structured rank deficient approximation of that matrix is desired. In many of those cases the STLS approach yields a Maximum Likelihood (ML) estimate as opposed to, e.g., TLS.In this paper we analyze the STLS problem for Hankel matrices (the theory can be extended in a straightforward way to Toeplitz matrices, block Hankel and block Toeplitz matrices). Using a particular parametrisation of rank-deficient Hankel matrices, we show that this STLS problem suffers from multiple local minima, the properties of which depend on the parameters of the new parametrisation. The latter observation makes initial estimates an important issue in STLS problems and a new initialization method is proposed. The new initialization method is applied to a speech compression example and the results confirm the improved performance compared to other previously proposed initialization methods.     

Multigrid and M-Matrices in the Finite Pointset Method

We consider the Finite Pointset Method (FPM) for incompressible flows. In the classical FPM derivatives are approximated by a least squares approximation. In general this approach yields stencils with both positive and negative entries. We present how optimization routines can force the stencils to have only positive weights aside from the central point. This approach yields an M-matrix structure, which is of interest for various linear solvers. We investigate algebraic multigrid to solve the arising linear systems. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Application of the Finite Pointset Method (FPM) to the kinetic BGK model

The BGK model of rarefied gas dynamics [1] is solved numerically by using the Finite Pointset Method (FPM) [2], which is a particle method developed at the ITWM Kaiserslautern. For the implementation a semilagrangian scheme [3] is used. Numerical results are shown on the example of a Shock tube problem for different Knudsen numbers. The solutions are compared to the solutions of exact Euler in the case of small Knudsen numbers and to DSMC solutions for higher Knudsen numbers. (© 2012 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

基于不动点方法求解非线性Falkner-Skan流动方程

Falkner-Skan流动方程描述绕楔面的流动,该方程具有很强的非线性.首先通过引入变换式,将原半无限大区域上的流动问题转化为有限区间上的两点边值问题.接着基于泛函分析中的不动点理论,采用不动点方法求解两点边值问题从而得到Falkner Skan流动方程的解.最后将不动点方法给出的结果和文献中的数值结果相比较,发现不动点方法得到的结果具有很高的精度,并且解的精度很容易通过迭代而不断得到提高.表明不动点方法是一种求解非线性微分方程行之有效的方法.     

Prioritisation of an IT budget within a local authority

This paper describes the prioritisation of an IT budget within a department of a local authority. The decision problem is cast as a simple multiattribute evaluation but from two perspectives. First, as an exercise in group decision making. Here the emphasis is on a shared process wherein the object is to obtain consensus. The use of an explicit evaluation framework and the ability to interact with the evaluation data in real time via a simple spreadsheet model were found to improve the decision making. Second, the prioritisation is made analytically. The motivation is to determine the degree to which the rankings are the result of the structural characteristics of the projects themselves rather than of the differences in importance attached to the achievement of the goals represented by the project attributes. Three methods are used: Monte Carlo simulation of ranks, cluster analysis based on attributes and an approach based on entropy maximisation. It is found that in the case studied the structure inherent in the data is high and so the results of the analyses are robust. Finally, a procedure is suggested for the appropriate use of these analyses via a facilitator to aid prioritisation decisions.     

Semidefinite programming approach for the quadratic assignment problem with a sparse graph

The matching problem between two adjacency matrices can be formulated as the NP-hard quadratic assignment problem (QAP). Previous work on semidefinite programming (SDP) relaxations to the QAP have produced solutions that are often tight in practice, but such SDPs typically scale badly, involving matrix variables of dimension \(n^2\) where n is the number of nodes. To achieve a speed up, we propose a further relaxation of the SDP involving a number of positive semidefinite matrices of dimension \(\mathcal {O}(n)\) no greater than the number of edges in one of the graphs. The relaxation can be further strengthened by considering cliques in the graph, instead of edges. The dual problem of this novel relaxation has a natural three-block structure that can be solved via a convergent Alternating Direction Method of Multipliers in a distributed manner, where the most expensive step per iteration is computing the eigendecomposition of matrices of dimension \(\mathcal {O}(n)\). The new SDP relaxation produces strong bounds on quadratic assignment problems where one of the graphs is sparse with reduced computational complexity and running times, and can be used in the context of nuclear magnetic resonance spectroscopy to tackle the assignment problem.     

The structured total least‐squares approach for non‐linearly structured matrices

In this paper, an extension of the structured total least‐squares (STLS) approach for non‐linearly structured matrices is presented in the so‐called ‘Riemannian singular value decomposition’ (RiSVD) framework. It is shown that this type of STLS problem can be solved by solving a set of Riemannian SVD equations. For small perturbations the problem can be reformulated into finding the smallest singular value and the corresponding right singular vector of this Riemannian SVD. A heuristic algorithm is proposed. Some examples of Vandermonde‐type matrices are used to demonstrate the improved accuracy of the obtained parameter estimator when compared to other methods such as least squares (LS) or total least squares (TLS). Copyright © 2002 John Wiley & Sons, Ltd.     

An intelligent system for prioritisation of organ transplant patient waiting lists using fuzzy logic

The objective of this paper is to investigate the effectiveness of using fuzzy logic in a complex decision-making capacity, and in particular, for the prioritisation of kidney transplant recipients. Fuzzy logic is an extension to Boolean logic allowing an element to have degrees of true and false as opposed to being either 100% true or 100% false. Thus, it can account for the ‘shades of grey’ found in many real-world situations. In this paper, two fuzzy logic models are developed demonstrating its effectiveness as a model for vastly improving the current prioritisation system used in the UK and abroad. The first model converts an element of the current kidney transplant prioritisation system used in the UK into fuzzy logic. The result is an improvement to the current system and a demonstration of fuzzy logic as an effective decision-making approach. The second model offers an alternative prioritisation system to overcome the limitations of the current system both in the UK and abroad, as brought up by research reviewed in this paper. The current UK transplant prioritisation system, adapted in the first model, uses objective criteria (age of recipient, waiting time, etc) as inputs into the decision-making process. This alternative model takes advantage of the facility for infinitely varying inputs into fuzzy logic and a system is developed that can handle subjective (humanistic) criteria (pain level, quality of life, etc) that are key to arriving at such important decisions. Furthermore, the model is highly flexible allowing any number of criteria to be used and the individual characteristics of each criterion to be altered. The result is a model that utilises the scope of fuzzy logic's flexibility, usability and effectiveness in the field of decision-making and a transplant prioritisation method vastly superior to the original system, which is constrained by its use of only objective criteria. The ‘humanistic’ model demonstrates the ability of fuzzy logic to consider subjective and complex criteria. However, the criteria used are not intended to be exhaustive. It is simply a template to which medical professionals can apply limitless additional criteria. The model is produced as an alternative to any current national system. However, the model can also be used by individual hospitals to decide initially whether a patient should be placed on the transplant or surgery waiting list. The model can be further adapted and used for the transplant of other organs or similar decisions in medicine. Concurrently with the research and work carried out to develop the two models the investigation focused on the constraints of the current systems used in the UK and the US and the seemingly impossible dilemmas experienced by those having to make the prioritisation decisions. By removing the parameters of objective-only inputs the ‘humanistic’ model eradicates the previous limitations on decision-making.     

Bi-criteria evolution strategy in estimating weights from the AHP ratio-scale matrices

The problem of deriving weights from ratio-scale matrices in an analytic hierarchy process (AHP) is addressed by researchers worldwide. There are various ways to solve the problem that are generally grouped into simple matrix and optimization methods. All methods have received criticism regarding the accuracy of derived weights, and different criteria are in use to compare the weights obtained from different methods. Because the set of Pareto non-dominated solutions (weights) is unknown and for inconsistent matrices is indefinite, a bi-criterion optimization approach is proposed for manipulating such matrices. The problem-specific evolution strategy algorithm (ESA) is implemented for a robust stochastic search over a feasible indefinite solution space. The fitness function is defined as a scalar vector function composed of the common error measure, i.e. the Euclidean distance and a minimum violation error that accounts for no violation of the rank ordering. The encoding scheme and other components of the search engine are adjusted to preserve the imposed constraints related to the required normalized values of the weights. The solutions generated by the proposed approach are compared with solutions obtained by five well-known prioritization techniques for three judgment matrices taken from the literature. In these and other test applications, the prioritization method that uses the entitled weights estimation by evolution strategy algorithm (WEESA) appears to be superior to other methods if only two, the most commonly used methods, are applied: the Euclidean distance and minimum violation exclusion criteria.     

A time-domain decomposition iterative method for the solution of distributed linear quadratic optimal control problems

We study a class of time-domain decomposition-based methods for the numerical solution of large-scale linear quadratic optimal control problems. Our methods are based on a multiple shooting reformulation of the linear quadratic optimal control problem as a discrete-time optimal control (DTOC) problem. The optimality conditions for this DTOC problem lead to a linear block tridiagonal system. The diagonal blocks are invertible and are related to the original linear quadratic optimal control problem restricted to smaller time-subintervals. This motivates the application of block Gauss–Seidel (GS)-type methods for the solution of the block tridiagonal systems. Numerical experiments show that the spectral radii of the block GS iteration matrices are larger than one for typical applications, but that the eigenvalues of the iteration matrices decay to zero fast. Hence, while the GS method is not expected to convergence for typical applications, it can be effective as a preconditioner for Krylov-subspace methods. This is confirmed by our numerical tests.A byproduct of this research is the insight that certain instantaneous control techniques can be viewed as the application of one step of the forward block GS method applied to the DTOC optimality system.     

Polynomial time solvability of non-symmetric semidefinite programming

In this paper, we consider semidefinite programming with non-symmetric matrices, which is called non-symmetric semidefinite programming (NSDP). We convert such a problem into a linear program over symmetric cones, which is polynomial time solvable by interior point methods. Thus, the NSDP problem can be solved in polynomial time. Such a result corrects the corresponding result given in the literature. Similar methods can be applied to nonlinear programming with non-symmetric matrices.     

关于用拉格朗日乘子法求解线性等式约束最小二乘问题

本文讨论用拉格朗日乘子法求解线性等式约束最小二乘问题(简称 LSE 问题)的优点.应用此法能细致地讨论约束条件与变量之间的关系,据此并可证明 LSE 问题与某一个无约束最小二乘问题的等价性.此外,尚可得到参数和拉格朗日乘子的协方差矩阵.最后给出一个数值稳定的解 LSE 问题的算法.     

Separating doubly nonnegative and completely positive matrices

The cone of Completely Positive (CP) matrices can be used to exactly formulate a variety of NP-Hard optimization problems. A tractable relaxation for CP matrices is provided by the cone of Doubly Nonnegative (DNN) matrices; that is, matrices that are both positive semidefinite and componentwise nonnegative. A natural problem in the optimization setting is then to separate a given DNN but non-CP matrix from the cone of CP matrices. We describe two different constructions for such a separation that apply to 5 × 5 matrices that are DNN but non-CP. We also describe a generalization that applies to larger DNN but non-CP matrices having block structure. Computational results illustrate the applicability of these separation procedures to generate improved bounds on difficult problems.     

On the properties of matrices defining some classes of BVMs

Summary It is known that the matrices defining the discrete problem generated by a k-step Boundary Value Method (BVM) have a quasi-Toeplitz band structure [7]. In particular, when the boundary conditions are skipped, they become Toeplitz matrices. In this paper, by introducing a characterization of positive definiteness for such matrices, we shall prove that the Toeplitz matrices which arise when using the methods in the classes of BVMs known as Generalized BDF and Top Order Methods have such property. Mathematics Subject Classification (2000):65L06, 47B35, 15A48Work supported by G.N.C.S.     

Exploiting structure in parallel implementation of interior point methods for optimization

OOPS is an object-oriented parallel solver using the primal–dual interior point methods. Its main component is an object-oriented linear algebra library designed to exploit nested block structure that is often present in truly large-scale optimization problems such as those appearing in Stochastic Programming. This is achieved by treating the building blocks of the structured matrices as objects, that can use their inherent linear algebra implementations to efficiently exploit their structure both in a serial and parallel environment. Virtually any nested block-structure can be exploited by representing the matrices defining the problem as a tree build from these objects. OOPS can be run on a wide variety of architectures and has been used to solve a financial planning problem with over 10⁹ decision variables. We give details of supported structures and their implementations. Further we give details of how parallelisation is managed in the object-oriented framework.