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

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

运筹学学报（中英文） ›› 2026, Vol. 30 ›› Issue (2): 93-108.doi: 10.15960/j.cnki.issn.1007-6093.2026.02.007

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

迟晓妮^1,3,†, 杨玉萍^1,3, 刘三阳², 杨绮丽^1,4

1. 桂林电子科技大学数学与计算科学学院, 广西高校数据分析与计算重点实验室, 广西桂林 541004;
2. 西安电子科技大学数学与统计学院, 陕西西安 710071;
3. 广西应用数学中心 (桂林电子科技大学), 广西桂林 541004;
4. 桂林电子科技大学广西自动检测技术与仪器重点实验室, 广西桂林 541004

收稿日期:2023-02-27 发布日期:2026-06-12
通讯作者: 迟晓妮 E-mail:chixiaoni@126.com
基金资助:
国家自然科学基金 (No. 11861026), 广西自然科学基金 (No. 2021GXNSFAA220034)

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

CHI Xiaoni^1,3,†, YANG Yuping^1,3, LIU Sanyang², YANG Qili^1,4

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:2023-02-27 Published:2026-06-12

摘要/Abstract

摘要： 给出全牛顿步可行内点算法(interior-point method,IPM)求解一般Fisher市场均衡问题的线性权互补问题(weighted linear complementarity problem,WLCP)模型。作为互补问题(complementarity problem,CP)的非平凡推广,权互补问题(weight complementarity problem,WCP)可以建模经济、科学和工程等领域中更广泛的一大类均衡问题。然而,WCP中存在非负权向量,使得WCP的理论和算法比CP更复杂。本文推广CP的IPM来求解WCP。基于一个核函数,得到定义中心路径的等价方程组,运用牛顿法求解该方程组得新搜索方向,从而提出求解一般Fisher市场均衡问题的全牛顿步可行IPM。算法采用全牛顿步,因而无需计算步长。在适当的假设下,证明算法全局收敛且具有多项式复杂度。最后数值算例验证了算法的有效性。

关键词: 一般Fisher市场均衡问题, 线性权互补问题, 内点算法, 全牛顿步, 核函数, 多项式复杂度

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

中图分类号:

O221

迟晓妮, 杨玉萍, 刘三阳, 杨绮丽. 基于核函数求解一般Fisher市场均衡问题的全牛顿步可行内点算法[J]. 运筹学学报（中英文）, 2026, 30(2): 93-108.

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.

参考文献

[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.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

本文评价

[1]	杨洋, 罗洪林, 罗慧林. 关于半定规划的一种宽邻域不可行内点算法的注记[J]. 运筹学学报, 2016, 20(2): 79-87.
[2]	张景, 白延琴. 二阶锥规划的基于自协调指数核函数的原始-对偶内点算法[J]. 运筹学学报, 2014, 18(4): 11-24.