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

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

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

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

基于新的核函数求解线性规划的原始-对偶内点算法

基于一个新的不显含增长项与障碍项的核函数,对线性规划提出了一种原始-对偶内点算法。这个核函数用于确定算法的搜索方向和度量迭代点与中心路径的距离。基于新的核函数和相应邻近函数良好的分析性质,证明了大步校正和小步校正算法的迭代复杂性阶分别为O(nlogn/ε)和O(nlognε)。     

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

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

求解凸二次规划的一种二阶Mehrotra型预估-校正算法

给出了求解凸二次规划的一种二阶Mehrotra型预估-校正算法。该算法受Salahi等人对线性规划提出的相应算法启发,引入了安全步策略,保证了校正步步长有适当下界,从而具有多项式复杂性。由于算法迭代方向不正交,算法在罚参数的校正和复杂性的分析上有别于线性规划的情形。最后,通过一些新的技术性引理,证明了算法在最坏情况下的迭代复杂性为O{n3/2log((x0)Ts0)/ε}。     

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

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

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

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

凸二次规划的一种基于削减策略的Mehrotra型预估-校正算法

2008年,Salahi等对线性规划提出一种新的Mehrotra型预估-校正算法.基于削减(cut)策略,该算法保证校正步长有下界,从而具有多项式复杂性.基于这种思路,将此方法推广到凸二次规划.由于新算法的迭代方向不再正交,因此算法的复杂性分析与线性规划时不同.通过一些新的技术引理,证明了算法在最坏情况下,至多经过O(n5/2logεn)次迭代终止.最后,利用数值实验验证了算法的可行性与有效性.     

求解凸二次规划的一种二阶Mehrotra型预估一校正算法

给出了求解凸二次规划的一种二阶Mehrotra型预估一校正算法。该算法受Salahi等人对线性规划提出的相应算法启发,引入了安全步策略,保证了校正步步长有适当下界,从而具有多项式复杂性。由于算法迭代方向不正交,算法在罚参数的校正和复杂性的分析上有别于线性规划的情形。最后,通过一些新的技术性引理,证明了算法在最坏情况下的迭代复杂性为O（n^3/2log（x^0）^TS^0/ε）.     

基于自适应参数校正策略求解SDP的二阶Mehrotra型内点算法

最近,Salahi提出了一种求解线性规划的基于自适应参数校正策略的二阶Mehrotra型预估-校正算法,并在不使用安全策略的情况下证明了其迭代的多项式复杂性。本文将这一算法推广到半定规划。通过利用Zhang的对称化技术,同样在不使用安全策略的情况下,证明了算法的多项式迭代复杂界。     

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

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

求解线性规划的一种Mehrotra型预估-矫正内点算法

提出了一种求解线性规划问题的Mehrotra型预估．矫正内点算法，并证明了算法的代数复杂度。     

求解P~*(τ)阵线性互补问题的宽邻域路径跟踪算法

针对p*(τ)阵线性互补问题,提出一种新的内点算法—宽邻域路径跟踪算法.该算法基于精典线性规划路径跟踪算法思想,把宽邻域路径跟踪算法推广到p*(τ)阵非单调线性互补问题,给出算法的具体步骤,讨论算法的迭代复杂性,并给出数值实验.     

具有O(n1/2L)复杂度的Mehrotra型预估-校正内点算法

基于中心路径的大邻域,提出了一种新的二阶预估-校正内点算法求解半定线性互补问题,并证明了该算法具有目前最好的多项式复杂度O(n^1/2L).     

A new second-order Mehrotra-type predictor-corrector algorithm for SDO

In Zhang's recent works,a second-order Mehrotra-type predictor-corrector algorithm for linear optimization was extended to semidefinite optimization and derived that the algorithm for semidefinite optimization had O(n~(3/2)log(X~0)~T·S~0/ε) iteration complexity based on the NT direction as Newton search direction. In this paper, we extend the second-order Mehrotra-type predictor-corrector algorithm for linear optimization to semidefinite optimization and discuss the polynomial convergence of the algorithm by modifying the corrector direction and new iterates. It is proved that the iteration complexity is reduced to O(n~(3/2)log(X~0)~T·S~0/ε), which coincides with the currently best iteration bound of Mehrotra-type predictor-corrector algorithm for semidefinite optimization.     

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

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

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

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