单调线性权互补问题的新全牛顿步可行内点算法

迟晓妮, 杨玉萍, 刘三阳, 柳乐

doi:10.13764/j.cnki.ncdl.2024.03.009

南昌大学学报（理科版） ›› 2024, Vol. 48 ›› Issue (03) : 221 -230. DOI: 10.13764/j.cnki.ncdl.2024.03.009

单调线性权互补问题的新全牛顿步可行内点算法

迟晓妮, 杨玉萍, 刘三阳, 柳乐

作者信息 +

Author information +

文章历史 +

PDF

摘要

提出求解单调线性权互补问题(WLCP)的全牛顿步可行内点算法。基于线性优化的连续可微函数，给出中心方程的新等价形式，接着运用牛顿法求解定义中心路径的等价方程组，从而得到单调WLCP的新搜索方向。沿该搜索方向使用全牛顿步，无需进行线搜索。通过适当选取参数，分析了全牛顿步的严格可行性，证得算法是二次收敛的且具有多项式时间迭代复杂度。最后数值实验结果表明算法有效。