对称正定矩阵多级分裂预处理子

本文基于对称正定矩阵的多级分裂,讨论了这类方程组的多级分裂预处理子的构造,证明了预处理子的合理性.数值试验显示我们的预处理子是有效的.     

非重迭型区域分解预处理共轭梯度法

本文讨论含有内部交叉点(cross point)的非重迭型区域分解预处理共轭梯度法。称一个点是交叉点,如果有三个或三个以上的子区域以该点做为共同边界点,该点为区域内点。 本文根据在对称正定块对角矩阵类中对角块是对称正定矩阵比较有效的预处理器的理论,通过简单自然的刚度矩阵分裂,基于代数方式,构造了一类预处理器并给出了预处     

实对称正定Toeplitz矩阵的带位移的Sine预处理子

本文研究了求解实对称正定Toeplitz线性方程组的预处理共轭梯度法.基于实对称Toeplitz矩阵都有一个三角变换分裂(TTS)的事实,我们提出了带位移的Sine预处理子TS,分析了预处理矩阵的谱性质,并讨论了每步迭代的计算复杂度.数值实验表明该预处理子比T.Chan预处理子~([2])更有效.     

速度追踪问题中鞍点系统的新分裂迭代

 有限元离散一类速度追踪问题后得到具有鞍点结构的线性系统,针对该鞍点系统,本文提出了一种新的分裂迭代技术.证明了新的分裂迭代方法的无条件收敛性,详细分析了新的分裂预条件子对应的预处理矩阵的谱性质.数值结果验证了对于大范围的网格参数和正则参数,新的分裂预条件子在求解有限元离散速度追踪问题得到的鞍点系统时的可行性和有效性.     

速度追踪问题产生的鞍点系统的新的分裂迭代技术

有限元离散一类速度追踪问题后得到具有鞍点结构的线性系统,针对该鞍点系统,本文提出了一种新的分裂迭代技术.证明了新的分裂迭代方法的无条件收敛性,详细分析了新的分裂预条件子对应的预处理矩阵的谱性质.数值结果验证了对于大范围的网格参数和正则参数,新的分裂预条件子在求解有限元离散速度追踪问题得到的鞍点系统时的可行性和有效性.     

非埃米特正定Toeplitz矩阵的m—步预处理子（英文）

众所周知,如果A是Toeplitz矩阵,那么矩阵A有一循环与反循环分裂(记为CSCS)[7],可写为A=C+S,其中C为循环矩阵,S为反循环矩阵.本文针对某类Toeplitz矩阵,提出了一个m步的预处理子P_m,这个预处理子P_m是基于CSCS迭代方法构建的.本文中证明当C和S都是正定矩阵时,对于适当的m,预处理矩阵(P_m*A)**(P_m*A)的谱半径聚集于1.实验结果表明,对于适当的m,本文提出的预处理子优于T—Chan预处理子[3].     

椭圆型方程的并行迭代区域分裂法——多子区域情形

本文提出了一个有内交叉点的多子域区域分裂法。无交叉点的多子域分裂可归为两子域情形。在每一交叉点处取一子域覆盖之。称其为覆盖子域。不同交叉点的覆盖子域互不相交。本文的算法是把求解子区域上的Dirichlet问题,混合问题和覆盖子域上的Dirichlet问题相结合而得到的。利用了两子域Schwarz交替法和两子域并行迭代分裂法的思想。本算法具有高度并行性和通信局部性,适应于任意多个子区域的分裂。     

几乎各向同性的高维空间分数阶扩散方程的分块快速正则Hermite分裂预处理方法

一类空间分数阶扩散方程经过有限差分离散后所得到的离散线性方程组的系数矩阵是两个对角矩阵与Toeplitz型矩阵的乘积之和.在本文中,对于几乎各向同性的二维或三维空间分数阶扩散方程的离散线性方程组,采用预处理Krylov子空间迭代方法,我们利用其系数矩阵的特殊结构和具体性质构造了一类分块快速正则Hermite分裂预处理子.通过理论分析,我们证明了所对应的预处理矩阵的特征值大部分都聚集于1的附近.数值实验也表明,这类分块快速正则Hermite分裂预处理子可以明显地加快广义极小残量(GMRES)方法和稳定化的双共轭梯度(BiCGSTAB)方法等Krylov子空间迭代方法的收敛速度.     

