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

A full-modified-Newton step feasible interior-point algorithm for a class of linear weighted complementarity problems

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

As the extension of a complementarity problem,the weighted complementarity problem is an important kind of equilibrium problem,which could be used to model a larger class of practical equilibrium problems in economy and finance.Because of the nonzero weight vector,the weighted complementarity problem is usually more complicated than the complementarity problem.There is little available work about the algorithms for the weighted complementarity problem.In this paper,an interior-point algorithm is extended from linear optimization to weighted complementarity problems.Based on an equivalent reformulation of central path,a full-modified-Newton step feasible interior-point algorithm is proposed for solving a class of linear weighted complementarity problems over the nonnegative orthant.There is no linear search at each iteration.Under appropriate assumptions,we prove the feasibility of the algorithm,and obtain the iteration complexity.The numerical results illustrate that the algorithm is effective.