给出全牛顿步可行内点算法(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。算法采用全牛顿步,因而无需计算步长。在适当的假设下,证明算法全局收敛且具有多项式复杂度。最后数值算例验证了算法的有效性。
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.
[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.
北大中文核心期刊