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

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

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

针对单调线性互补问题设计了一种基于核函数的满-Newton步不可行内点算法,算法的主迭代由一个可行步和几个中心步构成。通过建立和应用一些新的分析工具,证明了算法的多项式复杂性为O(nlogmax{(x0)Ts0,‖r0‖/n}),这与当前单调线性互补问题的不可行内点算法最好的迭代界一致。     

一类水平线性互补问题的一个不可行内点算法的收敛性

作为单调水平线性互补问题的推广,引入了Ｐ＊（κ）阵水平线性互补问题（简称Ｐ＊（κ）－ＨＬＣＰ）．证明了Ｙ．张的算法能被推广以解决Ｐ＊（κ）－ＨＬＣＰ问题,这个推广算法在运算过程中是独立于分类数κ的．如果这个算法的起始点是一对任意的正数,那么算法将达到Ｑ－线性收敛;如果起始点是一对足够大的正数,此算法经过至多Ｏ（（ｋ＋１）４ｎ２ｌｎ（（ｘ０）ｒｓ０）／ε次运算得到ε－逼近解,其中（ｘ０,ｓ０）是一对起始点     

求解P_*(κ)-LCP的自适应全-Newton步不可行内点算法

对P*(κ)线性互补问题提出了一种自适应全-Newton步不可行内点算法.算法是对Mansouri等人(H.Mansouri and M.Pirhaji in Journal of Operations Research Society of China 1:523-536,2013)提出的单调线性互补问题的自适应不可行内点算法的推广.在算法的每一次迭代中,障碍校正参数θ的取值并不固定,它总在1/(51n(1+4κ)2)和1/(14n(1+4κ)2)之间取满足算法要求的最大值,使得算法快速收敛于问题的一个ε-近似解.     

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

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

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

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

基于代数变换求解P0阵线性互补问题的不可行内点算法

基于代数变换和KMM算法的框架,通过在牛顿方程中嵌入一种自调节功能,提出了一种新的求解P0阵线性互补问题的不可行内点算法,并证明了该算法的全局收敛性.     

求解一类互补问题的不可行内点法与其计算复杂性

给出了求解一类非单调线性互补问题的不可行行内点法的基本步骤,证明了该算法的收敛性,讨论了算法的计算复杂性,给出了进求解单调性互补问题的不可行内点法的推广。     

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

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

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

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

A new class of infeasible interior-point algorithm for linear complementarity problem

This paper proposes an infeasible interior-point algorithm for linear complementarity problem with full-Newton steps.The main iteration consists of a feasibility step and several centrality steps.No more than O(n log(n /))iterations are required for getting an-solution of the problem at hand,which coincides with the best-known bound for infeasible interior-point algorithms.     

二阶锥规划的原始-对偶不可行内点法

针对二阶锥规划问题,给出了一种新的原始-对偶不可行内点法,利用该算法只需迭代O（槡nlnε-1）次就可找到问题的ε-近似解。该算法不要求初始点及其迭代点的可行性,只要求所有迭代点位于不可行中心路径的某个邻域内。初步的数值实验表明本算法是有效的。     

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

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

线性互补问题的邻域跟踪算法

文章把艾文宝的邻域跟踪算法推广到单调线性互补问题(LCP),由于单调LCP的迭代方向不再具有正交性,因此算法的理论分析变得复杂。证明了算法的迭代复杂性为O(nL),并且通过证明对偶间隙的单调性,使得算法易于执行。     

求解P_*(κ)-水平线性互补问题的核函数内点算法

提出了一个新的核函数,使用该核函数设计了一个求解P*(κ)-水平线性互补问题(P*(κ)-HLCP)的多项式内点算法.为了给出算法的复杂度,首先分析了该核函数的性质;最后,给出了大步更新算法和小步更新算法的迭代复杂度,这些复杂度与目前内点算法最好的复杂度一致.     

Interior-point algorithm for linear optimization based on a new kernel function

In this paper, we design a primal-dual interior-point algorithm for linear optimization. Search directions and proximity function are proposed based on a new kernel function which includes neither growth term nor barrier term. Iteration bounds both for large-and small-update methods are derived, namely, and . This new kernel function has simple algebraic expression and the proximity function has not been used before. Analogous to the classical logarithmic kernel function, our complexity analysis is easier than the other primal-dual interior-point methods based on logarithmic barrier functions and recent kernel functions.     

绝对值方程的一种严格可行内点算法

给出绝对值方程的一种新算法. 先把绝对值方程转化为线性互补问题, 再结合牛顿方向和中心路径方向, 通过求解一个线性方程组得到搜索方向.  获得了求解绝对值方程的一种严格可行内点算法, 并证明了该算法经过有限次迭代后收敛到原问题的一个最优解, 数值实验表明方法是有效的.