带有延迟时间下界的k-(n1,1,…,1)-排序问题的拟多项式时间算法

讨论Wikum的关于带有延迟时间下界的k-(n1,1,…,1)-链形结构排序问题的拟多项式时间算法,其中当n1=2的情况已由Yin等人(1999)解决,这里主要以n1=3的情形为例作更加细致的分析,然后给出较Yin等人(1999)的算法更加有效的拟多项式时间算法.为了保持文章的连续性,也将列出Yin等人(1999)的n1=2的算法加以比较.     

整数扩展欧几里得矩阵序列的选择项算法的修正

Wang和Pan提出了一个计算整数扩展欧几里得矩阵序列的选择项的算法,并把此算法应用于模有理数重构问题和数值有理数重构问题.这个算法仅消耗接近线性的时间复杂度,与目前已知的整数gcd算法的最佳时间复杂度相一致,而整数gcd算法只是此算法的一个特殊情形.分析了这个算法,指出了算法中由于考虑的不够全面而存在的错误,补充了矩阵序列性质的理论部分,并修正这个算法.     

线性分式多乘积规划问题的完全多项式时间近似算法

本文针对线性分式多乘积规划问题,通过Charnes-Cooper转化将原问题转化为一个等价问题,借助此等价问题提出一个获得原问题全局近似最优解的算法,最终证明了算法的收敛性,且提供了算法运算时间的理论分析.     

关于求解变分不等式问题的2-次梯度外梯度算法收敛性的一个补注

Yair Censor,Aviv Gibali和Simeon Reich为求解变分不等式问题提出了2-次梯度外梯度算法。关于此算法的收敛性,作者给出了部分证明,有一个问题：由算法产生的迭代点列能否收敛到变分不等式问题的一个解上,没有得到解决。此问题作为一个公开问题在文章“Extensions of Korpelevich's extragradient method for the variational inequalityproblem in Euclidean space”(Optimization,61(9)：1119-1132,2012)中被提出。在这篇简短的补注性文章中,对所提出的问题给出了答案：由算法产生的迭代点列能收敛到变分不等式问题的一个解上。给出2-次梯度外梯度算法的全局收敛性的一个完整证明,证明了从任意起始点开始,由算法产生的迭代点列都能收敛到变分不等式问题的一个解上。     

一种混合算法求解可分离带线性约束的变分不等式问题

本文研究了大规模的可分离带线性约束的变分不等式问题,提出了基于对数二次临近点法的交替方向法,新算法的每步用一个非线性方程组来代替变分不等式子问题.通过有效求解非线性方程组,使得新算法简单易行而且一定程度上提高了计算的效率.同时,在映射单调和原问题解集非空的条件下,证明了此算法具有全局收敛性,最后通过数值实验说明了此算法是有效可行的.     

全局优化问题的一个单参数填充函数方法

利用改进的填充函数的定义,对一般的无约束最优化问题给出了一个新的单参数填充函数,分析并证明了此填充函数的性质.利用该填充函数,构造了新的算法,对此算法进行了数值实验,并将此算法做了比较,结果表明此填充函数算法是可行的.     

H∞强镇定问题的新解法

H∞强镇定问题可解的原始算法是依赖于一个解存在的充分条件．自然的此算法应用起来有一定的局限性．针对此问题，首先给出H∞强镇定问题可解的一个充要条件．并说明该条件在计算上很容易实现的．并由此充要条件出发设计了一个简单且实际可行的算法．该算法实际上没有局限性，而且比较利于计算机编程．最后举例说明新算法与H∞强镇定问题可解的原有算法相比，具有更大的优点．     

卫星舱内长方体群布局的优化模型及全局优化算法

本文研究了卫星舱内长方体群优化问题,建立了一个三维布局优化模型,并用图论,群论等工具克服了布局优化问题时断时续性质带来的困难,在此基础上构造了一个全局收敛的优化算法,文中所用的方法可用于求解类似问题。     

自由构形幂零基的一个算法

给出求自由构形幂零基的一个算法 ,从而肯定地回答了Orlik的3个问题 ,并用此算法证明了Orlik的一个猜测成立的充分条件.     

求解稀疏分裂可行问题的一种投影算法

本文研究了稀疏分裂可行问题.通过将分裂可行问题转化为一个目标函数为凸函数的稀疏约束优化问题,设计一种梯度投影算法来求解此问题,获得了算法产生的点列可以收敛到稀疏分裂可行问题的一个解.用数值例子说明了算法的有效性.     

解一类Hessian矩阵亏秩的修正BFGs算法及其局部Q-超线性收敛性