广义鞍点问题的松弛维数分解预条件子

本文将Benzi等提出的松弛维数分解(Relaxed dimensionalfactorization, RDF)预条件子进一步推广到广义鞍点问题上,并称为GRDF(Generalized RDF)预条件子.该预条件子可看做是用维数分裂迭代法求解广义鞍点问题而导出的改进维数分裂(Modified dimensional split, MDS)预条件子的松弛形式, 它相比MDS预条件子更接近于系数矩阵, 因而结合Krylov子空间方法(如GMRES)有更快的收敛速度.文中分析了GRDF预处理矩阵特征值的一些性质,并用数值算例验证了新预条件子的有效性.     

关于H-矩阵的H-预处理子（英文）

设A为一实对称正定的严格对角占优矩阵.设A=D-B为A的Jacobi分裂.为了求解线性方程组Ax=b,在新提出的预处理子的基础上,我们采用预处理共轭梯度方法(PCG)来求解该问题.新提出的预处理子Pv=D+νvv~T,其中v=|B|e,e=(1,...,1)~T,ν=v~TBv/||v||_2~4,且ν使||cvv~T-B||_F达到极小.我们得到了预处理矩阵P_v~(-1)A特征值的上下界,它的界比JIN提出的预处理子的界简单紧凑.数值结果表明我们的预处理子的有效性.     

The Optimal Preconditioning in the Domain Decomposition Method for Wilson Element

