A Constrained Second-order Inertial Edge-flow Resource Competition Model: Conservation, KKT Equilibria, and Bounded Dominant Concentration
-
摘要: 针对一阶赢者通吃竞争模型难以兼顾惯性效应、状态约束与优化解释, 研究资源总量守恒与箱体约束下的分布式非凸资源分配问题. 为此, 对Hill型效用引入对数障碍正则化, 以图边流动量为中间状态构建二阶惯性边流资源竞争模型. 模型保持资源总量守恒, 并基于局部边际效用实现分布式交互. 随后, 通过能量函数和LaSalle不变性原理, 证明可行内点集正不变、系统能量单调耗散, 且系统轨迹收敛至平衡点集合. 进一步建立动力学平衡点与正则化问题KKT条件的对应关系, 并证明当障碍参数趋于零且对偶变量有界时, 平衡点极限恢复原问题的KKT结构. 此外, 在Hill边际效用饱和区, 给出能力参数与稳态资源分配之间的条件排序性质. 数值结果表明, 模型在保持约束的同时形成有界优势资源集聚.
-
关键词:
- 二阶惯性边流资源竞争模型 /
- 非凸资源分配 /
- 资源守恒
Abstract: This paper studies the distributed nonconvex resource allocation problem under total-resource conservation and box constraints, addressing the inability of first-order winner-take-all competition models to jointly capture inertia effects, state constraints, and an optimization interpretation. To this end, a logarithmic barrier regularization is introduced for Hill-type utilities, and a second-order inertial edge-flow resource competition model is constructed using graph edge-flow momentum as an intermediate state. The model preserves total-resource conservation and realizes distributed interaction based on local marginal utilities. Then, using an energy function and LaSalle＇s invariance principle, we prove positive invariance of the feasible interior set, monotonic dissipation of system energy, and that the system trajectory converges to the equilibrium set. We further establish the correspondence between dynamical equilibria and the KKT conditions of the regularized problem, and prove that, as the barrier parameter approaches zero and the dual variables are bounded, the equilibrium limits recover the KKT structure of the original problem. In addition, in the saturation region of the Hill marginal utility, we derive a conditional ordering property between capability parameters and steady-state resource allocations. Numerical results show that the model forms bounded dominant resource concentration while preserving constraints. -
图 1 固定障碍参数下的状态演化与约束保持
Fig. 1 State evolution and constraint preservation for a fixed barrier parameter
图 2 固定障碍参数下的性能指标与收敛行为
Fig. 2 Performance metrics and convergence behavior for a fixed barrier parameter
图 3 障碍参数扫描下的平衡分配与乘子趋势
Fig. 3 Equilibrium allocations and multiplier trends under a barrier-parameter sweep
图 4 障碍参数趋于零时的KKT残差验证
Fig. 4 Verification of KKT residuals as the barrier parameter approaches zero
表 1 初值与稳态资源分配对比($ \mu=0.020 $)
Table 1 Comparison of initial and steady-state resource allocations ($ \mu=0.020 $)
智能体$ i $ 能力参数$ c_i $ 初始资源$ x_i(0) $ 稳态资源$ x_i^\ast $ 1 1.00 0.41 0.060 9 2 1.20 0.38 0.062 3 3 1.45 0.32 0.227 3 4 1.70 0.29 0.309 9 5 2.00 0.27 0.366 7 6 2.35 0.25 0.416 8 7 2.70 0.24 0.458 0 8 3.10 0.24 0.498 0 
下载: 导出CSV
表 3 $ \mu $扫描下的平衡与残差指标
Table 3 Equilibrium and residual metrics under the $ \mu $ sweep
$ \mu $ $ \lambda^\ast(\mu) $ $ \max|{\rm{stat}}| $ $ \max|{\rm{comp}}| $ $ \max|B^{{\rm{T}}} h_\mu| $ $ \max(\mu_i^+,\;\mu_i^-) $ 0.080 2.960625 $ 6.61\times 10^{-10} $ $ 8.0\times 10^{-2} $ $ 8.17\times 10^{-10} $ 1.7007 0.040 2.809298 $ 9.16\times 10^{-10} $ $ 4.0\times 10^{-2} $ $ 1.31\times 10^{-9} $ 1.7715 0.020 2.742712 $ 1.45\times 10^{-9} $ $ 2.0\times 10^{-2} $ $ 2.29\times 10^{-9} $ 1.8310 0.010 2.710407 $ 6.44\times 10^{-9} $ $ 1.0\times 10^{-2} $ $ 1.07\times 10^{-8} $ 1.8626 0.005 2.694130 $ 1.73\times 10^{-8} $ $ 5.0\times 10^{-3} $ $ 2.94\times 10^{-8} $ 1.8783
下载: 导出CSV
表 2 随机初始条件和模型参数扰动下的统计结果
Table 2 Statistical results under random initial conditions and model-parameter perturbations
扰动类型 有效比例 $ J(x^\ast) $ 收敛时间(s) 峰值边流 排序一致率 随机初值组 1.00 $ 7.452\,10\pm0.010\,11 $ $ 1.97\pm0.28 $ $ 0.332\,19\pm0.080\,14 $ $ 1.000\pm0 $ 能力参数组 1.00 $ 7.437\,15\pm0.256\,18 $ $ 2.78\pm1.07 $ $ 0.355\,16\pm0.034\,15 $ $ 1.000\pm0$ Hill参数组 1.00 $ 7.256\,15\pm1.653\,11 $ $ 2.87\pm1.30 $ $ 0.336\,19\pm0.035\,19 $ $ 1.000\pm0 $
下载: 导出CSV
表 4 一阶/二阶模型与阻尼系数比较
Table 4 Comparison of the first-order and second-order models under different damping coefficients
模型 $ \alpha $ $ J(x^\ast) $ 收敛时间(s) 峰值边流强度 一阶约化流 0 7.447 979 3.06 0 二阶惯性流 4 7.475 509 2.78 0.487 5 二阶惯性流 8 7.447 979 2.00 0.357 0 二阶惯性流 12 7.447 979 4.12 0.279 5 二阶惯性流 20 7.447 979 7.40 0.192 7
下载: 导出CSV
表 5 不同网络拓扑和随机边权的平衡与敏感度分析
Table 5 Equilibrium and sensitivity analysis under different network topologies and random edge weights
拓扑 $ J(x^\ast) $ 收敛时间(s) 活跃分量数 边际失配 链式图 7.447979 35.04 1 $ 2.19\times 10^{-10} $ 环形图 7.447979 11.74 1 $ 3.04\times 10^{-9} $ 加边环形图 7.447979 2.00 1 $ 1.16\times 10^{-9} $ 完全图 7.447979 1.50 1 $ 6.04\times 10^{-9} $ 星形图 7.447979 6.32 1 $ 6.46\times 10^{-9} $ 随机边权加边环 7.447979 2.40 $ \pm $ 0.59 1 $ 1.73\times10^{-15} $
下载: 导出CSV
表 6 总资源变化对优势集聚结构的影响
Table 6 Effect of total-resource variation on the structure of dominant resource concentration
$ C_{{\rm{total}}} $ $ J(x^\ast) $ 下边界节点数 活跃节点数 前3节点资源占比 1.8 5.826 937 0 8 0.690 1 2.4 7.447 979 0 8 0.572 0 3.0 8.831 312 0 8 0.516 9 3.6 9.982 043 0 8 0.474 7
下载: 导出CSV
表 7 20个智能体完全图稳态资源排序
Table 7 Steady-state resource ranking for complete graph of 20 agents
排名 节点$ i $ 能力参数$ c_i $ 稳态资源$ x_i^\ast $ 1 20 3.400 0 0.389 7 2 19 3.273 7 0.377 6 3 18 3.147 4 0.364 8 4 17 3.021 1 0.351 1 5 16 2.894 7 0.336 3
下载: 导出CSV
-
[1] Lotka A J. Elements of Physical Biology. Baltimore: Williams and Wilkins, 1925. [2] Volterra V. Variations and Fluctuations in the Number of Individuals in Animal Species Living Together. New York: McGraw-Hill, 1927. [3] Grossberg S. Competition, decision, and consensus. Journal of Mathematical Analysis and Applications, 1978, 66(2): 470−493 doi: 10.1016/0022-247X(78)90249-4 [4] Hirsch M W. Systems of differential equations which are competitive or cooperative: I. Limit sets. SIAM Journal on Mathematical Analysis, 1982, 13(2): 167−179 doi: 10.1137/0513013 [5] Maass W. On the computational power of winner-take-all. Neural Computation, 2000, 12(11): 2519−2535 doi: 10.1162/089976600300014827 [6] Maurer S M, Huberman B A. Competitive dynamics of web sites. Journal of Economic Dynamics and Control, 2003, 27(11−12): 2195−2206 doi: 10.1016/S0165-1889(02)00121-5 [7] Noe T, Parker G. Winner take all: Competition, strategy, and the structure of returns in the internet economy. Journal of Economics & Management Strategy, 2005, 14(1): 141−164 doi: 10.2139/ssrn.250371 [8] Liu S B, Wang J. A simplified dual neural network for quadratic programming with its KWTA application. IEEE Transactions on Neural Networks, 2006, 17(6): 1500−1510 doi: 10.1109/TNN.2006.881046 [9] Liu Q S, Wang J. Two k-winners-take-all networks with discontinuous activation functions. Neural Networks, 2008, 21(2): 406−413 doi: 10.1016/j.neunet.2007.12.044 [10] Li S, Li Y M, Wang Z. A class of finite-time dual neural networks for solving quadratic programming problems and its k-winners-take-all application. Neural Networks, 2013, 39: 27−39 doi: 10.1016/j.neunet.2012.12.009 [11] 杨涛, 柴天佑. 分布式协同优化的研究现状与展望. 中国科学: 技术科学, 2020, 50(11): 1414−1425 doi: 10.1360/SST-2020-0040Yang Tao, Chai Tian-You. Research status and prospects of distributed collaborative optimization. Science China Information Sciences, 2020, 50(11): 1414−1425 doi: 10.1360/SST-2020-0040 [12] Li S, Zhou M C, Luo X, You Z H. Distributed winner-take-all in dynamic networks. IEEE Transactions on Automatic Control, 2017, 62(2): 577−589 doi: 10.1109/TAC.2016.2578645 [13] 陈刚, 李志勇. 集合约束下多智能体系统分布式固定时间优化控制. 自动化学报, 2022, 48(9): 2254−2264 doi: 10.16383/j.aas.c190416Chen Gang, Li Zhi-Yong. Distributed fixed-time optimization control for multi-agent systems with setconstraints. Acta Automatica Sinica, 2022, 48(9): 2254−2264 doi: 10.16383/j.aas.c190416 [14] Zhang Y Y, Li S, Xu B, Yang Y. Analysis and design of a distributed k-winners-take-all model. Automatica, 2020, 115: Article No. 108868 doi: 10.1016/j.automatica.2020.108868 [15] 时侠圣, 林志赟. 基于固定时间的二阶智能体分布式优化算法. 北京航空航天大学学报, 2023, 49(11): 2951−2959 doi: 10.13700/j.bh.1001-5965.2022.0060Shi Xia-Sheng, Lin Zhi-Yun. Fixed-time distributed convex algorithm over second-order multi-agent systems under bounded disturbances. Journal of Beijing University of Aeronautics and Astronautics, 2023, 49(11): 2951−2959 doi: 10.13700/j.bh.1001-5965.2022.0060 [16] Zhang Y, Li S, Weng J. Distributed k-winners-take-all network: An optimization perspective. IEEE Transactions on Cybernetics, 2023, 53(8): 5069−5081 doi: 10.1109/TCYB.2022.3170236 [17] 吴庆涛, 朱军龙, 葛泉波, 张明川. 一种基于条件梯度的加速分布式在线学习算法. 自动化学报, 2024, 50(2): 386−402Wu Qing-Tao, Zhu Jun-Long, Ge Quan-Bo, Zhang Ming-Chuan. An accelerated distributed online learning algorithm based on conditional gradient. Acta Automatica Sinica, 2024, 50(2): 386−402 [18] 时侠圣, 孙长银, 穆朝絮. 扰动线性多智能体系统的分布式资源分配算法. 中国科学: 信息科学, 2024, 54(4): 911−926 doi: 10.1360/SSI-2023-0093Shi Xia-Sheng, Sun Chang-Yin, Mu Chao-Xu. Distributed resource allocation algorithms for linear multi-agent systems with disturbances. Science China Information Sciences, 2024, 54(4): 911−926 doi: 10.1360/SSI-2023-0093 [19] Huang Y, Fang W T, Chen Z Y, Li Y G, Yang C H. Flocking of multiagent systems with nonuniform and nonconvex input constraints. IEEE Transactions on Automatic Control, 2023, 68(7): 4329−4335 doi: 10.1109/tac.2022.3206117 [20] Huang Y, Duan M M, Mo L P. Multiagent containment control with nonconvex states constraints, nonuniform time delays, and switching directed networks. IEEE Transactions on Neural Networks and Learning Systems, 2019, 31(11): 5021−5028 doi: 10.1109/tnnls.2019.2955678 [21] Chen Z Y. Winners take all: A reverse consensus model. arXiv preprint arXiv: 2409.12407, 2024. [22] Cao X W, Yang Y G, Li S, Stanimirović P S, Katsikis V N. A novel competition model for dynamic winner-take-all. International Journal of Systems Science, DOI: 10.1080/00207721.2025.2568717 -
下载:
计量
- 文章访问数: 105
- HTML全文浏览量: 62
- PDF下载量: 13
- 被引次数: 0
