首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 62 毫秒
1.
基于矩阵的非精确分裂和多重分裂、处理器的并行计算和松弛迭代算法,提出了求解线性互补问题的非精确松弛多分裂算法,当问题的系数矩阵为对角元为正的H-矩阵时或对称半正定时,证明了算法的全局收敛性.并在一定条件下给出了非精确松弛多分裂算法内迭代的特殊形式,分析了该情形下算法的收敛特性.  相似文献   

2.
研究了单调线性互补问题的一种内点法,将牛顿方向和中心路径方向相结合,通过求解一个线性方程组得到搜索方向;在每次迭代中,寻找使得新的迭代点满足可行性要求且同时使得势函数值下降的步长参数,进而建立了求解单调线性互补问题的一种势下降内点算法,并证明该算法经过多项式次迭代之后收敛到原问题的一个最优解,数值实验表明此方法是有效的。  相似文献   

3.
基于线性规划问题原始———对偶类内点算法的思想,讨论一类非单调线性互补问题,为其设计了一种新的算法———宽邻域内点算法,并讨论其多项式收敛性.与路径跟踪法相比较,该算法具有迭代过程简便,应用情景更加广阔等特点.  相似文献   

4.
对于一类非单调线性互补问题给出了一种新的内点算法-预估校正算法,并讨论了其多项式的收敛性。  相似文献   

5.
作为单调水平线性互补问题的推广,引入了P*(κ)阵水平线性互补问题(简称P*(κ)-HLCP).证明了Y.张的算法能被推广以解决P*(κ)-HLCP问题,这个推广算法在运算过程中是独立于分类数κ的.如果这个算法的起始点是一对任意的正数,那么算法将达到Q-线性收敛;如果起始点是一对足够大的正数,此算法经过至多O((k+1)4n2ln((x0)rs0)/ε次运算得到ε-逼近解,其中(x0,s0)是一对起始点  相似文献   

6.
研究非单调线性互补问题的宽邻域不可行内点算法.为减小算法的理论复杂度,通过两个牛顿方程分别计算两个搜索方向,再通过这两个搜索方向的凸组合,获得该算法的搜索方向.通过分析,该算法的复杂度与当前最好的宽邻域不可行算法的复杂度一致.  相似文献   

7.
将一种改进的满Newton步不可行内点算法拓展到单调线性互补问题(LCP)中.由于单调LCP的迭代方向不再具有正交性,因此算法的收敛分析不同于线性规划的情况.通过提出一些新的分析工具,证明了算法具有迭代复杂性O(n log (max{(x0)Ts0,‖r0‖}/ε)).  相似文献   

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

9.
给出了非负线性最小二乘问题的一个新算法.首先,把非负线性最小二乘转化为线性互补问题,结合牛顿方向和中心路径方向,通过求解一个线性方程组得到搜索方向;进而获得了求解非负线性最小二乘问题的一种严格可行内点算法,并证明该算法经过多项式次迭代之后收敛到原问题的一个最优解,数值实验表明此方法是有效的.  相似文献   

10.
针对单调线性互补问题设计了一种基于核函数的满-Newton步不可行内点算法,算法的主迭代由一个可行步和几个中心步构成。通过建立和应用一些新的分析工具,证明了算法的多项式复杂性为O(nlogmax{(x0)Ts0,‖r0‖/n}),这与当前单调线性互补问题的不可行内点算法最好的迭代界一致。  相似文献   

11.
对框式线性规划提出了一种非精确不可行内点算法,该算法使用的迭代方向仅需要达到一个相对的精度,在初始点位于中心线的某邻域内的假设下,证明了算法的全局收敛性。  相似文献   

12.
给出一种求解二次锥规划问题的原 对偶非精确不可行内点算法. 通过引入一个不可行邻域, 所给算法可以运用非精确搜索方向且不要求迭代点位于严格可行解集内. 该算法是全局收敛的.  相似文献   

13.
针对线性二阶锥权互补问题,提出一种新的非精确非单调光滑化牛顿法.首先,基于新的含参数光滑函数,将线性二阶锥权互补问题转化为一个光滑方程组;然后,给出求解该方程组的新非精确非单调光滑化牛顿法;最后,在半正定矩阵假设下,证明该算法全局收敛和局部超线性收敛.数值结果表明,该算法稳定、有效.  相似文献   

14.
框式线性规划的不可行内点算法   总被引:1,自引:0,他引:1  
对框式线性规划提出了一个原始-对偶不可行内点算法,并证明了该算法的迭代复杂性为多项式时间性.  相似文献   

15.
给出了一类新的非精确线性搜索,说明了在新的线性搜索下每次迭代产生下降方向.证明了此类共轭梯度算法具有全局收敛性.  相似文献   

16.
针对大规模二次锥规划问题提出一种非精确光滑算法.  该算法允许搜索方向有一定的误差, 在选择步长时采用非单调线性搜索策略. 证明了从任意点出发能得到算法的局部二次收敛速率.  相似文献   

17.
针对矩阵M为具有正主对角元素的严格对角占优矩阵的线性互补问题构造了一个迭代算法,证明了算法的全局收敛性,并给出了数值算例.  相似文献   

18.
解变分不等式的交替方向法每一步需要解一个(几个)变分不等式子问题,算法的有效性受这些子问题的影响很大.本文提出了一个解线性变分不等式的简单的交替方向法. 在每一步迭代中,只需要做矩阵-向量乘法和到简单集合的投影,使得算法的效率得到保证.在适当的条件下证明了算法的全局收敛性.初步的数值结果表明,我们的新算法较原有同类算法有所改进.  相似文献   

19.
提出了一个新的求解线性规划问题的不可行内点算法,这个算法每一步只须解一个线性方程组,算法是基于路径跟踪算法思想,适当选取初始点,算法至多可在O(nl)迭代步获得ε-可行性和ε-互补性,算法具有每一步的计算量少的特点。  相似文献   

20.
针对线性规划问题,给出了其原问题和对偶问题的最优性条件,并通过引入一个正则化的对称扰动的光滑函数,将其扩展成一个混合线性互补问题,并利用光滑型算法求解.该算法具有全局收敛的特性.对于有最优解的问题,算法能求得问题的一个严格互补解;对于不可行的问题,算法也能表明问题的不可行性.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号