多背包问题的半定松驰算法

The multiple knapsack problem denoted by MKP (B,S,rn,n) can be defined as follows. A set B of n items and a set S of rn knapsacks are given such that each item j has a profit pi and weight wj,and each knapsack i has a capacity Ci. The goal is to find a subset of items of maximum profit such that they have a feasible packing in the knapsacks. MKP (B,S,m,n) is strongly NP-Complete and no polynomial time approximation algorithm can have an approximation ratio better than 0.5. In the last ten years,semi-definite programming has been empolyed to solve some combinatorial problems successfully. This paper firstly presents a semi-definite relaxation algorithm (MKPS) for MKP (B,S,rn,n). It is proved that MKPS have a approximation ratio better than 0. 5 for a subclass of MKP (B,S,m,n) with n≤100, m≤5 and max^nj=1{wj}/min^mi=1={Ci}≤2/3.     

加速松驰迭代法的最优因子

本文定义了加速松驰迭代法的最优因子，并就具有相容次序且对角线上元素全不为零矩阵得到了最优因子的表达式，最后就本文的结论好于Ｇ．Ａｖｄｃｌａｓ＆Ａ．Ｈａｄｊｉｄｉｍｏｓ的结果给出了实例。     

关于位移线性方程组的加速超松弛迭代算法

本文研究关于系数矩阵为位移埃尔米特和位移反埃尔米特矩阵的复线性方程组的简便而有效的分裂迭代算法及其收敛性质.由于复系数线性方程组的系数矩阵由实部和虚部组成,运用松弛加速技术,我们得到了求解位移线性方程组的加速超松弛迭代算法,并分析了这类算法的收敛性质.数值算例表明,这类加速超松弛迭代算法是可行且有效的.     

关于并行迭代区域分解算法的松弛因子

1引言考虑二阶椭圆型Dirichlet边值问题的弱形式,求u∈H_0~1(Ω)使得a(u,v)=(f,v),(?) v∈H_0~1(Ω),(1)其中Ω是平面多角形区域,f∈L~2(Ω),(f,v)=∫_Ωfvdx,a(u,v)=∫_Ω(sum from i,j=1 to 2 a_(ij)(?)u/(?)x_i(?)等 a_0uv)dx,其中[a_(ij)]在Ω上对称一致正定,a_(ij)在Ω上分片连续有界,a_0≥0．由Lax-Milgram引理,问题(1)在H_0~1(Ω)中有唯一解．     

无严格互补松驰条件的序列线性方程组新算法

该文通过构造特殊形式的有效集来逼近KKT点处的有效集，给出了一个任意初始点下的序列线性方程组新算法，并证明了该算法在没有严格互补松驰条件的情况下具有全局收敛性和一步超线性收敛性。      

关于USSOR迭代收敛的充要条件和最佳松驰因子

本文在线性方程组系数矩阵A为相容次序矩阵及A的Jacobi迭代矩阵的特征值μj均为实数的条件下,得出了USSOR迭代法收敛的充分必要性定理,并给出了USSOR迭代矩阵之谱半径ρ（φw,w^-)的表达式及ρ（φw,w^-)的最佳松驰因子。     

一类极限循环连分式的加速收敛因子

本文获得了一类极限循环连分式的加速收敛因子,证明了它们具有良好的加速收敛性质.     

关于USSOR迭代法收敛的充要条件和最佳松弛因子

本文在线性方程组系数矩阵A为相容次序矩阵及A的Jacobi迭代矩阵的特征值μj均为实数的条件下,得出了USSOR迭代法收敛的充分必要性定理.并给出了USSOR迭代矩阵之谱半径ρ(ψω,-ω)的表达式及ρ(ψω,-ω)的最佳松弛因子.     

PSD方法的最优因子及效率分析

在系数矩阵是相容序2循环阵的情况下，本文给出了PSD方法的最优松弛参数和最优收敛因子，分析和讨论了它的实用性，并进而得到了一个新的迭代法，它的最优收敛因子与PSD方法一样，而迭代参数却只有一个．     

A New Relaxation Space for Obstacles

The space of obstacles (i.e. p-quasi upper semicontinuous functions) is endowed with a distance which is topologically equivalent to the -convergence. We find the metric completion of this space and we give some application for minimization problems of cost functionals depending on obstacles via their level sets. An element of the completion is a decreasing and _p -continuous on the left mapping Rt _t , where _t are positive Borel measures vanishing on sets of zero p-capacity.     

