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

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

具有O((√)nL)复杂性的Mehrotra型预估-矫正算法

针对内点方法在理论和实践之间存在着计算效果好的算法在理论上具有较差复杂性的矛盾,提出一种求解线性规划问题的Mehrotra型预估-矫正内点算法,并证明了该算法的迭代复杂性是O((√)nL).数值实验结果验证了算法的有效性.     

线性规划的一个新的Mehrotra型预估-矫正算法

在线性规划的内点算法中,理论和实践之间存在着数值效果好的算法具有较差复杂性的矛盾.目前大多数内点算法软件的执行采用Mehrotra型预估-矫正算法.本文提出了求解线性规划问题的一个新的Mehrotra型预估-矫正算法,证明了该算法的迭代复杂性是O(槡n L),这是内点算法所具有的最好的复杂性结果.     

二次锥规划的不可行内点算法

给出二次锥规划的一种不可行内点算法并证明该算法是多项式时间算法.利用本算法需O(√nlnε-1)次迭代就可找到问题的ε-近似解,其迭代复杂性界与现有的二次锥规划可行内点算法的复杂性界相同.     

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

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

框式线性规划的不可行内点算法

对框式线性规划提出了一个原始-对偶不可行内点算法,并证明了该算法的迭代复杂性为多项式时间性.     

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

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

枢式线性规划的不可行内点算法

对框式线性规划提出了一个原始-对偶不可行内点算法，并证明了该算法的迭代复杂性为多项式时间性。     

一种新的凸二次规划的内点算法

提出了一个新的求解凸二次内点算法,算法基于原始－对偶仿射尺度算法的思想,每步迭代只须解一个线性方程组,通过适当选取步长,算法具有多项式计算复杂性。     

线性互补问题基于核函数的满Newton步不可行内点算法

针对单调线性互补问题提出了一种满Newton步不可行内点算法.算法的每次主迭代是由一个可行步和若干个中心步组成.在算法的分析中,引入了一个有限核函数取代经典的对数障碍函数从而导出新的可行步,并且证明了算法的迭代复杂性与目前已知最好的线性互补问题的不可行性内点算法的迭代复杂性结果保持一致.     

一种新的求解CQSDP的全-Newton步内点算法

对凸二次半定规划提出了一种新的全-Newton步原始-对偶内点算法.通过建立和应用一些新的技术性结果,证明了算法的迭代复杂性为O( n log n )ε ,这与目前凸二次半定规划的小步校正内点算法最好的迭代复杂性一致.     

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

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

单调线性互补问题基于新的核函数的大步校正内点算法

提出了单调线性互补问题基于新的核函数的大步校正内点算法.这个核函数是强凸的,而且它既不是自正则函数也不是经典的对数函数.基于这个核函数,可以定义新的迭代方向和邻近度量.利用这个新的核函数的一些性质,得到新算法的迭代复杂性为O（√n（logn）^2log（n/ε））,这减少了大步校正原始-对偶内点算法的实际计算效果与理论复杂性之间的差距.     

线性规划内点算法的若干收敛性问题

对于线性规划问题 ｍｉｎ｛ｃтｘ｜Ａｘ≥ｂ，ｘ≥０｝，印度学者 и．Ｋａｒｍａｒｋａｒ于 １９８４年发明 了一种新的内点算法，它的时间复杂性为Ｏ（ｎ３．５Ｌ２），其中ｎ为问题的变量个数，Ｌ为输 入中的二进制位数。其后又出现了多种变形方案，如原始型和对偶型内点算法等等。本 文主要讨论它们的收敛性问题。关于Ｋａｒｍａｒｋａｒ算法，证明了当原始线性规划问题无有 限最优解时算法也可以收敛。关于原始型和对偶型内点算法，给出了它们的基本性质以 及若干收敛性结果。     

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

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

凸二次规划基于新的核函数的大步校正原始-对偶内点算法

本文对凸二次规划提出了一种基于新的核函数的大步校正原始-对偶内点算法．这种核函数构造新的障碍函数不仅可以定义新的搜索方向,而且可以控制内迭代的过程,使得对凸二次规划提出的大步校正原始-对偶内点算法的多项式复杂性阶改善到O（√n（logn）2log（n／ε））,优于基于经典对数障碍函数的相应算法的复杂性阶．     

线性规划的宽邻域预估校正算法

提出了一种新的内点算法--宽邻域预估校正算法。该算法基于经典预估校正算法思想,把窄邻域拓展到宽邻域里,使算法更快地迭代。给出了算法的具体步骤,讨论了其计算复杂性,分析结果表明,所给算法是一多项式时间算法。通过数值实验验证算法的有效性。     

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

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

内分类算法复杂性的讨论

在一定的条件下,给出内分类算法复杂性的严格定义;通过一种新的内分类算法分析及其与古典的内分类算法的测试比较,说明这一定义的合理性。最后给出了这种新算法的改进框图。     

求解凸二次规划的新内点算法

对凸二次规划提出了一种基于双障碍三角核函数的大步校正原始-对偶内点算法。通过应用新的技术性引理和这类核函数良好的性质,证明了算法的迭代复杂性为O(n~(2/3) logn/ε),这与目前凸二次规划基于三角核函数的大步校正内点算法最好的迭代复杂性一致。