本文对凸函数在极值点的Hessian矩阵是秩亏一的情况下,给出了一类求解无约束优化问题的修正BFGS算法.算法的思想是对凸函数加上一个修正项,得到一个等价的模型,然后简化此模型得到一个修正的BFGS算法.文中证明了该算法是一个具有超线性收敛的算法,并且把修正的BFGS算法同Tensor方法进行了数值比较,证明了该算法对求解秩亏一的无约束优化问题更有效.     

一种NTRU解密失败研究方案的分析与改进

NTRU是一种既速度快又结构紧凑的快速公钥体制,其安全性基于在有效时间内不可能从-个大维格中找到一个短向量的数学困难问题.YU等对NTRU解密失败问题进行了详细论述和研究,并给出解决解密失败时的处理方案.收稿通过实验和理论证明他们的处理理论和算法是错误的,并在此基础上给出了一个改进算法,该改进算法安全性与NTRU相同,可以解决NTRU解密失败问题.     

并行机问题的模拟退火调度算法研究

研究了一类调度目标是最小化最大完成时间的并行机调度问题.考虑到此问题的NP-hard特性,引入模拟退火算法思想以获取高质量近优解.分析了现有此问题模拟退火算法的缺陷,定义了关键机器和非关键机器,设计了一个包含局部优化的模拟退火算法.除了交换变换,还引入插入变换以改变各子调度中作业个数.大量的随机数据实验用于验证算法解的质量和计算效率,实验结果表明该模拟退火算法能够在有限时间内为大规模问题求得高质量满意解.     

P|rj,on-line|∑Cj的一类在线算法与竞争比分析

本文研究平等机上的在线排序问题,优化目标是使总完工时间最小,算法SSPT是此问题的一类在线算法,论文引入一个拟时间表,此时间表具有SRPT时间表的部分性质,论文通过此辅助时间表证明了SSPT算法是(3-(1/m))-competitive的.     

超载实时系统的算法

近年来,超载实时系统ｏｎ－ｌｉｎｅ排序已被许多作者研究过,对单台机问题,Ｓ．Ｂａｒｕａｈ等给出了一个最坏性能比的上界１／（１＋√Ｋ）~２,其中Ｋ为重要性比,Ｇ．Ｋｏｒｅｎ等提出了一个达到此界的最优算法（Ｄ－ｏｖｅｒ算法）,对多台机问题,Ｍ． Ｄｅｒｔｏｕｚｏｓ等证明即使在非超载情况下也不存在最优算法． Ｆ． Ｗａｎｇ等证明不可能存在竞争因子大于１／２的算法,并提出了一个算法,在Ｋ＝１及没有松弛时问的条件下,达到了１／２．对一般情况,他们证明任一Ｏｎ－ｌｉｎｅ算法的竞争因子均不会大于１／ａ,其中．对多台机情况,虽已发现了一些有用的性质,但如何构造一个较好的算法仍有待于进一步的研究．     

改进的生成树遗传算法及其在物流配送成本优化中的应用

针对物流配送成本优化问题的特点,建立了数学模型,并对基本的生成树遗传算法进行了改进,同时详细阐述了改进的生成树编码的遗传算法在物流配送成本优化问题中的运用等关键技术.最后根据此算法设计了一个物流配送优化系统,解决了一个物流配送成本优化问题,效果良好.此系统对于中小型物流公司设计最优物流策略和降低物流成本有着很大的应用前景.     

一类弱非线性方程组的非线性松弛非对称HSS类迭代算法

研究一类弱非线性方程组的求解问题,给出了求解此问题的一个非线性松弛非对称HSS类迭代算法,并在一定的条件下证明了算法的收敛性.数值结果表明该算法是有效的.     

求解分段常数图象分割模型的一个快速算法

针对Xue-ChengTai等提出的分段常数图象分割模型,我们提出了一个新的快速求解算法。通过引进一个函数来选择模型中的正则化参数β的值,并判断在迭代过程中何时求解不含惩罚项的泛函F。此函数的引入有效地加速了算法的收敛速度。结合原始-对偶Newton方法来求解总变差最小化问题。数值试验表明新算法具有很快的收敛速度与良好的分割效果,且算法对初始值的要求不高。     

单调线性互补问题的一种内点算法

本文研究了单调线性互补问题的一种内点算法.利用牛顿方向和中心路径方向,获得了求解单调线性互补问题的一种内点算法,并证明该算法经过多项式次迭代之后收敛到原问题的一个最优解.数值实验表明此方法是有效的.     

DC函数优化问题的非精确邻近点算法

本文对DC函数(即两凸函数之差)的最小化问题提出了一个非精确邻近点算法,并证明此算法的下降性和全局收敛性.