一种基于增广拉格朗日的并行分裂方法求解网络资源分配问题.pdf

2014年 12月 高 等 学 校 计 算 数 学 学 报 第 36卷第 4期 一 种基于增广拉格朗日的并行分裂方法求 解网络资源分配问题 木 王群 蔡邢菊 (南京师范大学数学科学学院，南京210023) 何洪津 (杭州电子科技大学理学院，杭州 310018) AN AUGM ENTED．LAGRANGIAN ．BASED PARALLEL SPLITTING M ETH0D FoR SoLVING NETW oRK RESoURCE ALL0CAT10N PR0BLEM S WangQun CaiXingju (SchoolofMathematicalSciences，NanjingNormalUniversity，Nanjing210023) HeHongjin (SchoolofScience，HangzhouDianziUniversity,Hangzhou310018) Abstract Thispaperpresentsanaugmented--Lagrangian--basedparallelsplitting methodfornetworkresourceallocationproblems，whichareimportantconstrained optimizationproblems．Theconvergenceofthem ethod isestablishedundersom e assumption，andpreliminarynumericalresultsdemonstratethereliabilityandef- ficiencyofthemethodinpractice． Key words splittingmethod，networkresourceallocationproblem ，variational inequality． AMS(2000)subjectclassifications 90C25，90C30，65K10 中图法分类号 0224 江苏省 自然科学基金 (B，江苏省高校 自然科学基金 (14KJB110015) 浙江省 自然科学基金 (LX14A010003)，杭州电子科技大学研究基金 (KYS075612037) 收稿 日期：2013—01一O3． 王群等：一种基于增广拉格朗日的并行分裂方法求解网络资源分配问题 第 4期 1 问题描述 网络资源分配问题是一类约束优化问题，网络具有一个有限容量的资源并且用户的 数量是有限的．当用户需要争夺资源，就需要一个控制机制来分配资源，避免网络拥塞．实 际中，需要尽量保证网络中的每个用户应该能够充分利用有限的资源，并且不会对网络中 其他用户造成不必要干扰，同时得到高的满意度．因此，每个用户的效用是通过一个与分 配给用户资源有关的函数来定义，每个用户的效用函数也可以被建模为分配给所有用户 资源的函数．每个用户的可行集被定义为一个欧氏空间的子集．所有用户的可行集的交集 称为分配资源的可行区域．如果用户的规格不同，比如处理器速度和存储容量的差异，他 们的效用函数和可行集也会各不相同．网络资源分配问题可以转化为在可行区域 内最大 化整体效用函数的一个问题． 我们研究的网络系统是多个用户共同控制和合作的网络，在这种设置下，用户网络是 以分布方式来优化全局 目标函数，受到全局和用户 自身的条件约束．当 目标函数是可分离 时，我们考虑 目标函数与 自身资源有关和与全局资源有关这两类问题． 我们考虑 5『]中的一个网络，由无向链集合c={1，… ，)和用户集合 ={1，… ，m) 组成，并且L m，每条链上的资源容量为 C1，定义与用户 i相连的链的集合为 L(i)cc， 与链2相连的用户