一个求解P_*(K)-矩阵线性互补问题的宽邻域路径跟踪算法(英)

基于预校正方法,对P*（K）-矩阵线性互补问题给出了一个迭代复杂性为O（k＋1）n2/3L）的宽邻域路径跟踪算法,算法改进了Zhang等的可行宽域路径跟踪算法的迭代复杂性;比迭代复杂性为O的小邻域路径跟踪算法为好．     

求解P~*(τ)阵线性互补问题的宽邻域路径跟踪算法

针对p*(τ)阵线性互补问题,提出一种新的内点算法—宽邻域路径跟踪算法.该算法基于精典线性规划路径跟踪算法思想,把宽邻域路径跟踪算法推广到p*(τ)阵非单调线性互补问题,给出算法的具体步骤,讨论算法的迭代复杂性,并给出数值实验.     

单调加权互补问题的路径跟踪算法

加权互补问题是线性互补问题的推广模型,具有重要的应用背景.分析了加权互补问题的中心路径及其邻域,基于新定义的邻域,提出了求解单调加权互补问题的一个路径跟踪算法.取邻域中一点为初始点,证明了算法的O(nL)迭代复杂性.当加权互补问题中的权向量w为零向量时,该中心路径及其邻域和线性互补问题中的定义相同,该算法即为求解线性互补问题的宽邻域路径跟踪算法.     

一个求解框式约束线性规划的原一对偶路径跟踪内点算法

给出了一个求解框式约束线性规划问题的原一对偶路径跟踪内点算法，其迭代复杂性为Ｏ（ｎＬ）。     

线性规划的一个宽邻域预估-矫正内点算法

在线性规划的内点算法中,宽邻域算法比窄邻域算法的数值效果好,但宽邻域算法的复杂性比窄邻域差.提出了求解线性规划问题的一个宽邻域预估-矫正内点算法,证明了该算法的迭代复杂性是O(n L),这是线性规划的内点算法中最好的复杂性结果.     

Dedekind函数k次方ψ^k（n）的均值估计

设ψ（ｎ）是Ｄｅｄｅｋｉｎｄ函数，给出了ｋ是自然数且ｋ≥２时的ψｋ（ｎ）的算术均值：ｎ≤ｘψｋ（ｎ）＝ｃ０ｘｋ＋１＋Ｏ（（ｘｌｏｇｘ）ｋ（ｌｏｇｌｏｇｘ）ｋ－１２），ｎ≤ｘ１ψｋ（ｎ）＝ｃ１＋ｃ２ｘｋ－１＋Ｏ１ｘｋ（ｌｏｇｘ）ｋ．     

高阶演化方程任意阶精度的显式格式

讨论高阶演化方程ａｕ／ａｔ＝ａ（ａ＾２ｋ＋１）／（ａｘ＾２ｋ＋１）（其中ａ≠０为实常数,ｋ＝１,２,３,．．．）的２层３层显式差分格式,已有格式的精度是Ｏ（τ＋ｈ）或Ｏ（τ＋ｈ＾２）利用半离散化方法给出一类具有任意阶精度Ｏ（τ＾ｐ＋ｈ＾ｑ）（ｐ．ｑ＝１．２,．．．）的显式格式,ｐ＝３,４,ｑ＝２ｋ．２（ｋ＋２）（２层格式）和ｐ＝２,４,ｑ＝２ｋ,２（ｋ＋１）．２（ｋ＋３）（３层格式）（ｋ＝１,２,     

求解单调线性互补问题的邻域跟踪内点算法

把艾文宝的邻域跟踪算法推广到单调线性互补问题(LCP),用2-范数代替1-范数来定义宽邻域.由于单调LCP的迭代方向不再具有正交性,因此算法的理论分析比线性规划复杂.证明了算法的迭代复杂性为O(√nL).通过证明对偶间隙关于搜索步长的单调性,使得算法易于执行.数值实验显示了该算法的有效性.     

一种求单源单汇点无环图最短路径的新算法

用Ｄｉｊｋｓｔｒａ算法，可求出单源单汇点最短路径，时间复杂性是Ｏ（ｎ＾２）。笔者提出了一种求最短路径的算法，时间复杂性是Ｏ（ｎ＋ｅ）（其中ｎ是图中顶点数，ｅ是边数），且两种算法的空间复杂性基本相同。     

广义Armijo步长搜索下循环共轭方向算法的收敛性证明

