基于核函数求解一般Fisher市场均衡问题的全牛顿步可行内点算法

doi:10.15960/j.cnki.issn.1007-6093.2026.02.007

Abstract

Abstract: In this paper, we design and analyze a full-Newton step interior-point method (IPM) for solving the weighted linear complementarity problem (WLCP), which is general optimization of the Fisher market equilibrium problem. As a non-trivial generalization of the complementarity problem (CP), weight complementarity problem (WCP) can be used to model a wide range of equilibrium problems in economics, science and engineering. Since there are nonnegative weight vectors in WCP, the theory and algorithms of WCP are more complicated than CP. In this paper, the IPM for CP is extended to solve WCP. Based on a kernel function, search directions are obtained by applying Newton's method to the equivalent system, which defines the central path. Thus, a full-Newton step feasible IPM for general Fisher market equilibrium problem is proposed. At each iteration we only use full-Newton steps, which avoids the calculation of the step size. Under suitable assumptions, the algorithm is shown to have global convergence and polynomial complexity. Some numerical results are provided to support the practical efficiency of the proposed algorithm.

Key words: general Fisher market equilibrium problem, weighted linear complementarity problem, interior-point method, full-Newton step, kernel function, polynomial complexity

CLC Number:

O221

CHI Xiaoni, YANG Yuping, LIU Sanyang, YANG Qili. The full-Newton step feasible interior-point method for general Fisher market equilibrium problems based on a kernel function[J]. Operations Research Transactions, 2026, 30(2): 93-108.

References

[1] Baranzini R. Léon Walras, Elements of theoretical economics or the theory of social wealth [M]//Walker D A, van Daal J. (eds.) History of Political Economy, Cambridge: Cambridge University Press, 2017, 49(1): 161-164.
[2] Arrow K J, Debreu G. Existence of a competitive equilibrium for a competitive economy [J]. Econometrica, 1954, 22(3): 265-290.
[3] Brainard W C, Scarf H E. How to compute equilibrium prices in 1891[J]. The American Journal of Economics and Sociology, 2005, 64(1): 89-92.
[4] Eisenberg E, Gale D. Consensus of subjective probabilities: The pari-mutuel method [J]. The Annals of Statistics, 1959, 30(1): 165-168.
[5] Ye Y Y. Exchange market equilibria with Leontief’s utility: Freedom of pricing leads to rationality [J]. Theoretical Computer Science, 2007, 378(2): 134-142.
[6] Ye Y Y. A path to the Arrow-Debreu competitive market equilibrium [J]. Mathematical Programming, 2008, 111(1-2): 315-348.
[7] Anstreicher K M. Interior-point algorithms for a generalization of linear programming and weighted centring [J]. Optimization Methods and Software, 2012, 27: 605-612.
[8] Potra F A. Weighted complementarity problems|a new paradigm for computing equilibria [J]. SIAM Journal on Optimization, 2012, 22(4): 1634-1654.
[9] Nesterov Y, Shikhman V. Computation of Fisher-Gale equilibrium by auction [J]. Journal of the Operations Research Society of China, 2018, 6(3): 349-389.
[10] Potra F A. Sufficient weighted complementarity problems [J]. Computational Optimization and Applications, 2016, 64(2): 467-488.
[11] Chi X N, Gowda M S, Tao J Y. The weighted horizontal linear complementarity problem on a Euclidean Jordan algebra [J]. Journal of Global Optimization, 2019, 73(1): 153-169.
[12] Asadi S, Darvay Z, Lesaja G, et al. A full-Newton step interior-point method for monotone weighted linear complementarity problems [J]. Journal of Optimization Theory and Applications, 2020, 186(115): 864-878.
[13] Chi X N, Wang G Q. A full-Newton step infeasible interior-point method for the special weighted linear complementarity problem [J]. Journal of Optimization Theory and Applications, 2021, 190(1): 108-129.
[14] Kheirfam B. Complexity analysis of a full-Newton step interior-point method for monotone weighted linear complementarity problems [J]. Journal of Optimization Theory and Applications, 2024, 202: 133-145.
[15] Zhang J. A smoothing Newton algorithm for weighted linear complementarity problem [J]. Optimization Letters, 2016, 10: 499-509.
[16] Tang J Y, Zhang H C. A nonmonotone smoothing Newton algorithm for weighted complementarity problem [J]. Journal of Optimization Theory and Applications, 2021, 189(3): 679-715.
[17] Roos C, Terlaky T, Vial J P. Theory and Algorithm for Linear Optimization|An Interior Point Approach [M]. New York: John Wiley and Sons Inc, 1997.
[18] Darvay Z. New interior point algorithm in linear programming [J]. Advanced Modeling and Optimization, 2003, 5(1): 51-92.
[19] Kong L C, Xiu N H, Han J Y. The solution set structure of monotone linear complementarity problems over second-order cone [J]. Operations Research Letters, 2008, 36(1): 71-76.
[20] Liu H W, Yang X M, Liu C H. A new wide neighborhood primal-dual infeasible interior-point method for symmetric cone programming [J]. Journal of Optimization Theory and Applications, 2013, 158(3): 796-815.
[21] Dai Y H, Liu X W, Sun J. A primal-dual interior-point method capable of rapidly detecting infeasibility for nonlinear programs [J]. Journal of Industrial and Management Optimization, 2020, 16(2): 1009-1035.
[22] Peng J, Roos C, Terlaky T. Self-regular functions and new search directions for linear and semidefinite optimization [J]. Mathematical Programming, 2002, 93(1): 129-171.
[23] Bai Y Q, Ghami M E, Roos C. A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization [J]. SIAM Journal on Optimization, 2004, 15(1): 101-128.
[24] Wang G Q, Bai Y Q. A class of polynomial interior point algorithms for the Cartesian P -matrix linear complementarity problem over symmetric cones [J]. Journal of Optimization Theory and Applications, 2012, 152(3): 739-772.

The full-Newton step feasible interior-point method for general Fisher market equilibrium problems based on a kernel function

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 2

Recommended Articles

Metrics

Comments

[1]	LIU Changhe, SHANG Youlin, LI Jinrui. Path-following interior point algorithms based on wide neighborhoods and a new class of directions [J]. Operations Research Transactions, 2016, 20(1): 43-53.
[2]	ZHANG Jing, BAI Yanqin. Self-concordant exponential kernel function based interior point algorithm for second-order cone optimization [J]. Operations Research Transactions, 2014, 18(4): 11-24.