（计算数学专业论文）dsl系统谱管理的几种模型及解法.pdf

ab s t r a c t ii ab s t r a c t i n m o d e m d i g i t a l s u b s c r i b e r l i n e s ( d s l ) s y s t e m s w h e r e m u l t i p l e u s e r s m u s t c o - e x i s t i n t h e s a m e fr e q u e n c y b a n d , c r o s s t a l k i n t e r f e r e n c e i s t h e d o m i n a n t s o u r c e o f p e r - f o r m a n c e d e g r a d a t i o n . d y n a m i c s p e c t r u m m a n a g e m e n t i s a n e ff e c t i v e t e c h n i q u e f o r r e d u c i n g c r o s s t a l k i n t e r f e re n c e a n d i m p r o v i n g t o t a l s y s t e m t h r o u g h p u t . i t e r a t iv e w a - t e r f i l l i n g a l g o r i t h mo wf a ) , o n e o f t h e e a r l i e s t p r o p o s e d d y n a m i c p o w e r c o n tr o l a l g o- r it h m , s e q u e n t ia l l y l e t e a c h u s e r l o c a l l y m e a s u r e t h e t o ta l n o i s e p l u s i n t e r f e r e n c e p o w e r s i n a l l fr e q u e n c i e s a n d o p t i m a l l y a ll o c a t e i t s p o w e r a c r o s s fr e q u e n cy t o n e s a c c o r d i n g t o a w a t e r fi l l i n g p r o c e d u r e t o m a x i m i z e i t s o w n a c h i e v a b l e r a t e . i n t h i s t h e s i s w e a l s o p r e s e n t a s i m u l t a n e o u s i wf a , l e t a l l u s e rs s i m u l t a n e o u s l y r u n t h e i r c o r r e s p o n d i n g w a - t e r fi l l i n g p r o c e d u r e s t o m a x i m i z e t h e i r r e s p e c t i v e ra t e s . t h e n it c o u l d b e d e s i g n e d a s a p a r a l l e l a l g o r i t h m a n d m a y c o s t l e s s t i m e t h a n t r a d i t i o n a l s e r i a l a l g o r it h m . a l t h o u g h i w f a i s w e l l kn o w n f o r i t s l o w c o m p l e x i t y a n d r a p i d c o n v e r g e n c e s p e e d , t h e s o l u t i o n g e n e ra t e d b y i w f a i s n o t o p t i m a l i n g e n e r a l . i n a d d i t i o n w e w i l l s t u d y t h e o p t i m a l s p e c tr u m m a n a g e m e n t b a s e d o n t h e m u l t i -ob j e c t iv e p r o g r a mm i n g , o b t a i n s o m e p a r e t o s o l u t i o n s g e n e r a t e d fr o m l i n e a r w e i g h t e d s u m mo d e l , p r i m a r y o b j e c t i v e m o d e l a n d i d e a l p o i n t m o d e l , r e s p e c t i v e l y . k e y w o r d s : d s l , s p e c t r u m m a n a g e m e n t , i w f a , m u l t i -o b j e c t i v e p r o g r a m m i n g 南开大学学位论文版权使用授权书 本人完全了 解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容:按照学校要求提交学位论文的印刷本和电子版 本;学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、 数字化或其它手段保存论文; 学校有权提供目 录检索以及提供 本学位论文全文或者部分的阅览服务; 学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版; 在不以 赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学 位 论 文 储 签 名 : a -l 16 7 4 4 刁年了 月 如日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名:学位论文作者签名: 解密时间:年月日 各密级的最长保密年限及书写格式规定如下: “ 部5 年 最 长 5 年 可 少 于 5 年 ， 秘 密 * 10 年 最 长 10 年 ， 可 少 于 0 年 2 o 呈 馒 竺 竺 五型士 2 0 w ) 南开大学学位论文原创性声明 本人郑重声明:所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果.除文中已 经注明引用的内 容外，本学位论文的研究成果不包含 任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉 及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学 位论文原创性声明的法律责任由本人承担。 学 位 论 文 作 者 签 名 : 6 1 4 ) 甲7 年了 月zo 日 第一章 绪论 第一章绪论 数字用 户线( d i g i t a l s u b s c r i b e r l i n e s , d s l ) 技 术 1 2 ， 是一 种利用普 通电 话 线实现宽带网络接入的技术， 它是目前全球普通消费者主要使用的宽带上网技术 之 一 它 包括普 通d s l , i -i d s l ( 高比 特率d s l ) , s d s 以 单线d s l ) a d s l ( 不对 称 d s l ) , v d s l ( 超高比 特率d s l ) 等多 种接入技术 . 这些接 入技术的 基础系统 架构 与原理基本上是相似的， 只是在信号传输速率与距离、 具体实现方式及上、 下行 速率的对称性等方面有所区别， 适用于不同用途用户选择. 在一个d s l系 统中， 信息 在用户端调制 解调器伽o d e m ) 和中 心局( c e n t r a l o ff i c e ) 调 制解调 器间 传输， 其间以双 绞线连接， 多 条双 绞线组成扎， 多个 扎组成 一条电缆. 由于同一电缆内各线对物理地绑定在一起， 就产生了电磁祸合效应， 导 致 线对间 均存 在不同 程度的串 扰( c r o s s t a l k ) . 串 扰的作 用相当 于噪声， 在功能上 等 效于增加了 信道的 损耗， 会降低 信噪比 和系 统 容量. 故而串扰是限 制d s l 系统 传输吞吐能力提高的一个重要因素. 能量谱管理指通过能量控制的办法来减弱串扰对系统性能的负面效应. 传统 的静 态谱 管理( s t a t i c s p e c t r u m m a n a g e m e n t , s s m ) ， 由 于 对所有的d s l 调制解调 器都 使用同样的 谱 面具( s p e c t r u m m a s k ) ， 此谱 面具 是基于 最坏情况 考虑的 ， 故 这 些 谱面具限 制过 于严 格， 以 致结 果不 够理想 3 1 . 而 动态 谱管理( d y n a m i c s p e c t r u m m a n a g e m e n t , d s m ) 4 , 5 , 6 , 7 , 8 , 9 , 1 0 , 川， 则是根 据具 体的 信道特点 及串 扰活 动， 动态地调整用户线间的可用资源， 进而减弱串扰效应， 最大化系统吞吐量. 动态谱 管 理的 核心在 于通 过先进的网 络优 化技术提供 最优 的资 源分配和传 输效果【 1 2 1 . 迭代充 水法( i t e r a t i v e w a t e r fi l l i n g a l g o r i t h m , i w f a ) 4 5 1 是 最早提出的 动态 谱 管 理算法之 一， 是一 种分 布式的能 量控 制方法， 即 不需 借助谱管理中 心( s p e c t r u m m a n a g e m e n t c e n t e r , s m o进行中 央控制， 各个 用户 只需 知道自 身 各信道 传输系数 及总 干扰即 可. i w f a采用的 是博弈论思想， 让各个 用户依次根据充水 法调整自 己 的能量 分配， 不考 虑其他 用户， 贪婪得使自 身 数据 速率达最大. ( 4 5 1 和 8 1 9 1 分别讨论了两个用户和多个用户情况下这个d s l博弈的n a s h 均衡点的存在唯一 性问 题. 本文还 将提出一 种同 步的 迭代充水法， 也就 是每次 迭代中 让各 个用 户同 时执行各自的充水法， 这样就可以采用并行算法来执行， 在用户数量较多的情况 第一章 绪论 下， 就可能会比传统的串行算法花费更短的时间. i wf a算法的主要优点是其收 敛 速度 快， 但由 于是各用户皆 贪婪地 追求自 身 利益 最大化， 这样并 不能 保证 整体 最 优， 所以由 此求出 的均衡 点并非问 题的最 优解. 度量系 统吞吐量 最典 型的尺 度是所有 用户数 据速率 之和 但 这个在 各自 能量 约束下最大化速率和的问题是个可能有多个局部最优点的非凸问题 若直接采用 搜索法， 必将导致算法关于用户数和子信道总数皆为指数次幕复杂度. 而通常这 个子信道总数很大， a d s l 系统中子信道数是2 5 6 ， 而 v d s l系统中是 4 0 9 6 . 这 样， 就导致了 计算 机上不易处理 . l 3 中提出 了 一种模拟 退火算法， 以 期求出 一 个全局最优能量分配解， 但这种方法缺乏严谨的数学论证与分析， 不能保证收敛 到 全局最优， 而且收敛速度 还比 较慢 . 1 4 考虑每 个子 信道各为某 个用户所 独占 这种情形下的速率和最大问题， 对干扰系数、 噪音及能量预算作相关假定后， 使 得这样求出的解为局部最优解. 6 中 提出 了 一 种 采 用 对 偶 分 解 法 的 最 优 谱 管 理( o p tim a l s p e c tr u m m a n a g e - m e n t , o s m ) 方法， 其算法关 于子信道 总数是 线性而非 指数次 复杂 度， 虽然关于 用 户 数还是 指数次幂 复杂度， 但 在用户 数不大的 情况 下， 就容 易在 计算 机上 执行. 这 个最优谱管理算法求出的解， 是系统中各用户数据速率间的可能的最好的平衡， 能达 到数据速率域 边界上的任意 速串组 合. 1 5 还 在此基 础上 提出 在所有用户 总 能量预算这个单约束条件下的最优谱管理模型及算法. 本文的结构安 排如下: 本章剩 下部分 将给出d s l 系统模型 及相关 概念和符 号; 在 第二章我们从 博弈论的角 度讨 论谱管理问 题， 给出i w f a算 法及收 敛性分 析， 并提出可并行化的i wf a算法; 在第三章我们将从多目标规划的角度来考虑 最优谱管理问题， 提出线性加权和模型、 主目 标模型、 理想点模型等不同意义下 最优解求法; 最后一章我们将从数值例子结果总结比较前面这些算法， 并提出今 后可能的研究方向. 系统模型 假设系 统中包 含n条线路， 亦即n个 用户端， 且 都采 用离散 多音 频( d is c r e t e m u l t i - t o n e , d m 劝调 解技术， 即 信道被 分成k个并 行独 立子信 道， 独 立地传抬 信 号. 在高 斯干扰的假定下， 在每个信道 上， 每个 用户都 将来自 其 他用户的 干扰与 加性噪音之和一起视为高斯噪音. 这样第 1 i n ) 用 户在第斌1 k - 。 口 尹 0 表 示 信 道k 上 用户9 对用 户i 的串 音干扰系数， 咋0 表示 用户2 分配到 信道k 上的 传翰信号 能 量 . 记 向 量8 i 会8 1 , 8 2 , . . . ， 9 k ) t 指 用 户云 的 能 量 谱向 量 . k 这 样 用 户 的 数 据 速 率 凡 一 艺b k 就 是 关 于 si 口 = 1 , 2 ， 一 ， n ) 的 函 数 ， 即 a . (5 1 , 8 2 , s n ) 一 艺10 9 2 4 + 9 11 - ki 十- f - a ;j ( 1 . 2 ) 各用户还有各自 的能量预算， 表示为 艺4 k p te, v i 一 1 , 2 ， 一n ( 1 . 3 ) 其中欣 ， “ 0 , k = 1 , 2 , x l r 9 k 1 . j #+ ， k ( 2 . 1 ) 第二章 基于博弈论的d s l谱管理问题 笋.3 d s l 博弈模型对应的i wf a算法 从上 述模型问题可以 看出， 预先 给定所有 能量谱向 量护 0=1 , 2 , . , 川 初 始 值， 然后 对每 个用户依次 求解形 如( 2 . 1 ) 的 模型问 题， 依 此循环下 去， 若由 此产 生的点列收敛， 易见收敛点必定是该d s l博弈的纳什均衡点. 下 面先 考虑用 户i 的 模型问 题( 2 . 1 ) 的k u h n - t u c k e r ( k - t ) 条件. k 令牙 ， 风( “ 一1 , 2 , . . . , 叼分 别 对 应 不 等 式艺雌p . 和雌全“ 的 介 -1 l a g ra n g e 乘 子， 另 外 前 面 系 统 模 型 中 定 义 的a 护只 是 对j 尹 有 意 义 的 ， 不 失 一 般 性 ， 我 们 定 义j = 葱 时 其 值皆 为1 ， 亦 即 对 任 意 的k 二 1 , 2 , , , , k , 二1 ,2 ， 二， n 都 有吐 =1 ， 这 样( 2 . 1 ) 的k - t 条 件 为 : 兴- 一羊一十 x 一 瘫 一 。 ， d k = 1 ,2 , - -,k ” j 声 ， 吐+ 乞 叮 0 * 1 p ; 一 艺s 1 0 0:5 t o ,土s , _ 0 , k =l d k =1 , 2 , ， k 将上 面第一式中风代入第 三式中， k - t 条 件即 化为 0 _ 0 , i n 2 b k =1 , 2 , . . . , k 2)3) (2(2 a k + e crk o 0 命题 2 . 3 . 1问题 ( 2 . 1 ) 的k - t 条件 ( 2 . 2 ) 等价于: 3 0 er使得满足 ” 旅1 吐 十 艺心咬 十 沪 全 。 ， b k = 1 , 2 , . . . , k j =1 e 9 k = p . 证明 . 先 证( 2 .2 ) = - ( 2 . 3 ) 第二章 基于博弈论的d s l谱管理问题 由 于 c -, + 艺昭9 k “ ， 根 据(2 .2 ) 第 一 式 右 边 可 知a 。 必 成 立 ， 再 由 (2 .2 ) 第 二 式 ， 则 有艺8 1, 一 p m “ 成 立 ， 即 得 到 了 (2 .3 ) 第 二 式 取 “ = _ 1(in 2 ) a 即厂 =一 舔 ， 代 入 (2.2) 第 一 式 ， 再 由 v 0 , 则 有 0 成一q k + 又心砍 + v 0 j = 1 成立， 这正是( 2 . 3 ) 第一 式， 这样就由( 2 . 2 ) 式证得了( 2 . 3 ) 式. 反 过 来 ， 由 (2 .3 ) 证 (2 .2 )， 只 需 令 ” 一 命 即 可 事 实 上 ， (2 .3 ) 本 身 已 暗 含 了 v 0 ， 则 吐 + 艺心咬 + .t j = 1 。 ， 那么 根据( 2 . 3 ) 第一 式必成立8 k 二0 ( v k =1 , - - , k ) ， 也就 得到 这与( 2 . 3 ) 第二 式矛盾， 故v 0 , ( 2 .2 ) 两式也显 然成立 . 命题2 . 3 . 2问 题( 2 . 1 ) 存在唯一 解， 可表示为 s k 一 二 0 ， - v 一 ( q k + 艺a k ) , v k = 1 , 2 , 其中， v满足 艺m a x 0 ， - v 一 (q k 十 艺心动 一 p .- k =1j 笋 i , x ( 2 .a ) ( 2 . s ) 证明. 由 于目 标函 数凡 为 有界闭凸 集s i 上严格凹 函数， 则必存 在唯一全局极大 点 ， 设为8 t . 那 么 必 存 在 一 组l a g r a n g e 乘 子 使 得 其 与歹满 足k -t 条 件( 2 .2 ) ， 根 据 命 题2 .3 .1 知， 必 存 在 一 个0 使得夕， ,v ) 满 足(2 .3 ) ， 即 满 足 第二章 基于博弈论的 d s l谱管理问魔 “ s k 1 3 k + a k + e心成 + v 0 , b k 一 1 , 2 , . . . , k . 将上式写成 (a)( 若 艺 a l 0 , b k =1 , 2 , . . . , k , 艺8 k = p . , k = 1 。 g ( 0, )仁 1 e r n k ， 其 中o o ( a k ) 艇 1 ， a a ( a ij ) i,9 n .1 = = 1 是n k x n k阶 分 块 矩 阵 ， 其 中妙 a d ia g (心) 艇 1 是kx k对 角 阵滋意 : a “ 是 单 位 阵 ). 可以 看出仿 射变分 不等式( a ff i n e v a ri a t i o n a l i n e q u a li t y , a v i ) : 求解。 e x， 使 得对 v s ex都成立: ( e 一s , o + a s ) _ 0 ( 2 . s ) k 的 k - t 条 件 正 是 (2 .3 ) ， 其 中 的 v 对 应ea k 一 4 的 l a g ra n g e 乘 子 于 是 ， 再 抢 =i 根据( 2 . 3 ) 和( 2 . 2 ) 的 等价性知， s 是模型问 题( 2 . 1 ) 的 解( d s l 博 弈的n a s h 平衡) 当 且仅当s 是 上面a v i 问 题的解 1 9 . 记 上述a v 为a v i ( x , o , a ) . 命 题2 . 4 . 1 s = ( s ); 是a v i ( x , o , a ) 的解， 当 且仅当 对v i =1 , 2 ， 二 ， n , s 都 满足 ( 6 一 s ， o + 艺 a j s j ) 。 v s 任 s , .( 2 . 乃 i = i 证明 . 充分性显 然. 下面证明 必要性， 设。 =夕) 江 ; 是a v i ( x , o , a ) 的 解. 对v i =1 , 2 , - . . , n , vs e 氏 ， 取8 t = s (v 1 76 i ) ， 则 对 这 样 的s = ( s 勺 仁 1 0 ( s 一 s , o r + a s ) 第二章 基于博弈论的d s l谱管理问题 =艺(s , 一 s t, 01 + 艺a ij s ) i=1 j = 1 一( s 一 s i ， a i + 又a s j ) 定义p n ( . ) 表 示到空间q 上的欧 几里 得投影 算子， 亦即 p n ( x ) =a r il - 2 n y e n “ 二 一， i i 已知投影算子有个如下基本性质: ( x 一 p n ( x ) , p n ( x ) 一 ， ) 0 , v y e n 另外， 若存 在z n使得 ( 二 一 z , : 一功 0 ,勺 e 1 z 则该z 为x 在f 2 上的投影， 即z = p n ( 劝 . 现在再 来 看( 2 .7 ) 式， 由 于a i i =i 单 位阵， 故 。 (s . 一 a i f a i + e a .0 ) j = 1 =(。 陀 一 $ i s i + o i + 艺a j s j ) j 肖 =( 3 ,i 一 4 i , 4 i 一 ( - q i 一 e a s ) ) j 笋 i 对 任 意的。 任 s i 都 成 立 . 根据投影算子性质， 知 s 二 p , 4 ( _ a i 一 f a t .,j ) j 肖 ( 2 . 8 ) 这样就得出， 变分不等式( 2 . 7 ) 等价 于投影表达 式( 2 . 8 ) ， 那么模型问 题( 2 . 1 ) 的 解 等价于对 任意的 =1 , 2 , . . . , n , ( 2 . 8 ) 式都成 立. 也就可以 得出， 前面命题 2 . 3 .2 中 解表 达式( 2 .4 ) 其实就是 投影式( 2 . s ) 的 具体表 达. 那么 迭代充水 法就可以 表述如下: 第。 次迭代时， 用户i 根据迭代步 玄 -1 n : ” ， 一 p 4 l 一 o 一 (艺a j 9 0 a + 艺a j s 一 0 ) 1 ( 2 . 9 ) j - + 1 第二章 基于博弈论的d s l谱管理问题 来更新变量 s i ， 其中s v ,j 表示第 。 次迭代所得的s 的值. 下面我们将根 据迭代步( 2 . 9 ) 来考察i w f a算 法收 敛性， 先要定义一 些矩阵. 定 义nx n阶 方 阵b “ (翰 ) 芯 二 : ， 其中 b i i 二 二m a x 1 k ka = ok v i , j =1 , 2 , , n 注意: 坛=1 , v i = 1 , 2 , - - - , n ， 也就是说 矩阵b是一 个 对角线元 素皆 为i 的非负 矩阵. 记b d i. , b i- , b ， 分 别 为b的 对 角、 严 格 下 三 角 、 严 格 上 三 角 部 分 . 可 见b di, 即nx n阶 单 位阵 ， b t，和b uy 皆 为 非 负 阵 . 这 样 可 知(b d i. 一 b i- ) - 必 存 在 且 也 为 非 负 阵 ， 则 矩 阵t = ( b d iu 一 b lo w ) - b u y 也 为 非 负 矩 阵 ， 记 其 谱 半 径 为a t ) . 记b 的 比 较 矩阵( c o m p a ri s o n m a tr ix ) ( 2 0 ) b d i, 一 b i.一 殊 a- b0-(凡)芯 = 1 定 理2 .4 .2 假设p ( t ) 1 , 列i w f a 产生 的 迭 代 序 列 (v ) 全( 户 勺 丝 : 必 收 效， 收 效点是该d s l 博弃的 唯一的n a s h 均衡 点 . 证明 . 由 迭代形 式( 2 .9 ) ， 对任意 正整数i , v 有 s v + “ 一 p g , - o t 一 (艺 a j s v + ,; +r a j e + - 10 )l j -, 诬 _1 j = i + 1 ， 一 p , , - a 一 (ea ij s v o +ea y s 0 - 1 0 )1 j = i j = i + 1 利用投影算子的非扩张性质， 即 i ip n ( x ) 一 p o ( y ) 11 :5 ll x 一 y 11 有 i l s v + l ,i 一 ， v ,i 1 1 ii l- a 一 ( a ij s v + l,j + 艺 n + 1 a ij s v + l- l j j = i+ 1 ) 1 一 - a 一 (艺a j s v j +艺a j s 一 ， ) 1 11 -i + ln a ij (s v + lj 一 s v i ) + 艺a ij ( s v + 一 j 一 : 一 , ) ii j = i +t ii a ij ( s j 一 。 0 ) iiii a ij (s v + 一 ， j 一 。 v - lj ) ii ，一十 ，n 十 。112尸d拭 艺b ij l l s 0 + 1 j 一 s v j ll +e b , il s v + l- l j 一 s v - l j 第二章 基于博弈论的d s l谱管理问题 其中卜“ 表示ir k空间 上欧几里得 范数 . 上面第一个不等式就是利用了投影算子的非扩张性质， 最后一个不等式是由 于a ii 0- d ia g ( a k )k 1 和b ;j 0- 将上面式子移项， 即得到 m a x 1 k k心 艺b ij il3 v + lj 一 8 v j ll 艺b ,j its v + l- lj 一 s v - 1 j ii . 对所有的 =1 , 2 , - , n ， 都有 相应的 上面 式子成立. 令叮会 iib v 十 lj 一 s v ,j ii , 向 量9 0 会 (衅 )翼 1 ， 则 有 ( b d ia 一 b ,-) e v bp e v - 由 于( b d i 。 一 b i - ) 一 存在且非负， 故有 0 e 0 ( b d a 一 b i m ) - 1 b u v r - 1 二r e v - 1 由风 r ) 0 ， 所有i - 1 , - - - , n都有 h s , 一 3 . ,i 1 1 一 ” p -4 i 卜 o f 一 ( l a ij s v + l j 十 - p .4 , ( - o 一 ea 8 0 ) 11 i 卢 11 艺a j (s v + l o 一 : 0 ) + j = 1 艺a ij ( s v j 一 ， . j a l j t1n 艺 j =11 1 a ij (s v t l ,j 一 3 j ) l卜 n il a ij ( s v j 一 s 0 ) 11 艺舟 又b ij l l s + j 一 s . i ll +艺 b ij lls v j 一 s .,i 11. j =1 亦即 对所有i =1 , 2 , , n都成立 eb ij lls v + l j 一 s 0 11 艺 b ij lls v a 一 s 1 . 令,io 7v + 1 a lls v + l j 一 s . 0 11， 向 量g + l(畔1 )n 1 ， 则 有 ( b di , 一 b lm o ) 19. 1 b , fl 亦即 0 v 叶1 兰t 1 9 0 由风 r ) 1 ， 可以 得出 li m俨=0 幻 叫 +自 j 亦即 li m u ，+ 亡 笼，118 10 ) 一 8 ii 一 0 ， 也 就 是 。 呱 s (o ， 一 8 . 这 样 根 据 极 限 的 唯 一 性 ， 必 有 s 三8 . ， 即得到了n a s h均衡点的唯一性. 证毕. 注:上面定理证明的前一部分， 提供了该博弈模型解存在性的一个新证明. 另外， 从上面证 明过 程可以看出 ， 若改变各 用户 之间的 顺序， 也 就是 改变算 法执行顺序时， 会对应不同的收敛性条件. 特别的， 若取与前面完全相反的次序， 即从 第n个用户开始 执行 直至第1 个用 户， 这时相 应的 迭代步变为: i -i n ， ， = p 9 1 1 一 a 一 ( 又a j 3 v - lo +艺a 幼 5 ” j ) ( 2 . 1 0 ) 第二章 基于博弈论的 d s l谱管理问题 类 似 定 理2 .4 .2 的 证明 容 易 得出 ， 当 满 足风( 场 a 一 尽 ,p ) - 1 b ,o ,o ) 1 时 ， 对 应 于 ( 2 . 1 0 ) 这 个迭代步的算法也 必收敛到 该d s l 博 弈唯一的n a s h 均衡点. 同 样， 如 果对应于任意的迭代顺序. 算法都收敛， 那么必收敛于同一点， 换句话说， 就是 可以认为收敛结果与用户顺序初始点选取都无关. 2 . 5 并行的i wf a 从 博弈论的 观点看， 迭代步( 2 . 9 ) 从i = 1 , - - - , n循 环一次的 过程， 就相当 于 一局动态博弈的进行. 动态博弈， 就是指各博弈方的行动有先后顺序， 而且后行动 者在自己行动之前能观测到先行动者的行动， 并以之作为参考从而做出对自己最 优的 行 动. 相对应的， 博 弈论中还 存在另 外一 类博弈， 是 要求博 弈方同时 行动( 或 者博弈 方行 动虽有 先后， 但没有 在自 己 行动 之前观 测到 其他 博弈方的 行动 ) ， 这 种 博弈称 为静态 博弈. 那么， 从 这个角 度来看， 就是 在每一 轮 迭代过 程中， 各用 户都 不能知道其他用户当前轮的结果， 而只知道上一轮的结果， 这样我们可以提出如 下迭代步: s 0 = p g t - o 一 艺a y s 0 - 1 j i 肖 =1 ， 一 ， n 为了 加 速收敛， 可以 考虑 加上记 忆项: v - 1 , ， 亦即自 身 上轮迭 代结果， 那么 就 得到这样一个j a c o b i 迭代步: 8 v , 一 。 8 v - 1 f + ( 1 一 。 )p ,4, p a 一 艺a s 0 - 10 i i 肖 ( 2 . 1 1 ) 其中 ， 。 e 沁 ， 1 ) 为 给 定 常 数， 8 v , 表 示 第。 次8 i 迭 代 结 果 . 可 见。 = 0 时 ， 就 是 上 面不考虑记忆项时的迭代步. 从 另一 方面来讲， 前面采用( 2 . 9 ) 迭代步的 经典i wf a ， 是一 个完全串 行的 算 法， 因 为 后面的 用户都得利 用其前面 用户的 最新计 算结果; 而采用( 2 . 1 1 ) 的算法 却 可以 是一个并行的 算法， 因为 各用户都 只需采用 上一 轮的 计算结果 . 这样， 当 用户数目n的值很 大时， 采用( 2 . 1 1 ) 并 行迭代步的 充 水法可能 会比 经典的i wf a 更高效. 那么， 这个 并行算法 是否收 敛呢? 利用与 上一 节类似的 证法 可以 得到 类似的 收敛性结果. 定理2 . 5 . 1 俊设风 i - ( 1 - 劝b ) 1 , 则 按并 行迭 代充 水葬法( 2 . 1 1 ) 得到 的序 第二章 基于博 弈论的d s l 谱管 理问 题1 5 列i s m会(s v ， 丝 1 f 收 效 到 该d s l 博 弃 的 唯 一 的 n a s h 均 衡 点 . 特 别 的 ， 当 、 取 蚤 时 ， 收 效 性条 件 即 为p (b ) 当 取0 时 ， 收 效 性条 件 为p ( b lm v + 殊 ) 1 . 证明. 由 迭 代形式( 2 . 1 1 ) ， 对任意正 整数1 , 。 有 s + 1, 二 。 0 + 1- 1 ,i + ( 一 。 ) p gg i l- o i 一 艺a y s 一 ， + l 1 j 护 i s v i = lo s ” 一 ,i + (1 一 。 ) p -4 , 1- - i 一 ea ij s 一 ，i 了 笋 i 与定理2 . 4 . 2 的证明类似有: s v +1 一a . ， 恨 区沼d俏 w s v + l - l ,i 一 s v - , ,i l l + ( 1 一 。 ) 1a ij (s 0 + i- l 0 一 。 v - l j ) ii 三 。 卜 v + l- l ,i 一 s v - l,i l卜 ( 1 一 。 ) b ij lls v + l- l ,j 一 s v - l a ll 同 样 令叮a lls v + l,j 一 8 v 4 11 r 向 量俨会(叮 ) 美 ， ， 上 式 即 为 e w e - 1 + ( 1 一 。 ) (b lo w + 殊 )r-1 = 沙 i + ( 1 一 。 ) (b i.+ b . v ) b v - 1 = (i 一 ( 1 一 。 ) b b - 1 上 面 最 后 一 个 等 式 是 由 于b d m 二 i 和b = b d ia 一 b i.一 刀 即 . 这 样 与 定 理2 .4 .2 类 似， 由p ( i 一 ( 1 一 叼 功 1 ， 即 可 推出 s (v ) 序 列 收 敛 . 特别 的 ， 。=委 时， i 一 ( 1 一 w ) r 3 =盖 b , 亦即、=盖 时 ， 收 敛 性 条 件是 p ( b ) _ 0 , =1 , 2 ， 一， 。 下面给出上述多目标问题的几种解的定义. ( 3 . 1 ) 1 . 绝对最优解 定义3 . 1 . 1 设扩 x， 知果 对于 任意的xe x, 均 有f ( x ) _ f ( x ) 成立， 即 对于一 切9 = 1 , 2 , . . . , p ， 均 有f i ( x * ) ? f . ( x ) , i h l 称x . 是多目 标极大化问 题的绝 对最 优解. 所有绝对最优解构成的集合称为绝对最优解集. 绝对最优解对应的像点称为 绝对最优点. 绝对最优 解的概 念显然 是单目 标规划最 优解概 念的直 接推广. 显然， 这是一 种最理想的解， 所有目标函数都同时在同一点处达到最大值， 可是这种解一般很 第三章 基于多目 标规划的d s l谱管理问题 难存在， 因此， 必须探讨其它意义下的最优解. 2 . 有效解 定义3 . 1 . 2设x x , 知果不存 在: e x使向圣不 等式f ( x ) - f ( x ) 成立 ， 则称x 是多目 标极大化问题的有效解. 所有有效解构成的集合称为有效解集 这 里 向 量不 等 式f ( 劝 f (x ) 的 含 义 是: 对 于 一 切i =1 , 2 , . . . , p ， 均 有寿 (劝 f i ( x * ) ， 并 且 至 少 存 在 一 个 e 1 ， 2 ， . . . , p ， 使 得a ( x ) f i ( x ) 成 立 . 也 就 是 说 ， 对于 有效解x 而言， 在向 量不等式 ” 匕 ” 意义 下， 可行 域x内不 存在比它 更 好的 解. 有效解( e ff e c t iv e s o l u ti o n ) 又 称为非劣 解( n o d o m i n a t e d s o l u ti o n ) 或p a r e 。 有 效解. 其对应的 像点称为有效点或非劣点. 显然， 若绝对最优解存在， 这个绝对最优解必定是有效解. 并且当绝对最优 解集非空时， 有效解集等于绝对最优解集. 3 . 弱有效解 定义3 . 1 3设x e x ， 如果 不存 在: e x使向童不 千式f ( 习f ( x ) 成立 ， 则称x 是多目 标极大 化问 题的 弱有效 解试 弱非 劣解 ， w e a k p a r e t o s o l u t i o n ) . 也就是说， 若x 是弱有效解， 则在可行域x内找不到比x* 在” ” 意义下更好的 解， 即找不到 一 个二 e x使 得a(x) f i ( x . ) 对所有 =1 , 2 ， 一， p 都成立 . 显然， 有效解必是弱有效解 另外， 不难看出， 各个分量目标函数在可行域x上的最优解必是弱有效解. 事 实 上 ， 若 设2 是f i (x ) 在x上 的 最 优 解， 即f i( x ) f i (x ) , b x e x ， 亦 即 不存 在x x使得f i ( x ) f i ( x ) ， 也就是 说不存 在二 e x使得f ( x ) f ( z ) 成 立， 由弱有效解定义知， x 必为弱有效解. 多目 标极大化问 题( 3 . 1 ) 有效 解存在的一 个充 分条件是: 所有目 标函数 分量 f ; (x ) 在 约 束 集x上 连 续 ， 且 存 在x e x ， 使 水 平 集h z = x e x f (a ) _ f ( x ) ) 为有界闭集. 我们来看下面两个图， 考察它们的有效点集. 左图: o a b c o所围 区域为 像集. 容易 看出b点 为绝 对最优点， 有效点 仅有 一个即b点， 弱有效点集为b c线段. 第三章 基于多目标规划的 d s l谱管理问题 右图: o a b c d e o 所围 区 域为 像集( c为 与b 点 横坐标相 等的边界点 ) . 显然， 绝对最 优点 并不存 在， 有效 点集为b 点 加上边界上c d 一段( 不包 括c点 ) ， 弱有 效点集为b点 加上 边界上c d e 一段( 包括c点 ) ， f 2 f 2 立f i旦 一 ，f i 3 . 1 .2 多目标规划解法 研究多目 标最优化问 题的 一个基本途径， 是把它转化为与 之相关的 单目 标 ( 标量) 最优 化问 题. 这 种把向量问 题标量化的 做法， 便是所谓多目 标最 优化的 标 量 化处理. 另外， 我们知 道， 一 个给定的多目 标问 题一般 具有许多 个( 弱 ) 有效 解， 因 此， 人们通常 不满 足求出它 的随意 一个( 弱) 有 效解， 而是 要设 法求得这 样一个 解， 它既是问 题的( 弱 ) 有效 解， 同时 又是在 某种意义 下令人 满意的 解. 这是多目 标 最优化与单目 标 最优化求 解的一 个重要不同 点. 下面介 绍几种 基本的( 弱 ) 有效 解生成 方法， 问 题描 述还是 采用前面的( 3 . 1 ) . 必 . 1 . 2 . 1 主目 标法 在多