Fisher市场均衡问题的新全牛顿步可行内点算法

A New Full-Newton Step Feasible Interior-Point Algorithm for Solving the Fisher Market Equilibrium Problem

【目的】基于光滑中心路径的等价变换,提出一种新的求解Fisher市场均衡问题的线性权互补(Weighted linear complementarity problem, WLCP)模型的全牛顿步可行内点算法。【方法】扰动WLCP,构造光滑中心路径的新代数等价形式,运用牛顿法得到新搜索方向,从而提出求解Fisher市场均衡问题的全牛顿步可行内点算法。【结果】算法采用全牛顿步避免线搜索,提高计算效率,且具有可行性和多项式复杂度。【结论】初步数值结果表明算法有效。

[Purposes]Based on the equivalent transformation of smooth central path, a new full-Newton step feasible interior-point algorithm is presented to solve the weighted linear complementarity model of the Fisher market equilibrium problem. [Methods] By perturbing WLCP, the new algebraic equivalent transformation of smooth central path is constructed, and a new search direction by Newton’s method is obtained. Then a full-Newton step feasible interior-point algorithm for solving the Fisher market equilibrium problem is proposed. [Findings] The algorithm uses the full-Newton steps to avoid linear search and improve computational efficiency. It shows the feasibility and polynomial complexity of the algorithm. [Conclusions] Preliminary numerical results indicate that the algorithm is effective.