中文

Operations Research Transactions >

2026 , Vol. 30 >Issue 2: 93 - 108

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2026.02.007

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

  • CHI Xiaoni ,
  • YANG Yuping ,
  • LIU Sanyang ,
  • YANG Qili
Expand
  • 1 School of Mathematics and Computing Science, Guangxi Colleges and Universities Key Laboratory of Data Analysis and Computation, Guilin University of Electronic Technology, Guilin 541004, Guangxi, China;
    2 School of Mathematics and Statistics, Xidian University, Xi'an 710071, Shaanxi, China;
    3 Center for Applied Mathematics of Guangxi (Guilin University of Electronic Technology), Guilin 541004, Guangxi, China;
    4 Guangxi Key Laboratory of Automatic Detecting Technology and Instruments, Guilin University of Electronic Technology, Guilin 541004, Guangxi, China

Received date: 2023-02-27

  Online published: 2026-06-12

Fold

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

Cite this article

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 . DOI: 10.15960/j.cnki.issn.1007-6093.2026.02.007

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.
Options
Outlines

/

〈 〉