不重叠型Schwarz交替法的加速收敛

Matsokin与Nepomnyaschikh所提出的不重叠型S交替法的算法中不含有松弛因子，我们知道它有与h无关的几何收敛速度，但由于不含算法参数，该算法不能根据具体的情况加速收敛，本文提出加速收敛算法，我们在原算法的基础上引入两个松弛因子θ2，θ2并证明了除了例外均可实现加速收敛，θ1=θ^-1，θ2=θ^-2是满足均衡条件的最佳松弛因子，最后的算例表明该加速算法的有效性。     

On the Surrogate Gradient Algorithm for Lagrangian Relaxation

When applied to large-scale separable optimization problems, the recently developed surrogate subgradient method for Lagrangian relaxation (Zhao et al.: J. Optim. Theory Appl. 100, 699–712, 1999) does not need to solve optimally all the subproblems to update the multipliers, as the traditional subgradient method requires. Based on it, the penalty surrogate subgradient algorithm was further developed to address the homogenous solution issue (Guan et al.: J. Optim. Theory Appl. 113, 65–82, 2002; Zhai et al.: IEEE Trans. Power Syst. 17, 1250–1257, 2002). There were flaws in the proofs of Zhao et al., Guan et al., and Zhai et al.: for problems with inequality constraints, projection is necessary to keep the multipliers nonnegative; however, the effects of projection were not properly considered. This note corrects the flaw, completes the proofs, and asserts the correctness of the methods. This work is supported by the NSFC Grant Nos. 60274011, 60574067, the NCET program (No. NCET-04-0094) of China. The third author was supported in part by US National Science Foundation under Grants ECS-0323685 and DMI-0423607.     

Overlapping Schwarz Waveform Relaxation for the Heat Equation in N Dimensions

We analyze overlapping Schwarz waveform relaxation for the heat equation in n spatial dimensions. We prove linear convergence of the algorithm on unbounded time intervals and superlinear convergence on bounded time intervals. In both cases the convergence rates are shown to depend on the size of the overlap. The linear convergence result depends also on the number of subdomains because it is limited by the classical steady state result of overlapping Schwarz for elliptic problems. However the superlinear convergence result is independent of the number of subdomains. Thus overlapping Schwarz waveform relaxation does not need a coarse space for robust convergence independent of the number of subdomains, if the algorithm is in the superlinear convergence regime. Numerical experiments confirm our analysis. We also briefly describe how our results can be extended to more general parabolic problems.     

一类求解反应扩散方程的Newton波形松弛方法

对反应扩散方程提出一种新型的Newton波形松弛方法,并给出此方法的误差估计式.通过与传统的波形松弛方法比较,这种Newton波形松弛方法有更快的收敛性,且收敛速度不随网格加密而减慢.这种方法可以保持传统波形松弛方法可并行的特点.最后通过数值算例验证这种方法的有效性.     

Relaxation Phenomenon of the P—systems

ＲｅｌａｘａｔｉｏｎＰｈｅｎｏｍｅｎｏｎｏｆｔｈｅＰ－ｓｙｓｔｅｍｓＬｉＹｉｆａｎｇ（ＮｏｒｔｈＣｈｉｎａＩｎｓｔｉｔｕｔｅｏｆＷａｔｅｒＣｏｎｓｅｒｖａｎｃｙａｎｄＨｙｄｒｏｅｌｅｃｔｒｉｃＰｏｗｅｒ，Ｚｈｅｎｇｚｈｏｕ，４５００４５）ＬｉｕＦａｇ...     

线性随机微分方程的离散波形松弛方法的几乎必然收敛性

提出了随机微分方程的离散型波形松弛方法,证明了它是几乎必然收敛的.此外,通过数值实验验证了所得结果.     

On the convergence properties of Hildreth's quadratic programming algorithm

We prove the linear convergence rate of Hildreth's method for quadratic programming, in both its sequential and simulateneous versions. We give bounds on the asymptotic error constant and compare these bounds to those given by Mandel for the cyclic relaxation method for solving linear inequalities.Research of this author was partially supported by CNPq grant No. 301280/86.On leave from the Universidade Federal do Rio de Janeiro, Instituto de Matemática, Rio de Janeiro, R.J. 21.910, Brazil. Research of this author was partially supported by NIH grant HL28438.