1.TheCollstructionofPreconditionerLetfil)eapolygolldolllaillillR',feL'(fl).Consi(lertheholllogeneousDiricllletboulldaryvalueProblenlofPoissonequation,Assllmethat,fordomainfi,thereareacoarsersubdivisionTHwitllIneshsizeHalldananotheroneThwithmeshsizeh,whichisobtainedbyrefiningTH'Thebotllsubdivisionssatisfythequasi-uniformityandtheillversehypothesis.FOragivenelemelltT,Pm(T)dellotesthespaceofallpolynomialswiththedegreenotgreaterthanm,Qm(T)denotesthespaceofallpolynomialswiththedegreecorres…     

Preconditioning of the Stiffness Matrix of Local Refined Triangulation

A preconditioning method for the finite element stiffness matrix is given in this paper. The triangulation is refined in a subregion; the preconditioning process is composed of resolution of two regular subproblems; the condition number of the preconditioned matrix is O(1 logH/h), where H and h are mesh sizes of the unrefined and local refined triangulations respectively.     

A Decomposition Method for Global and Local Quadratic Minimization

We present a decomposition method for indefinite quadratic programming problems having n variables and m linear constraints. The given problem is decomposed into at most m QP subproblems each having m linear constraints and n-1 variables. All global minima, all isolated local minima and some of the non-isolated local minima for the given problem are obtained from those of the lower dimensional subproblems. One way to continue solving the given problem is to apply the decomposition method again to the subproblems and repeatedly doing so until subproblems of dimension 1 are produced and these can be solved directly. A technique to reduce the potentially large number of subproblems is formulated.     

An Integral Simplex Algorithm for Solving Combinatorial Optimization Problems

In this paper a local integral simplex algorithm will be described which, starting with the initial tableau of a set partitioning problem, makes pivots using the pivot on one rule until no more such pivots are possible because a local optimum has been found. If the local optimum is also a global optimum the process stops. Otherwise, a global integral simplex algorithm creates and solves the problems in a search tree consisting of a polynomial number of subproblems, subproblems of subproblems, etc. The solution to at least one of these subproblems is guaranteed to be an optimal solution to the original problem. If that solution has a bounded objective then it is an optimal set partitioning solution of the original problem, but if it has an unbounded objective then the original problem has no feasible solution. It will be shown that the total number of pivots required for the global integral simplex method to solve a set partitioning problem having m rows, where m is an arbitrary but fixed positive integer, is bounded by a polynomial function of n.A method for programming the algorithms in this paper to run on parallel computers is discussed briefly.     

An efficient solution method for Weber problems with barriers based on genetic algorithms

In this paper we consider the problem of locating one new facility with respect to a given set of existing facilities in the plane and in the presence of convex polyhedral barriers. It is assumed that a barrier is a region where neither facility location nor travelling are permitted. The resulting non-convex optimization problem can be reduced to a finite series of convex subproblems, which can be solved by the Weiszfeld algorithm in case of the Weber objective function and Euclidean distances. A solution method is presented that, by iteratively executing a genetic algorithm for the selection of subproblems, quickly finds a solution of the global problem. Visibility arguments are used to reduce the number of subproblems that need to be considered, and numerical examples are presented.     

A decomposition approach for global optimum search in QP,NLP and MINLP problems

Nonconvex programming problems are frequently encountered in engineering and operations research. A large variety of global optimization algorithms have been proposed for the various classes of programming problems. A new approach for global optimum search is presented in this paper which involves a decomposition of the variable set into two sets —complicating and noncomplicating variables. This results in a decomposition of the constraint set leading to two subproblems. The decomposition of the original problem induces special structure in the resulting subproblems and a series of these subproblems are then solved, using the Generalized Benders' Decomposition technique, to determine the optimal solution. The key idea is to combine a judicious selection of the complicating variables with suitable transformations leading to subproblems which can attain their respective global solutions at each iteration. Mathematical properties of the proposed approach are presented. Even though the proposed approach cannot guarantee the determination of the global optimum, computational experience on a number of nonconvex QP, NLP and MINLP example problems indicates that a global optimum solution can be obtained from various starting points.     

Column enumeration based decomposition techniques for a class of non-convex MINLP problems

We propose a decomposition algorithm for a special class of nonconvex mixed integer nonlinear programming problems which have an assignment constraint. If the assignment decisions are decoupled from the remaining constraints of the optimization problem, we propose to use a column enumeration approach. The master problem is a partitioning problem whose objective function coefficients are computed via subproblems. These problems can be linear, mixed integer linear, (non-)convex nonlinear, or mixed integer nonlinear. However, the important property of the subproblems is that we can compute their exact global optimum quickly. The proposed technique will be illustrated solving a cutting problem with optimum nonlinear programming subproblems.     

Simulated annealing with asymptotic convergence for nonlinear constrained optimization

In this paper, we present constrained simulated annealing (CSA), an algorithm that extends conventional simulated annealing to look for constrained local minima of nonlinear constrained optimization problems. The algorithm is based on the theory of extended saddle points (ESPs) that shows the one-to-one correspondence between a constrained local minimum and an ESP of the corresponding penalty function. CSA finds ESPs by systematically controlling probabilistic descents in the problem-variable subspace of the penalty function and probabilistic ascents in the penalty subspace. Based on the decomposition of the necessary and sufficient ESP condition into multiple necessary conditions, we present constraint-partitioned simulated annealing (CPSA) that exploits the locality of constraints in nonlinear optimization problems. CPSA leads to much lower complexity as compared to that of CSA by partitioning the constraints of a problem into significantly simpler subproblems, solving each independently, and resolving those violated global constraints across the subproblems. We prove that both CSA and CPSA asymptotically converge to a constrained global minimum with probability one in discrete optimization problems. The result extends conventional simulated annealing (SA), which guarantees asymptotic convergence in discrete unconstrained optimization, to that in discrete constrained optimization. Moreover, it establishes the condition under which optimal solutions can be found in constraint-partitioned nonlinear optimization problems. Finally, we evaluate CSA and CPSA by applying them to solve some continuous constrained optimization benchmarks and compare their performance to that of other penalty methods.     

An implicit finite volume method for the solution of 3D low Mach number viscous flows using a local preconditioning technique

This paper presents a cell-centered high order finite volume scheme for the solution of the three-dimensional (3D) Navier–Stokes equations with low Mach number. The system of non-linear equations is solved by means of a fully implicit pseudo-transient scheme. Each pseudo-time step is solved by a Newton-GMRes procedure. A local preconditioning technique is used to scale the speed of sound and to improve the system condition number for low Mach number and low cell Reynolds number. This preconditioning is applied to the AUSM+up flux vector splitting function. The method is tested on 2D and 3D low Mach number laminar flows.     

求解互补问题的一种序列二次规划方法

通过将互补问题转化为一种带非负约束的极小化问题 ,给出了求解互补问题的一种序列二次规划方法 .该方法中每一个子问题都是可解的 ,迭代产生的序列是非负的 ,在适当的条件下 ,分别证明了算法的全局收敛性、局部超线收敛性以及局部二次收敛性 .