基于代数等价路径的一致P-函数非线性互补问题的可行内点算法

对一致P-函数非线性互补问题,提出了一种新的基于代数等价路径的可行内点算法,并讨论了计算复杂性.该算法可以在任一内部可行点启动,并且全局收敛;当初始点靠近中心路径时,此算法便成为中心路径跟踪算法,特别对于单调线性互补问题,总迭代次数为O(n^(1/2)L),其中L是问题的输入长度.

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

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

互补问题的几种可行内点算法的计算机实现

对一致p函数非线性互补问题及其特例对p矩阵非单调线性互补问题的已有的两种算法,宽或窄邻域路径跟踪算法和基于等价代数路径跟踪算法,利用Matlab编程做数值实验.通过构造优化模型,设计了求解问题的初始点和p矩阵的正指数的方法,完成了这两种算法的计算机实现,验证了算法的收敛性和有效性.通过对实验数据的分析得出如下结论:路径跟踪算法在宽邻域上的实际效果比窄邻域上的要好,与基于等价代数路径跟踪算法相比各有优劣.通过对参数β和t的分析,提出了改进算法.改进算法应用在大规模问题上表现出明显的优势.