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

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

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

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

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

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

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

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

一种求解单调方程组的范数下降共轭梯度法

提出一种求解大规模非线性单调方程组的范数下降共轭梯度算法.所提算法推广了Xiao,Song,Wang等提出的求解无约束优化问题的基于BB循环步长的共轭梯度算法,并结合Solodov和Svaiter提出的投影梯度算法.所提算法迭代形式简单、储存量小,且每步迭代不需要方程组的导数信息.本文证明算法的全局收敛性,并做数值试验验证算法在求解非线性单调方程组方面的有效性.     

单调加权互补问题的路径跟踪算法

加权互补问题是线性互补问题的推广模型,具有重要的应用背景.分析了加权互补问题的中心路径及其邻域,基于新定义的邻域,提出了求解单调加权互补问题的一个路径跟踪算法.取邻域中一点为初始点,证明了算法的O(nL)迭代复杂性.当加权互补问题中的权向量w为零向量时,该中心路径及其邻域和线性互补问题中的定义相同,该算法即为求解线性互补问题的宽邻域路径跟踪算法.     

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

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

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

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

非单调QP-free非可行域方法

提出了带有Fischer-Burmeister非线性互补(NCP)数的非单调QP-free非可行域算法.根据优化问题的一阶KKT条件,利用乘子和NCP函数,得到非光滑方程,给出解这个非光滑方程的迭代算法.该算法包含原始-对偶变量,在局部意义下,可看成关于一阶KKT最优条件的扰动牛顿-拟牛顿迭代算法.在线性搜索时,此算法采用非单调方法.给出的算法是可实现的并具有全局收敛性,且在适当假设下具有超线性收敛性.     

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

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