基于CPLEX的原始——对偶嵌套分解算法

本文介绍了一种求解大规模下三角结构线性规划问题的原始一对偶嵌套分解算法，并以CPLEX9.0作为核心求解器将算法实现。原始—对偶嵌套分解算法将原问题分解成一系列子问题，每个子问题既可以收到来自前一阶段子问题的价格信息，又可以收到来自后一阶段子问题的资源信息，较传统嵌套分解算法具有更加平衡的信息传递方式和良好的收敛性。实验数据表明，该算法在求解较大规模、稀疏度较小、耦合度较小的下三角结构线性规划问题时，相比单纯形法，在时间效率上有明显提高。     

两阶段特殊结构混合0-1规划的分解算法

本文介绍了一种用于求解具有特殊结构的两阶段混合0-1规划问题的原始-对偶分解算法,并以CPLEX软件作为核心求解器将算法实现.该算法将原问题分解成两个相对简单的子问题,较传统分解算法有更平衡的分解结构和收敛性.实验数据表明,该算法在求解较大规模、稀疏度较大、耦合度较大的复杂两阶段下三角结构混合0-1规划问题时,相比CPLEX提供的分枝剪枝法,在时间效率上有明显提高.算法最后通过固定0-1变量的取值可以得到满足管理精度要求的近似最优解.     

基于线性规划核心矩阵的单纯形算法

本文讨论了线性规划中的核心矩阵及其特性,探讨了利用核心矩阵实现单纯形算法的可能性,并进一步提出了一个基于核心矩阵的两阶段原始一对偶单纯形方法,该方法通过原始和对偶两个阶段的迭代,可以在有限次迭代中收敛到原问题的最优解或证明问题无解或无界．在试验的22个问题中,该算法的计算效率总体优于基于传统单纯形方法的MINOS软件．     

基于线性规划核心矩阵的单线形算法

本文讨论了线性规划中的核心矩阵及其特性,探讨了利用核心矩阵实现单纯形算法的可能性,并刊一步提出了一个基于核心矩阵的两阶段原始－对偶单纯形方法,该方法通过原始和对偶两个阶段的迭代,可以在有限次迭代中收敛到原问题的最优解或证明问题无解或无界。在试验的２２个问题中,该算法的计算效率总体优于基于传统单纯形方法的ＭＩＮＯＳ软件。     

基于最陡边规则的亏基对偶Ⅰ阶段算法

将摄动算法和亏基原始单纯形算法相结合,采用最陡边的列主元规则,以充分发挥这两种算法的优势,从而为亏基对偶单纯形算法提供一个新的I阶段算法,以使其进一步克服了退化所带来的困扰.初步的数值试验表明,所提出的算法能有效地减少总迭代次数,其效率不仅远远优于传统的原始两阶段单纯形算法,且优于原有的亏基原始单纯形算法,是一个非常吸引人而充满希望的新尝试.     

Broyden修正算法

对于求解非线性方程组F (x) =0的Broyden秩1方法的计算格式提出一种修正算法,尝试利用矩阵的奇异值分解求解迭代方程组,并且配合使用加速技巧,从而大大提高了算法的安全性和收敛速度.数值算例表明了新算法的有效性.     

一类无结构三角网上抛物方程的有限差分区域分解算法

本文讨论了一类在无结构三角网上数值求解二维热传导方程的有限差分区域分解算法．在这个算法中,将通过引进两类不同类型的内界点,将求解区域分裂成若干子区域．一旦内界点处的值被计算出来,其余子区域上的计算可完全并行．本文得到了稳定性条件和最大模误差估计,它表明我们的格式有令人满意的稳定性和较高的收敛阶．     

非线性不等式约束最优化一个超线性与二次收敛的强次可行方法

本文讨论非线性不等式约束最优化问题，借助于序列线性方程组技术和强次可行方法思想，建立了问题的一个初始点任意的快速收敛新算法．在每次迭代中，算法只需解一个结构简单的线性方程组．算法的初始迭代点不仅可以是任意的，而且不使用罚函数和罚参数，在迭代过程中，迭代点列的可行性单调不减．在相对弱的假设下，算法具有较好的收敛性和收敛速度，即具有整体与强收敛性，超线性与二次收敛性．文中最后给出一些数值试验结果．     

求解反应扩散对流问题的并行块单调迭代算法

考虑求解一类非线性反应扩散对流方程的块单调迭代算法,其中包括传统的块Picard,块Jacobi,以及在区域分解算法中常用的并行Schwarz算法.所讨论的算法可从问题的一个上解和下解出发,产生一个上解迭代序列和下解迭代序列并单调收敛于离散问题的解.这类算法的优点在于算法的并行结构好且可直接通过所产生的上解和下解迭代序列,得到迭代解的最大模误差界.在理论上,得到了算法的单调收敛性、线性与超线性收敛性.     

热传导方程的一类新型重叠型并行区域分解有限差分算法

0引言随着大规模科学工程计算的发展和计算精度要求的提高,区域分解和并行计算的发展越来越受到人们的重视.区域分解方法把复杂或大型的问题分解成若干重叠或非重叠子区域上的子问题,再在子区域上利用各种算法求解子问题.借助于区域分解,各子区域之间的计算可以并行,这引起了人们的研究兴趣和极大的应用前景.重叠型区域分解法的原始思想来源于Schwarz交替法.近年来建立在Schwarz交替法基础上的区域分解法在理论分析和实际应用中取得令人注目的发展,已成为一种有效的迭代方法.经典的Schwarz交替法本质上是串行的.随着并行计算的发展,出现了多种可完全并行化的Schwarz算法     

