修正一类非单调线性互补问题的宽邻域路径跟踪算法

通过对非单调线性互补问题所提出的一种内点算法进行分析,指出了算法中存在的关键性错误,在此基础上给出了求解一类非单调线性互补问题的宽邻域路径跟踪算法,给出了作为复杂性分析基础的两个重要关系式的正确表达式,并克服了由此带来的在收敛性分析中的一系列困难,成功地将线性规划问题的宽邻域内点算法,推广到非单调线性互补问题,讨论了算法的迭代复杂性。特别对于单调线性互补问题,得到了目前宽邻域内点算法迭代复杂性的最好结果。

一个求解单调线性互补问题的不可行内点算法

基于核函数设计一个求解单调线性互补问题的不可行内点算法,在算法的每一步迭代中,只需要求解线性方程组得到新的搜索方向。然后,按照一定的线性搜索规则,选择合适的步长得到新的迭代点。数值实验结果显示该算法是有效的。

求解一类非单调线性互补问题的宽邻域内点方法及其计算复杂性

对于一类非单调线性互补问题给出了一种新的算法———宽邻域内点算法,并讨论了其计算复杂性。

单调线性互补问题的Mehrotra型预估-校正算法的迭代复杂性(英文)

Mehrotra型预估-校正算法是很多内点算法软件包的算法基础,但它的多项式迭代复杂性直到2007年才被Salahi等人证明.通过选择一个固定的预估步长及与Salahi文中不同的校正方向,本文把Salahi等人的算法拓展到单调线性互补问题,使得新算法的迭代复杂性为O(nlog((x0)Ts0/ε)),同时,初步的数值实验证明了新算法是有效的.

一类非单调线性互补问题的高阶Dikin型仿射尺度算法

对于一类非单调线性互补问题提出了一个新算法 :高阶Dikin型仿射尺度算法 .算法的每步迭代 ,基于线性规划Dikin原始 对偶算法思想来求解一个线性方程组得到迭代方向 ,再适当选取步长 。

一类非单调线性互补问题的宽邻域内点算法

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

非单调线性互补问题的宽邻域算法复杂度分析

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

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

对P*(κ)阵线性互补问题提出了一种新的宽邻域预估校正内点算法.该算法是基于Mehrotra型预估校正算法思想,把线性规划问题拓展到非单调线性互补问题中(P*(κ)-LCP),并讨论了其计算复杂性.分析结果表明,所给算法是多项式时间算法.最后通过数值实验验证了算法的有效性.

单调线性互补问题的高阶仿射尺度算法

对于单调线性互补问题提出了一种新的内点算法———高阶仿射尺度算法 算法的每一步迭代 ,利用高阶原始—对偶内点算法的思想求解一个方程组得到迭代方向 ,再适当选取步长 。

单调线性互补问题的全牛顿步内点算法

针对单调线性互补问题,构造了新的核函数.通过构造的核函数来确定搜索方向和逼近度量,接着给出了求解单调线性互补问题的全牛顿步内点算法,最后给出了算法的复杂性界.所构造核函数使得算法分析简单,采用全牛顿步避免了线性搜索.

单调线性互补问题的非精确不可行内点算法

对单调线性互补问题提出了一种非精确不可行内点算法.该算法的迭代方向仅需要达到一个相对的精度.在初始点位于中心线的某邻域内的假设下,证明了算法的全局收敛性.

基于核函数求解单调线性互补问题的新full-Newton步内点算法

本文对单调线性互补问题设计了一种基于核函数的full-Newton步内点算法.该核函数导出新的搜索方向并定义了迭代点到中心路径的邻近度量.通过应用新的技术引理,证明了该算法的多项式复杂性阶为O(nL),这与当前求解单调线性互补问题内点算法最好的迭代复杂性阶一致.

一类非单调线性互补问题的仿射尺度算法

对于一类非单调线性互补问题给出一种新的内点算法。算法的每一步迭代 ,利用线性规划的原始——对偶内点算法的思想求解一个线性方程组而得到迭代方向 ,再适当选取步长 ,使算法具有多项复杂性。

P-矩阵非单调线性互补问题的宽邻域路径跟踪算法及其计算复杂性

对一类非单调(P-矩阵)线性互补问题,提出了一种新的宽邻域(N-∞(β))路径跟踪算法,并讨论了该算法的收敛性及计算复杂性.分析结果表明,所给方法是一多项式时间算法.

一类非单调线性互补问题宽邻域预估校正算法

对于一类非单调线性互补问题给出了一种新的内点算法-宽邻域预估校正算法,算法基于精典预估校正思想,把窄邻域拓展到一个宽邻域里使得算法更快地迭代,讨论了其算法的计算复杂性,并给出了数值实验.

一类非单调线性互补问题的预估校正算法

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

非单调线性互补问题的不可行内点算法

研究了一类更广泛的非单调线性互补问题,提出了其一个不可行内点算法,分析了算法的收敛性,给出了算法的多项式复杂性。

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

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

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

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

一种新的求解单调线性互补问题的满Newton步不可行内点算法

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