共查询到17条相似文献,搜索用时 93 毫秒
1.
提出了单调线性互补问题基于新的核函数的大步校正内点算法.这个核函数是强凸的,而且它既不是自正则函数也不是经典的对数函数.基于这个核函数,可以定义新的迭代方向和邻近度量.利用这个新的核函数的一些性质,得到新算法的迭代复杂性为O(√n(logn)^2log(n/ε)),这减少了大步校正原始-对偶内点算法的实际计算效果与理论复杂性之间的差距. 相似文献
2.
本文给出了凸二次优化问题基于一类有限核函数的新的大步校正内点算法.这些核函数是一类相当广泛的函数,它的主要特征是非自正则的,而且在其可行域边界上的值是有限的.利用类似于线性规划的相应算法的分析方法,证明了新算法具有目前最好的大步校正算法的迭代复杂性,即O(√nlognlog(n/ε)). 相似文献
3.
《南阳理工学院学报》2016,(6):116-122
基于一个新的不显含增长项与障碍项的核函数,对线性规划提出了一种原始-对偶内点算法。这个核函数用于确定算法的搜索方向和度量迭代点与中心路径的距离。基于新的核函数和相应邻近函数良好的分析性质,证明了大步校正和小步校正算法的迭代复杂性阶分别为O(nlogn/ε)和O(nlognε)。 相似文献
4.
《南阳理工学院学报》2016,(2):123-128
对凸二次规划提出了一种基于双障碍三角核函数的大步校正原始-对偶内点算法。通过应用新的技术性引理和这类核函数良好的性质,证明了算法的迭代复杂性为O(n~(2/3) logn/ε),这与目前凸二次规划基于三角核函数的大步校正内点算法最好的迭代复杂性一致。 相似文献
5.
提出了一个新的求解凸二次内点算法,算法基于原始-对偶仿射尺度算法的思想,每步迭代只须解一个线性方程组,通过适当选取步长,算法具有多项式计算复杂性。 相似文献
6.
基于一类非自正则核函数,为单调非线性互补问题提出了一个新的原始—对偶大步校正内点算法.该算法借助于Peng在文献[Peng J,Roos C,Terlaky T.Self-Regularity:A New Paradigmfor Primal-Dual Interior-Point Algorithms.Princeton,NJ:Princeton University Press,2002]中相应算法的分析框架,通过将非自正则函数作为分析工具,来确定出算法的搜索方向和步长.算法最终被证明具有多项式复杂性.特别地,当取增长项q=logn时,该算法迭代复杂性为O( (1+L)2 1/n1+p (logn)(1+2p)/(1+p)logn/ε),与基于经典的对数障碍函数的算法相比,此迭代界有了较大的提高. 相似文献
7.
沈忠环 《三峡大学学报(自然科学版)》2008,30(5)
基于线性规划原始-对偶内点算法的思想,对框式凸二次规划提出了一种新的内点算法-原始-对偶势下降内点算法.算法取牛顿方向作为迭代方向,利用势函数选择迭代步长,并证明了新算法具有O(nL)的迭代复杂性. 相似文献
8.
可分凸二次规划的不可行内点算法 总被引:4,自引:0,他引:4
给出了可分凸二次规划的不可行内点算法,并证明了该算法在O(n^2L次迭代之后,或收敛到问题的一个近似最优解,或说明该问题在某个较大区域内无最优解。 相似文献
9.
王浚岭 《三峡大学学报(自然科学版)》2003,25(5):464-466
对线性约束的凸规划问题给出了一个原始-对偶仿射尺度算法,比较了这种方法与“内椭球法”两种算法的关系,并证明了该算法的迭代复杂性是O(nL^2)。 相似文献
10.
给出了求解凸二次规划的一种二阶Mehrotra型预估-校正算法。该算法受Salahi等人对线性规划提出的相应算法启发,引入了安全步策略,保证了校正步步长有适当下界,从而具有多项式复杂性。由于算法迭代方向不正交,算法在罚参数的校正和复杂性的分析上有别于线性规划的情形。最后,通过一些新的技术性引理,证明了算法在最坏情况下的迭代复杂性为O{n3/2log((x0)Ts0)/ε}。 相似文献
11.
对框式约束的可分凸二次规划提出了1个原始-对偶不可行内点算法,并证明了该算法是1个多项式时间算法。 相似文献
12.
对凸二次半定规划提出了一种新的全-Newton步原始-对偶内点算法.通过建立和应用一些新的技术性结果,证明了算法的迭代复杂性为O( n log n )ε ,这与目前凸二次半定规划的小步校正内点算法最好的迭代复杂性一致. 相似文献
13.
14.
求解框式约束下凸二次规划问题的内点算法 总被引:7,自引:0,他引:7
对于框式凸二次规划问题给出了一个内点路径跟踪算法,该算法的迭代复杂度为O(√nL),每一步近代所需计算量为O(n^3),其中n为变量个数,L为问题的输入长度。 相似文献
15.
16.
对一类利用对数障碍函数法求解凸二次规划问题的内点算法给出了全局收敛定理的证明,同时指出该算法并没有考虑到避免Maratos效应,因此很难有超线性收敛的结论,但是由于该算法简单,计算量少,故对小规模问题依然是有效的。 相似文献
17.