一类线性权互补问题的修正全牛顿步可行内点算法

摘要

作为互补问题的推广,权互补问题是一种重要的优化问题,可以建模一大类经济金融中的实际均衡问题。由于非零权向量的存在,权互补问题比互补问题复杂得多,因而目前关于权互补问题的算法并不多见。将线性优化的内点算法推广到权互补问题。基于中心路径的等价变换,提出求解非负象限上一类线性权互补问题的修正全牛顿步可行内点算法。在每次迭代时,算法无需进行线性搜索。在适当假设下,证明了算法的可行性,得到了算法的迭代复杂度。数值实验结果表明了算法的有效性。

关键词

权互补问题 / 修正全牛顿步 / 可行内点算法 / 迭代复杂度