A technique for speeding up the solution of the Lagrangean dual

We propose techniques for the solution of the LP relaxation and the Lagrangean dual in combinatorial optimization and nonlinear programming problems. Our techniques find the optimal solution value and the optimal dual multipliers of the LP relaxation and the Lagrangean dual in polynomial time using as a subroutine either the Ellipsoid algorithm or the recent algorithm of Vaidya. Moreover, in problems of a certain structure our techniques find not only the optimal solution value, but the solution as well. Our techniques lead to significant improvements in the theoretical running time compared with previously known methods (interior point methods, Ellipsoid algorithm, Vaidya's algorithm). We use our method to the solution of the LP relaxation and the Langrangean dual of several classical combinatorial problems, like the traveling salesman problem, the vehicle routing problem, the Steiner tree problem, thek-connected problem, multicommodity flows, network design problems, network flow problems with side constraints, facility location problems,K-polymatroid intersection, multiple item capacitated lot sizing problem, and stochastic programming. In all these problems our techniques significantly improve the theoretical running time and yield the fastest way to solve them.     

Solving the stochastic steady-state diffusion problem using multigrid

Darran Furnival ^{We study multigrid for solving the stochastic steady-state diffusionproblem. We operate under the mild assumption that the diffusioncoefficient takes the form of a finite Karhunen-Loèveexpansion. The problem is discretized using a finite-elementmethodology using the polynomial chaos method to discretizethe stochastic part of the problem. We apply a multigrid algorithmto the stochastic problem in which the spatial discretizationis varied from grid to grid while the stochastic discretizationis held constant. We then show, theoretically and experimentally,that the convergence rate is independent of the spatial discretization,as in the deterministic case, and the stochastic discretization.}     

On a class of Szász-Mirakyan type operators

The actual construction of the Szász-Mirakyan operators and its various modifications require estimations of infinite series which in a certain sense restrict their usefulness from the computational point of view. Thus the question arises whether the Szász-Mirakyan operators and their generalizations cannot be replaced by a finite sum. In connection with this question we propose a new family of linear positive operators.     

多项式分裂可行问题

本文研究多项式分裂可行问题,即由多项式不等式定义的分裂可行问题,包括凸与非凸、可行与不可行的问题;给出多项式分裂可行问题解集的半定松弛表示;研究其半定松弛化问题的性质;并基于这些性质建立求解多项式分裂可行问题的半定松弛算法.本文在较为一般的条件下证明了,如果分裂可行问题有解,则可通过本文建立的算法求得一个解点;如果问题...     

On multilevel iterative methods for optimization problems

This paper is concerned with multilevel iterative methods which combine a descent scheme with a hierarchy of auxiliary problems in lower dimensional subspaces. The construction of auxiliary problems as well as applications to elasto-plastic model and linear programming are described. The auxiliary problem for the dual of a perturbed linear program is interpreted as a dual of perturbed aggregated linear program. Coercivity of the objective function over the feasible set is sufficient for the boundedness of the iterates. Equivalents of this condition are presented in special cases.Supported by NSF under grant DMS-8704169, AFOSR under grant 86-0126, and ONR under Contract N00014-83-K-0104. Consulting for American Airlines Decision Technologies, MD 2C55, P.O. Box 619616, DFW, TX 75261-9616, USA.Supported by NSF under grant DMS-8704169 and AFOSR under grant 86-0126.     

Multigrid Waveform Relaxation for Anisotropic Partial Differential Equations

Multigrid waveform relaxation provides fast iterative methods for the solution of time-dependent partial differential equations. In this paper we consider anisotropic problems and extend multigrid methods developed for the stationary elliptic case to waveform relaxation methods for the time-dependent parabolic case. We study line-relaxation, semicoarsening and multiple semicoarsening multilevel methods. A two-grid Fourier–Laplace analysis is used to estimate the convergence of these methods for the rotated anisotropic diffusion equation. We treat both continuous time and discrete time algorithms. The results of the analysis are confirmed by numerical experiments.     

求解Oseen流的交替线松弛多重网格方法

利用Riemann解的通量差分分裂法——Godunov方法对Oseen流控制方程进行离散,得到了基于一阶上迎风格式的离散方程,并给出了使用多重网格方法求解该离散方程的V 循环算法和W-循环算法的收敛性分析.通过局部Fourier分析方法,对获得的离散方程的聚对称交替线Gauss-Seidel松弛的光滑性质进行了研究.结果表明：使用多重网格的两层网格及三层网格算法求解具有不同Reynolds数的Oseen流,即便是在高Reynolds数情况下,聚对称交替线Gauss-Seidel松弛具有很好的光滑性质,多重网格W-循环算法收敛性比V-循环算法好.     

关于多重网格并行计算中拟边界Jacobi成份的影响

1．引言分布式存储并行计算环境中,高效率的获取一般通过区域分解或数据分割实现大粒度并行[4]．因此,对于有效求解偏微分方程的多重网格算法[1,6],并行计算均采用网格划分进行任务分配[5],实现大粒度并行．其中,松弛算子并行度是影响算法并行效率的关键因素．Gauss－SeidellGS）点或块松弛、ILU松弛和适合于方程组的分布式GS松弛（DGS）[1,6]为多重网格算法的有效松弛算子,但本质上都是串行的．尽管采用红黑（RB）序可增强并行度,但每次松弛在每层网格上仍需两次数据交换门（即所有子网格相互交换拟边界数据）．为了减少通…     

非参数局部多项式回归估计的最优子抽样算法

随着科学技术的发展,虽然人们提高了收集和处理数据的能力,但仍存在一些大数据集超出了现有计算机的计算能力.目前,抽取一部分样本来替代全样本进行建模计算是减轻计算负担的一种方法.大数据背景下线性模型的子抽样方法已经得到了相对成熟的研究,在减轻计算量方面获得了很大的优势.文章将线性模型下的子抽样方法推广到非参数回归模型,并推...     

矩阵特征多项式的图论计算公式

给出了赋权有向图邻接矩阵特征多项式的图论计算公式,从而得到了一般矩阵特征多项式的图论计算方法,并且研究了赋权有向图邻接矩阵特征多项式和谱半径的一些性质．