线性权互补问题基于核函数的全牛顿步可行内点算法

摘要

为求解科学和工程领域的一大类问题,基于核函数等价变换中心路径,提出求解R~n上线性权互补问题的全牛顿步可行内点算法。算法每次迭代无需进行线性搜索。算法基于核函数得到新的牛顿搜索方向,并定义了迭代点到中心路径的邻近测度。通过选择适当参数,分析了算法的可行性,证明了算法具有线性优化目前最好的多项式时间迭代复杂度。数值实验结果验证了算法的有效性。

关键词

线性权互补问题 / 可行内点算法 / 全牛顿步 / 迭代复杂度 / 核函数

基金资助

国家自然科学基金(11861026); 广西自然科学基金(2016GXNSFBA380102); 广西密码学与信息安全重点实验室基金(GCIS201819); 广西自动检测技术与仪器重点实验室基金(YQ18112)