一个求解P（K）—矩阵线性互补问题的宽邻域路径跟踪算法

基于预校正方法,对Ｐ（Ｋ）－矩阵线性互补问题给出了一个失代复杂性Ｏ（ｋ＋１）ｎ＾２／３Ｌ）的宽邻域路径跟踪算法,算法改进了Ｚｈａｎｇ等的可行宽域路径跟踪算法的迭代复杂性;比迭代复杂性为Ｏ（ｋ＋１）√ｎＬ的小邻域路径跟踪算法为好。     

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

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

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

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

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

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

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

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

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

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

框式凸二次规划宽邻域原始-对偶势下降内点算法

基于线性规划原始-对偶势下降内点算法的思想,对框式凸二次规划提出一种新的内点算法宽邻域原始-对偶势下降内点算法.算法选取牛顿方向作为迭代方向,利用势函数选择迭代步长,分析算法的多项式迭代复杂性,并证明新算法具有较好的迭代复杂性O(nL).     

凸二次规划宽邻域原始-对偶势下降内点算法

基于线性规划原始-对偶内点算法的思想,对凸二次规划提出了一种新的内点算法-宽邻域原始-对偶势下降内点算法.算法取牛顿方向作为迭代方向,利用势函数选择迭代步长.由于迭代方向不再正交,因此,算法的复杂性分析不同于线性规划的相应算法的分析.证明了新算法具有O(nL)的迭代复杂性.此外,初步的数值试验表明了算法的可行性以及有效性.     

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

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

单调线性互补问题的宽邻域预估-校正内点算法

基于邻近度量函数的最小值,对单调线性互补问题提出了一种新的宽邻域预估-校正算法,在较一般的条件下,证明了算法的迭代复杂性为O√nlog(x0)Ts0/ε).该算法可视为最近zhao提出的线性规划基于邻近度量函数最小值的宽邻域内点算法的推广.     

求解P*(k)阵线性互补问题的内点幂级数算法

本对P*(k)阵线性互补问题,给出了一种内点幂级数算法,其迭代复杂度为O（2k 1)^2n^(1 1/r)/2L^(1 1)/r,r为阶数。     

P*(κ)线性互补问题的预估-校正内点算法

通过修正大邻域跟踪算法的搜索方向, 提出一种新的求解P*(κ)线性互补问题(LCP)的不可行预估-校正内点算法, 并对算法进行了收敛性分析, 证明了该算法具有目前最好的理论复杂度O((1+κ)^5/2nL). 数值结果验证了算法的有效性.     

拟希尔伯特阵和一般阵相乘的快速串行与并行计算

本文给出了拟希尔伯特阵和一般阵相乘的快速串行与并行算法。对于串行计算,时间复杂性是O((nlogn)~2),对于并行计算,在有n台处理机的条件下,其计算步数是O(nlog~2n),而效率是O(1)。     

二次半定规划一个原始对偶路径跟踪算法

本文提出求解二次半定规划的一个基于H..K..M方向的原始对偶路径跟踪算法.文中首先导出确定H..K..M方向的线性方程组,并证明该搜索方向的存在唯一性;然后给出算法的具体步骤,并证明算法产生的迭代点列落在中心路径的某个邻域内.最后采用Matlab(R2011b)数学软件编程对算法进行数值试验.数值结果表明算法是有效的.     

在MIMD－CREW模型上确定凸多边形可碰撞区域的并行算法

设Ｐ和Ｑ是平面内任意两个互不相交的凸多边形，目前确定Ｐ与Ｑ的可碰撞区域的最佳串行算法时间复杂度为Ｏ（ｎ＋ｍ），其中ｎ和ｍ分别为凸多边形Ｐ和Ｑ的顶点个数．在该算法的基础上构造了一个易于并行化的求支撑点的串行算法，进而给出了在ＭＩＭＤ－ＣＲＥＷ模型上确定可碰撞区域的并行算法，其时间复杂度为Ｏ（（Ｓ＋ｌｏｇ＿２（ｎ＋ｍ））ｌｏｇ＿２（ｎ＋ｍ）／ｌｏｇ＿２Ｓ），其中Ｓ为处理机个数     

基于代数等价路径的一类线性约束凸规划问题的内点算法

对于满足尺度李谱希茨条件的一类线性约束凸规划问题,提出了一种基于代数等价路径的原始-对偶内点算法,并讨论了计算复杂性.该算法可以在任一内部可行点启动,并且全局收敛,当初始点靠近中心路径时,此算法便成为中心路径跟踪算法,总迭代次数为O(nL),其中L是问题的输入长度,数值实验结果表明算法是有效的.     

找K个最小生成树的并行算法

基于SIMD 机器——一种可以同时读但不可同时写的共享计算模型(CREW-PRAM)给出了找K 个最小生成树的并行算法,此算法需O(log~2n+Klogn~*)时间及O(n~2)处理器;而基于可以同时读、写的更强计算模型(CRCW-PRAM),求K 个最小生成树仅需O(Klogn)时间及O(n~2)处理器,这里n 是图的顶点数.     

平行批排序最小化最大完工时间在线算法的一个注记

讨论单机、平行批、批容量无界、最小化最大完工时间的在线排序问题.对该排序问题,Zhang等人(G.Zhang,X.Cai and C.K.Wong,On-line algorithms for minimizing makespan on batch processing machines,NavalResearch Logistics,48(2001),241-258.)和Deng等人(X.Deng,C.K.Poon and Y.Z.Zhang,Approximation algo-rithms in batch processing,Journal of Combinatorial Optimization,7(2003),247-257.)两组作者分别独立地给出了同一个竞争比为(5 1)/2的在线算法,并证明该在线算法是最佳可能的.在他们的算法中,在每一批中的加工时间最大的工件,不妨设其准备时间为r而加工时间为p,将被滞后到(1 α)r αp时刻以后加工,其中α=(5-1)/2.对同一问题设计了一个修订的在线算法,其中加工时间为p的工件只需要滞后到αp时刻.该在线算法仍然是最佳可能的,并且在一定意义下,该在线算法是渐近最优的.     

下限极限分析的子迭代路径跟踪内点算法

采用路径跟踪内点法求解有限元下限极限分析所对应的非线性规划问题。在非线性方程组的Newton算法中引入子迭代过程,能够直接采用位移型有限元的数据存储格式和求解工具,并且大量计算可以在单元一级完成。改进的算法可直接利用现有的位移型有限元程序,实现过程简单。算例表明,该算法的效率和精度均可以得到保证。