共查询到18条相似文献,搜索用时 171 毫秒
1.
基于代数等价路径的一致P-函数非线性互补问题的可行内点算法 总被引:2,自引:0,他引:2
对一致P-函数非线性互补问题,提出了一种新的基于代数等价路径的可行内点算法,并讨论了计算复杂性.该算法可以在任一内部可行点启动,并且全局收敛;当初始点靠近中心路径时,此算法便成为中心路径跟踪算法,特别对于单调线性互补问题,总迭代次数为O(√nL),其中L是问题的输入长度。 相似文献
2.
一种新的可分凸二次规划的不可行内点算法 总被引:3,自引:0,他引:3
本文对可分凸二次规划提出了一个新的不可行内点算法 ,证明了该算法是一个多项式时间算法 ,并将迭代复杂性界降至O(nL) . 相似文献
3.
对水平线性互补问题提出了一种广义中心路径跟踪算法.任意的原始-对偶可行内点均可作为算法的初始点.每步迭代选择“仿射步”与“中心步”的凸组合为新的迭代方向,采用使对偶间隙尽可能减小的最大步长.算法的迭代复杂性为O(√nL). 相似文献
4.
在原始对偶内点算法的设计和分析中,障碍函数对算法的搜索方法和复杂性起着重要的作用。本文由核函数来确定障碍函数,设计了一个求解半正定规划问题的原始。对偶内点算法。这个障碍函数即可以定义算法新的搜索方向,又度量迭代点与中心路径的距离,同时对算法的复杂性分析起着关键的作用。我们计算了算法的迭代界,得出了关于大步校正法和小步校正法的迭代界,它们分别是O(√n log n log n/c)和O(√n log n/ε),这里n是半正定规划问题的维数。最后,我们根据一个算例,说明了算法的有效性以及对核函数的参数的敏感性。 相似文献
5.
6.
本文通过使用相同的矩阵因子,给出了一个求解单调线性互补问题的r-阶Mehrotra型宽城不可行内点算法,其中嵌入Wright的快速步与安全步算法.所给算法的迭代复杂性为O(n~((r 1)/r)L).在考虑的问题有一个严格互补解的条件下,所给算法具有2阶Q-超线性收敛性. 相似文献
7.
2010年高考湖北卷理科第(9)题为:若直线y=x+b与曲线y=3-√4x-x^2有公共点,则实数b的取值范围是 ( )
(A)[-1,1+2√2].
(B)[-1-2√2,1+2√2].
(C)[1-2√2,3].
(D)[1-√2,3]. 相似文献
8.
基于不可行内点法和预估-校正算法的思想,提出两个新的求解二阶锥规划的内点预估-校正算法.其预估方向分别是Newton方向和Euler方向,校正方向属于Alizadeh-Haeberly-Overton(AHO)方向的范畴.算法对于迭代点可行或不可行的情形都适用.主要构造了一个更简单的中心路径的邻域,这是有别于其它内点预估-校正算法的关键.在一些假设条件下,算法具有全局收敛性、线性和二次收敛速度,并获得了O(rln(ε0/ε))的迭代复杂性界,其中r表示二阶锥规划问题所包含的二阶锥约束的个数.数值实验结果表明提出的两个算法是有效的. 相似文献
9.
10.
11.
Mehrotra-type predictor-corrector algorithm,as one of most efficient interior point methods,has become the backbones of most optimization packages.Salahi et al.proposed a cut strategy based algorithm for linear optimization that enjoyed polynomial complexity and maintained its efficiency in practice.We extend their algorithm to P*(κ)linear complementarity problems.The way of choosing corrector direction for our algorithm is different from theirs. The new algorithm has been proved to have an ο((1+4κ)(17+19κ) √(1+2κn)3/2log[(x0)Ts0/ε] worst case iteration complexity bound.An numerical experiment verifies the feasibility of the new algorithm. 相似文献
12.
基于一类带有参数theta的新方向, 提出了求解单调线性互补问题的宽邻 域路径跟踪内点算法, 且当theta=1时即为经典牛顿方向. 当取theta为与问题规模 n无关的常数时, 算法具有O(nL)迭代复杂性, 其中L是输入数据的长度, 这与经典宽邻 域算法的复杂性相同; 当取theta=\sqrt{n/\beta\tau}时, 算法具有O(\sqrt{n}L)迭代复杂性, 这里的\beta, \tau是邻域参数, 这与窄邻域算法的复杂性相同. 这是首次研究包括经典宽邻域路径跟踪算法的一类内点算法, 给出了统一的算法框架和收敛性分析方法. 相似文献
13.
14.
$$O\sqrt{n}L$$ ); otherwise, the complexity bound is O(nL). The relations between our search direction and the one used in the standard interior-point algorithm are also discussed.
Received September 9, 1996 / Revised version received December 22, 1997? Published online March 16, 1999 相似文献
15.
Let T:X → X be an Axiom A diffeomorphism,m the Gibbs state for a Hlder continuous function ɡ. Assume that f:X → Rd is a Hlder continuous function with ∫Xfdm = 0.If the components of f are cohomologously independent, then there exists a positive definite symmetric matrix σ2:=σ2 (f ) such that Sfn √ n converges in distribution with respect to m to a Gaussian random variable with expectation 0 and covariance matrix σ2 . Moreover, there exists a real number A > 0 such that, for any integer n ≥ 1,Π( m*( 1√ nS f n ),N (0,σ2 ) ≤A√n, where m*(1√ n Sfn)denotes the distribution of 1√ n Sfn with respect to m, and Π is the Prokhorov metric. 相似文献
16.
设Pn(x)为n次多项式,a0≠0,m≥2且m∈N,得到形如∫Pn(x)ma0x3+a1x2+a2x+a3dx的三次无理函数积分可解的充要条件,且其解的形式为∫Pn(x)ma0x3+a1x2+a2x+a3dx=Qn-2(x).m(a0x3+a1x2+a2x+a3)m-1+C,其中Qn-2(x)为各项系数待定的(n-2)次多项式.运用待定系数法可求出Qn-2(x)的各项系数. 相似文献
17.
实例说明用第一类换元积分法或分部积分法求解几个典型不定积分,其被积函数含有根式a2-x2或x2±a2. 相似文献
18.
一种新的线性规划多项式时间算法 总被引:2,自引:0,他引:2
本文给出了一种新的线性规划多项式时间算法。在此算法中,每步可沿一族方向中的一个进行线性搜索,同时,还使用了开关策略,从而大大减少了求逆矩阵的次数,最后,证明了算法经O(nL)次迭代结束。 相似文献