Long-step primal-dual target-following algorithms for linear programming

In this paper we propose a long-step target-following methodology for linear programming. This is a general framework, that enables us to analyze various long-step primal-dual algorithms in the literature in a short and uniform way. Among these are long-step central and weighted path-following methods and algorithms to compute a central point or a weighted center. Moreover, we use it to analyze a method with the property that starting from an initial noncentral point, generates iterates that simultaneously get closer to optimality and closer to centrality.This work is completed with the support of a research grant from SHELL.The first author is supported by the Dutch Organization for Scientific Research (NWO), grant 611-304-028.The fourth author is supported by the Swiss National Foundation for Scientific Research, grant 12-34002.92.     

Trefftz,collocation, and other boundary methods—A comparison

In this article we survey the Trefftz method (TM), the collocation method (CM), and the collocation Trefftz method (CTM). We also review the coupling techniques for the interzonal conditions, which include the indirect Trefftz method, the original Trefftz method, the penalty plus hybrid Trefftz method, and the direct Trefftz method. Other boundary methods are also briefly described. Key issues in these algorithms, including the error analysis, are addressed. New numerical results are reported. Comparisons among TMs and other numerical methods are made. It is concluded that the CTM is the simplest algorithm and provides the most accurate solution with the best numerical stability. © 2006 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2007     

Volume preserving RK methods for linear systems

1. IntroductionIn recent yearss there has been a great interest in constructing numerical integrationschemes for ODEs in such a way that some qualitative geometrical properties of the solutionof the ODEs are exactly preserved. R.th[ll and Feng Kang[2'31 has proposed symplectic algorithms for Hamiltollian systems, and since then st ruct ure s- preserving me t ho ds fordynamical systems have been systematically developed[4--7]. The symplectic algorithms forHamiltonian systems, the volume-pre…     

求解离散不适定问题的正则化GMERR方法

迭代极小残差方法是求解大型线性方程组的常用方法, 通常用残差范数控制迭代过程.但对于不适定问题, 即使残差范数下降, 误差范数未必下降. 对大型离散不适定问题,组合广义最小误差(GMERR)方法和截断奇异值分解(TSVD)正则化方法, 并利用广义交叉校验准则(GCV)确定正则化参数,提出了求解大型不适定问题的正则化GMERR方法.数值结果表明, 正则化GMERR方法优于正则化GMRES方法.     

s个几乎相等的素数的k次方和(Ⅰ)

假定pθ‖k,当p=2,2|k时，γ=θ 2；其它情况时，γ=θ 1。而R＝П(p-1)|kp^γ。本文在GRH（广义Riemann假设下），证明了当s=2^k 1,1≤k≤11时，任何足够大的整N≡s(modR)都可以表示为s个几乎相等的素数的k次方程。     

A note on the biasing of Newton's direction

This note deals with the geometric interpretation of the Levenberg-Marquardt search direction when the augmented Hessian is not positive definite.     

Diagonalized multiplier methods and quasi-Newton methods for constrained optimization

Two approaches to quasi-Newton methods for constrained optimization problems inR ⁿ are presented. These approaches are based on a class of Lagrange multiplier approximation formulas used by the author in his previous work on Newton's method for constrained problems. The first approach is set in the framework of a diagonalized multiplier method. From this point of view, a new update rule for the Lagrange multipliers which depends on the particular quasi-Newton method employed is given. This update rule, in contrast to most other update rules, does not require exact minimization of the intermediate unconstrained problem. In fact, the optimal convergence rate is attained in the extreme case when only one step of a quasi-Newton method is taken on this intermediate problem. The second approach transforms the constrained optimization problem into an unconstrained problem of the same dimension.The author would like to thank J. Moré and M. J. D. Powell for comments related to the material in Section 13. He also thanks J. Nocedal for the computer results in Tables 1–3 and M. Wright for the results in Table 4, which were obtained via one of her general programs. Discussions with M. R. Hestenes and A. Miele regarding their contributions to this area were very helpful. Many individuals, including J. E. Dennis, made useful general comments at various stages of this paper. Finally, the author is particularly thankful to R. Byrd, M. Heath, and R. McCord for reading the paper in detail and suggesting many improvements.This work was supported by the Energy Research and Development Administration, Contract No. E-(40-1)-5046, and was performed in part while the author was visiting the Department of Operations Research, Stanford University, Stanford, California.     

投入产出技术在计划平衡中的理论与应用

在用投入产出技术作计划平衡时，目前一般采用最终产品法、总产品法及国民收入法等．本文从理论上研究了这些方法的可行性问题，并在此基础上提出一个较理想的综合法．最后附有实例并说明综合法的现实意义．     

A comparison of some ODE solvers which require Jacobian evaluations

A variety of third-order ODE solvers which have a minimum configuration (i.e. minimum work per step) have been numerically tested and the results compared. They include implicit and explicit processes, and share the property that a Jacobian matrix must be evaluated at least once during the integration. Some of these processes have not been previously described in the literature.     

一种求解鞍点问题的广义对称超松弛迭代法

本文研究了鞍点问题的迭代算法.利用新的待定参数加速迭代格式并结合SSOR分裂的方法,获得了有两个参数的广义对称超松弛迭代法及其收敛性条件.数值例子表明选择适当的参数值可以提高算法的收敛效率,推广和改进了SOR-like迭代法.