共轭方向算法中搜索方向依赖于对参数β＾（ｋ）的选取ｓ＾（１）＝－ｇ＾（１），ｓ＾ｋ＋１）＝－ｇ＾（ｋ＋１）＋β＾（ｋ）ｓ＾（ｋ），ｋ≥１。本文给β＾（ｋ）适当条件以保证算法的下降性，并在广义Ａｒｍｉｊｏ步长搜索下，给出了算法的收敛性证明。     

一种求单源单汇点无环图最短路径的新算法

用Ｄｉｊｋｓｔｒａ算法，可求出单源单汇点最短路径，时间复杂性是Ｏ（ｎ２）．笔者提出了一种求最短路径的算法，时间复杂性是Ｏ（ｎ＋ｅ）（其中ｎ是图中顶点数，ｅ是边数），且两种算法的空间复杂性基本相同。     

求解框式约束下凸二次规划问题的内点算法

对于框式凸二次规划问题给出了一个内点路径跟踪算法,该算法的迭代复杂度为Ｏ（√ｎＬ）,每一步近代所需计算量为Ｏ（ｎ＾３）,其中ｎ为变量个数,Ｌ为问题的输入长度。     

一类非单调线性互补问题宽邻域预估校正算法

对于一类非单调线性互补问题给出了一种新的内点算法-宽邻域预估校正算法,算法基于精典预估校正思想,把窄邻域拓展到一个宽邻域里使得算法更快地迭代,讨论了其算法的计算复杂性,并给出了数值实验.     

Ore k-型图的性质和1-因子

本文研究了 Ｏｒｅ ｋ－型图的若干表征其结构的性质，并证明了 Ｏｒｅ ｋ－型图 Ｇ在 δ（Ｇ）＝ｋ＋２≤ｎ＋１或δ（Ｇ）≥ｎ＋ｋ的条件下含有ｋ＋２个边不重的１－因子．从而部分地证实了Ｗｉｎ 猜想．     

P-矩阵非单调线性互补问题的宽邻域路径跟踪算法及其计算复杂性

对一类非单调(P-矩阵)线性互补问题,提出了一种新的宽邻域(N-∞(β))路径跟踪算法,并讨论了该算法的收敛性及计算复杂性.分析结果表明,所给方法是一多项式时间算法.     

线性规划的宽邻域预估校正算法

提出了一种新的内点算法--宽邻域预估校正算法。该算法基于经典预估校正算法思想,把窄邻域拓展到宽邻域里,使算法更快地迭代。给出了算法的具体步骤,讨论了其计算复杂性,分析结果表明,所给算法是一多项式时间算法。通过数值实验验证算法的有效性。     

线性规划基于修正牛顿方向的宽邻域内点算法

通过修正经典宽邻域算法的搜索方向, 提出一种新的求解线性规划问题的宽邻域内点算法, 并对算法进行收敛性分析, 证明了该算法具有经典宽邻域算法的迭代复杂性界O(nL). 数值实验表明算法是有效的.     

第二类Fredholm方程的有限元迭代校正算法

对第二类Ｆｒｅｄｈｏｌｍ积分方程，以有限元解为基础，建立了一个高精度算法──迭代校正算法，证明了在光滑核条件，对ｍ次有限元解做一次迭代校正，可使精度从Ｏ（ｈ＾ｍ＾＋＾１）提高到Ｏ（ｈ＾３＾ｍ＾＋＾３）。     

关于一个乘性混合问题（II）

设Ｎ为一充分大自然数，ｋ≥４为整数，Ｇ１．．．，Ｇｋ为（Ｎ＋１，．．．，２Ｎ）的子集，且（Ｇ１）〉〉Ｎ，．．．，Ｇｋ〉〉Ｎ，则存在ｎ１∈Ｇ１，．．．ｎｋ∈Ｇｋ及自然数ｂ，使得ｎ１．．．ｎｋ＝ｂ＾ｋ＋Ｏ（ｂ＾ｋ－３／２）。     

关于Hennekemper的一个基本不等式

用与Ｈｅｎｎｅｋｅｍｐｅｒ不同的方法研究了（ｆ＾ｋ＋１）＾（ｋ）的值分布，将Ｈｅｎｎｅｋｅｍｐｅｒ所得的基本不等式推广至小函数情形，得到了如下定理：设ｆ为超越亚纯函数，Ｆ＝（ｆ＾ｋ＋１）＾（ｋ），ｋ∈Ｎ，ψ为非零的小函数，则Ｔ（ｘ，ｆ）≤（１＋２ｋ＋１／４ｋ＾２＋２ｋ－１）Ｎ（ｒ，１／ｆ）＋４ｋ＋２／４ｋ＾２＋２ｋ－１Ｎ↑－（ｒ，１／Ｆ－ψ）＋Ｓ（ｒ，ｆ）。