（信号与信息处理专业论文）基于凸优化理论的fir滤波器设计及其在lascdma系统中的应用.pdf

北京邮电大学硕士学位论文摘要 基于凸优化理论的f i r 滤波器设计 及其在l a s c d m a 系统中的应用 摘要 在过去的二十年中，关于凸优化理论和内点方法的研究取得了长 足的进展，开发出了强大的优化模型以及高效的算法和软件工具。最 近，这些进展开始对各个应用科学和工程领域产生影响。在过去的三 十年中，数字信号处理和数字通信领域中采用的主要优化算法是最速 下降方法和最小二乘方法。虽然这些算法得到了很好的应用，但他们 存在一些固有的缺陷，例如，收敛速度慢、对初始条件和步长选择比 较敏感等。将非凸优化问题转化为凸优化问题或者松弛凸优化问题是 避免上述缺陷的有效方法，凸优化问题可以保证得到全局最优解，并 且避免了步长选择、算法初始化和局部最优解等令人头疼的问题。 l a s c d m a 技术通过构造具有零相关窗的扩频码，克服了传统 c d m a 技术的缺陷，工程实现简单，系统容量大，具有广阔的应用 前景。 本文中，将带有频谱特征约束的有限冲击响应滤波器设计问题转 化为以滤波器系数的自相关系数为优化变量的凸优化问题，并且通过 扩展正实引理将滤波器频谱特征约束的无限描述形式转化为有限描 述形式，最后采用内点算法求解得到的凸优化问题，从而设计出带有 频谱特征约束的有限冲击响应滤波器。 关键词：凸优化内点算法滤波器有限冲击响应 v 北京邮电大学硕士学位论文 n re 【唧rd e 阻g n b a s e do nc o n v e xo p i 】【m i z a t i o nt h e o r y a n d 1 sa p p l i c a l l o ni nl a s 。c d 【as y s t e m a b s t r a c r o v e rm el a s tt 、7 l ，od e c a d e s ，t h e r eh a v eb e e ns 诤曲c 弛ta d v a n c c si nt h e r e s e 眦ho fc o n i co p t i m i z a t i o n 柚di n t e r i o rp o 硫m e t h o d s p 嘴i f i l l o 皿m i z a 曲nm o d e l s ，e m c i e n ta l g o r h h 螂a n ds o f t w a r et o o lh a v eb e p r i 讪c c d r e c e n y ；t h e s ea d v a c e sh a v eb e g u nt oi m p a c tv a r i o u sa p p l i e d s d e n c e 翘d 舀n e e r i i l gf i c l d s i t lt h ep 勰tt h i n yy e a r s ，( h ew o r k - h o r s e a 1 9 0 d 血m si nt h e 矗e l do fd i 醇a ls i g n a lp f o c c s s i n ga n dc o m m u n 捌o n h a v eb e e nt h eg m d i 曲td e s c e n ta l 窘o i i t h ma n dm el e 舔ts q u a r ea l g o t i t h m w h i l et l l e s ea l g o r i t l l m sh a v es e n ，e dt h e i rp u r p o s ew e u ，t h e ys u f e r 丘d m s l o wc o n v e 玛e n c ea i l ds e n s i t i v 蚵t ot h ea l g o r i t l l mi n i t i a l i z a t i o na n ds t 印 s i 孺s e k c t i o n ，e s p e d a l l yw h e na p p l i e dt oi l l - c o n d i t i o n e do rn o n c o n v e x p r o b l e mf o 咖l i l a t i o n s 0 n ep o w e 血1w a yt oa v o i dt h e s ep f o b l e m si st o d e i i v ea ne x a c tc o n v e xr e f b n n i l l a t i o no r ac o n v e xr e l a x a t i o no f 也e o r i g i n a l n m l c o n v e xf o m u l a t i o n o n c eac o n v e xr c f o 删a 吐o no r r e l a 】【a t i i s0 b t a i l l e d ，w ec 姐b eg u 甜柚t e e do f 丘n d i n gt h e g l o b a l l y o p 缸a ld e s i 蔓尹e 茁c i c n d yw i 也o u tt h e 咖a lh c a d a c h 髓o fs t e ps i z e s e k c t i o n ，a l g o r i t h mi n i t i a l i z a t i o na n dl o c a li i l i n i m a ，n l r o u 鲈c o n s t i u c 咖gs p r e a d i 】略c o d e sw 洫z e r oc o 玳d a t i o nw i n d o w s l a s 一( 、d m at e c l l l l o l o g yg c t so v e rt h ed r a w b a c ko f 仃a d i t i o n a lc d m a t e c h n o l o g y c o m p a r e dw i t h t r a d i t i o n a lc d m as y s t e m ，l a s c d a s y s t e mh a s ab 远g e r s y s t e mc 叩a c i t y w i t ha s i m p l e r 蛐g i e r i n g i m p l e m e n t a t i o n i nt l l i sp a p e r ，w er e f 0 册u l a t et h ep r o b l e mo fd e s i g n i n gaf mf i l t e r w i ms p e c t n j mm a s kc o n s a i n t st oac o n i c o p t i m i z a t i o np m b l e m ，t h m u g l l u s i n g t h ea u t o c o r r e l a t i o no ft h ef i l t e f sc o e f f i d e n t sa s o p t i m i z a t i o n v a d a b l e s 触s o ，t h r o u 曲e x p a n d i n gp o s i t i v er e a ll e m m a ，w er e f o r i n u l a t e t h ei n f i n i t ef 0 珊o ft h es p e c t m mm a s kc o n s t r a i l l t st oaf i n i t ef o 蛐f i n a l i y 、e a d o p tm ei n t e r i o rp o i n tm e t h o d st os o l v et h er e f o 姗u l a t e dc o n i c 北京邮电大学硕士学位论文a b s l l b 岍 o p t i m i z a t i o np m b l e m ，a n dg e tt h ec o e f f i c i e n t so f l ed e s n df i rf n t e r k e y w o r d s ：c o n v e x 叩t i m i z a t i o n ，i n t e r i o rp o i n tm e t h o d s ，f i l t e r ， 北京邮电太学硕士学位论文声明 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：至盟日期：塑：塑： 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名：圣盟 日期： 导师签名： m q 5 5 。 日期：曼塑：曼塑 北京邮电大学硕士学位论文 绪论 1 1c d m a 系统概述 1 绪论 随着人类进入2 1 世纪，以通信计算机为代表的信息技术( h f 0 皿a t i 衄 1 鼬n o l o g y ，即r r ) 的迅猛发展给人类社会带来巨大变革，推动了社会生产力的 飞速发展，对人们的工作生活的方方面面都产生了重大的影响。在通信技术方面， 个人通信业务( p c s ) 需求尤其是跟无线移动通信相关的需求在近二十年来增长 显著。现有的以g s m 和i s l 9 5 为代表的第二代移动通信系统已很难满足用户的 需求，因此提出了第三代( 3 g ) ，后3 g ( b 3 g ) 甚至4 g 移动通信系统。 移动通信系统的多址接入方式主要有频分多址( f d m a ) 、时分多址( j i d m a ) 和码分多址( c d m a ) 。与使用不同频段接入的f d m a 系统、使用不同时隙接入 的1 1 ) m a 系统不同，在c d m a 系统中，用户被分配以特定的扩频序列，不同 用户共享相同的频段和时隙，是第三代移动通信的主流技术。第三代移动通信的 三个国际标准一c d m a 2 0 0 0 、w c d m a 和t d s c d m a 都是以c d m a 作为多址 接入方式。我们国家由李道本教授提出的l a s c d m a 【1 】也是以c d m a 作为无 线接入方式的。 如果不同用户所使用的扩频序列之间的互相关为零，则c d m a 系统为理想 的正交接入系统。然而理论分析表明，在相同的通信带宽条件下，使用非理想正 交扩频码的a ) m a 系统的信道容量比1 d m a 以及f d m a 的要高【2 1 。在移动通 信中，c d m a 系统可以采用话音激活技术、扇区化天线技术以及为1 的频率重 用因子，这样它的系统容量可高达1 d m a 系统的4 倍，以及f i l m a 的2 0 倍【2 k 此外由于c d m a 还比较容易采用一些新的关键技术并且在实际应用中具有更大 的灵活性与更好的性能，故而成为第三代移动通信的主流技术。 1 1 1 传统c d m a 技术是干扰受限的c d m a 技术 扩频码码限的研究指出不可能构造出理想的满足i s l = 0 、m 越；0 并且 a a = 0 的c d m a 系统扩频码，要使a ) m a 系统能够使用，只能退而求其次， 不再要求i s i o 、m a i o 并且a c i o ，只要求它们小到系统能够正常工作。 当i s i ，0 、m a j _ o 并且a a _ o 时，如果这些干扰比热噪声。小很多，那么就 不会对系统性能产生影响。但实际上通常容易找到的扩频码引入的这些干扰要比 热噪声。大得多，所以系统性能受到干扰限制，故称为干扰受限的c d m a 系统。 传统的c d m a 系统是在扩频码问存在干扰情况下设计的。因而在反向链路， 北京邮电大学硕士学位论文 多个移动台的信号被一个基站接收，其间互相产生干扰。如果对于某一个扩频码， 它的信号电平低于其它某些扩频码信号的电平，那么尽管努力没法使m a i 小于 某一数值以不影响正常接收，但如果这些作为干扰的扩频码信号由于距离基站比 较近而使接收到的信号很强，就造成了不可克服的干扰，通常称为“远近”干 扰，传统c d m a 中的许多技术和问题都是由于“远近”干扰造成的。 “远近”干扰在传统c d 眦a 系统无法消除只能控制，办法是使到达接收点 的信号强度相同，这样就恢复到最初设计的条件，码间的相互干扰与信号能量相 比应低到可以容忍的程度。于是各种功率控制的方法就应运而生。 然而，要能够精确的控制使各移动台来的信号电平保持相等是一件很困难的 事。这是因为无线传播条件是非常恶劣的，在移动台固定或移动速度很慢时，接 收的信号是缓慢起伏的，功率控制比较容易。而当移动速度很快时不仅产生多卜 勒频移更产生快衰落，这时要求快速的控制。功率控制的前提是对某个地址信号 电平的快速的测量和估值，但是测不准原理告诉我们，不可能在无限短的时间得 到无限高的测量精度。测量时间越长精度才越高，而且测量结果还要立即发送到 移动台，以便迅速调正发送功率。实际上功率控制不可能达到理想状态，功率控 制不理想的结果造成了系统性能的下降。如果功率控制失效将造成系统性能急剧 下降甚至瘫痪。其实因为各移动台到达基站的传播路径不同，测量不可能在没有 码间干扰条件下进行，在移动台高速移动时，快速功控有时还会带来负作用。在 衰落情况下精确的控制是不可能的，尤其是在多移动台的情况下。 对于前向功率控制。既然要求接收到的各扩频码信号电平相同，那么在基站 发出的各扩频码信号电平应当完全相同。不过因为移动台距离基站的距离不同， 要保证最远距离的移动台能正常工作，发送的电平参考点就是以最远移动台为基 准。这样对于近的移动台，显然是不需要的。但不能够按各移动台的距离( 传输 损耗) 分别配置发送功率，而只能以最远的移动台为准，如果这个“最远”的移 动台也距基站比较近，那么发送的功率就可以小一些。不能根据各移动台传播条 件( 包括距离和障碍物) 来实时的按需分配功率，这是因为如果要按需分配，就 造成了在移动台接收机各扩频码的功率不同，产生“近远”干扰。 通信距离和系统性质有关。在噪声受限系统中，传输距离和系统容量无关， 在给定传输速度下，一定的发信功率扣除传输损耗和衰落保护裕量后达到保证满 足传输质量的最小容许接收信号电平，从而可以计算出传输距离。关键是只要增 大发信功率或降低接收噪声就可以增加传输距离。 传统的- c d m a 系统是一个干扰受限的系统，传输距离或小区半径由一个用 户受到的其它用户的干扰电平决定。显然传输距离除与传输损耗( 包括路径损耗、 衰落保护裕量、馈线损耗) 以及发信功率，保证接收质量的最小信扰比有关之外， 2 北京邮电大学硕士学位论文 还与用户数有关。 如果小区仅有一个移动台工作，没有其它用户的干扰，相邻小区也没有用户 工作，这时加大发射功率就可以传送到足够远的距离。当用户数增加，干扰相应 增大，通信距离缩小，当达到小区最大用户时，通信距离或小区半径缩减到最小。 这时不能靠增加发送功率来提高小区半径，因为一个移动用户功率增加，势必导 致所有移动台都增加功率，结果水涨船高，干扰也加大，不仅不能增加通信距离， 还会降低通信质量。 1 1 2 乙峪a ) m a 技术是噪声受限的c d m a 技术 由下一章的分析可知，通过构造具有零相关窗的扩频码，当多经成分落在零 相关窗内的时候，u 峪c d m a 系统不存在塔i 和m a i ，l a s a ) m a 系统与传统 的a ) h l a 系统不同，它是一个噪声受限系统。因此，l a s c d m a 系统不需要采 用功率控制、软切换等传统c d m a 系统必须采用的复杂技术，而可以简单的工 程实现获得比传统c d m a 系统大得多的系统容量，具有广阔的应用前景。 1 2 凸优化应用概述 凸优化( c o n v c xp r o 伊锄) 问题是一类特殊的数学优化问题，它是非线性优 化( n o n l i l i e a ro p 蛞m i z a t i ) 问题中的一个子类。我们熟悉的最小二乘( 1 e 路ts q u 舡e ， l s ) 问题和线性规划( 1 i 耻缸p r 0 龋m ， ) 问题都属于凸优化问题，凸优化问 题统一并且推广了最小二乘问题、线性规划问题和凸二次规划( q u 砒r a t i c p m j 驴m ，q p ) 问题。近年来，学者们定义了其它一些凸优化问题的标准形式， 它们包括：半定规划( s e m i d 锄i t ep i o g r a m ，s d p ) 问题【3 1 、二阶锥规划 ( s c c o n d 训既c o p r o 舯m ，s 0 c p ) 问题【4 】和几何规划( g e 咖咖cp r o g r a m ， g p ) 问题。最小二乘问题和线性规划问题都已经具备了相当完善的理论基础， 并在实际工程问题中得到了广泛的应用。对于其它的凸优化问题，同样的事情正 在发生着。 虽然关于凸优化理论的研究已经持续了一个世纪，该领域的最新进展还是引 起了大家的关注。首先，人们认识到用于解决线性规划问题的内点方法 ( i n t 盯p o m m 劬o d ) 同样可以用于解决凸优化问题【5 ，6 】。内点方法使得解决某 些凸优化问题如同解决线性规划问题一样容易，例如，二阶锥规划问题和半定规 划问题。其次，人们认识到凸优化问题在工程实践中存在的比例比以前认识到的 更大，它可以广泛的应用于自动控制系统、信号处理【7 9 】、电子电路、数据分析 与建模等很多学科领域。所以，大家相信凸优化更多的应用领域还有待发现。 在过去的二十年中，关于凸优化理论和内点方法的研究取得了长足的进展， 北京邮电大学硕士学位论文绪论 开发出了强大的优化模型以及高效的算法和软件工具【1 0 】。最近，这些进展开始 对各个应用科学和工程领域产生影响。将现代优化方法应用于信号处理和数字通 信领域是有其理由的。在过去的三十年中，数字信号处理和数字通信领域中采用 的主要优化算法是最速下降方法和最小二乘方法。虽然这些算法得到了很好的应 用，例如，信道均衡【8 】、成形滤波器设计【7 】和数字波束赋形【9 】等，但他们存在 一些固有的缺陷，例如，收敛速度慢、对初始条件和步长选择比较敏感，特别是 当优化问题是病态的或者是非凸的时候，这些问题更加严重。对非凸优化问题直 接应用最小二乘算法或者最速下降算法的主要缺陷是收敛速度慢和局部最小值。 将非凸优化闯题转化为凸优化问题或者松弛凸优化问题是避免上述缺陷的有效 方法，凸优化问题可以保证得到全局最优解，并且避免了步长选择、算法初始化 和局部最优解等令人头疼的问题。 在数字信号处理和数字通信领域中，另一个富有挑战性的问题是针对模型误 差和实现误差得到具有健壮性的解，这些误差通常是由测量噪声、模型失配和数 字硬件的有限实现精度导致的。由于上述误差在数字信号处理和数字通信领域中 普遍存在，研究具有健壮性的算法就有其重要的意义。如果不能对所需要的健壮 性进行正确的建模，得到的最优设计将变得毫无意义。由于缺少有效的数学模型 和优化方法，以前大多数关于信号处理和数字通信的算法研究不直接涉及算法的 健壮性或者不能给出令人满意的解决方案。随着近年来数学规划领域不断取得新 的进展，具有健壮性的优化技术【1 1 】也得到了长足的发展，从而使得上述问题得 到了很好的解决。 1 3 论文结构 本文将讨论凸优化理论的新进展，及其在数字信号处理领域中尤其是c d m a 系统f 取滤波器设计中的应用。第二章给出l a s c d m a 系统的性能分析。第三 章给出凸分析的基本原理【1 2 ，1 3 】，第四章给出数学优化的基本原理和算法【1 2 ， 1 3 】，第五章给出凸优化理论在u 峪c d m a 系统f m 滤波器设计中的应用。第六 章给出结论。 4 北京邮电大学硕士学位论文l a s a m 系统性能分析 2 “峪一c d m a 系统性能分析 我们考察包含m 个正交扩频序列的扩频序列集爿= a ，a # ，a 铲 ， 其中a # ) 一扣搿，口留，口f ；) ，啦。) ，前是复数，= 1 2 ，m ，f ；o ，1 一1 。 2 1 基本概念 2 1 1 非周期相关函数 设雌和a 2 为上述正交扩频序列集爿的两个正交扩频序列，非周期相关函数 c i ，) 定义为 g ，( 肌) = 墨1 口f ：? ( 杜，) ，一 善口剐n 趴，m c 。 ( 2 1 ) o ， i m i 具中 表不复共轭。 2 1 2 周期相关函数 设a 妒和以为上述正交扩频序列集4 的两个正交扩频序列，周期相关函数 r 。，( 所) 定义为 r ，( 胁) 一薹n 搿( 口鼢，。) ) ，历z ( 2 2 ) 其中m o d 表示模运算，z 表示整数集合。 当七一，时q ，j ( m ) 和墨，j ( 埘) 分别称为非周期互相关函数和周期互相关函数： 当j ；j 时g ( 小) 、r ( m ) 分别称为非周期自相关函数和周期自相关函数。并 且满足如下关系式 r ，j ( p + m ) = q ，( 聊) + c t ，( 坍一) ，p z ，o s m c ( 2 3 ) 我们称m = o 时的自相关函数值为自相关函数的主峰；m 一0 时的自相关函数 值和所有的互相关函数值称为相关函数的副峰。 本文中的相关函数是指非周期相关函数。 5 北京邮电大学硕士学位论文 l a s a ) m a 系统性能分析 2 1 3 零相关窗 单边非周期自相关函数的零相关窗宽度兀。，的定义为 l 。= m 强 形i c 。( m ) = o ，1 s 七s m ，o t i 历i 量) ( 2 4 ) 单边非周期互相关函数的零相关窗宽度，、的定义为 乙。= m a x 杪i q ，( 赫) ；o ，1 s 七，j s m ，七一lo 量j m i 蔓形 正交扩频序列集爿的单边非周期零相关窗宽度l c c ，定义为 五一埘n i 】咀i z c l ，7 岛 正交扩频序列集a 的非周期零相关窗宽度z 森定义为 一2 l + l 2 2 m a 系统的干扰分析 ( 2 5 ) ( 2 7 ) 考察单小区d s c d m a 系统前向反向链路，假设有足个激活用户，每个用 户分配一个持续时间为r 的特征波形吼o ) ，其中r 为符号间隔，r = 正。特征 波形口。( f ) 为 口t o ) ；口搿p ( f n t ) ，七= 1 ，2 ，置 ( 2 8 ) 其中是码片间隔，是扩频码长度，p o ) 是宽度为t 的成形脉冲，如果没有 特殊说明，p ( f ) 为矩形方波。不失一般性，假设所有的眉个特征波形吼( f ) 具有 单位能量 j ：口：( f ) 出= 1 ( 2 9 ) 第_ 】 个用户的信道k o ) 的等效低通离散表示为 ( f ) 。薹，6 ( ，) c x p ( ，幻) ( 2 1 0 ) 其中a “是表示第七个用户第j 径的幅度增益系数，九j 表示相位偏移，气。，是第七 个用户第f 径的时延，不妨假设0 蔓，。t j t t t 。c r 。 第七个用户的数据符号为 川) 2 荟搿r c c t ( f 坩) ( 2 m ) s ；) 表示第t 个用户在时间段【f f ，( f + 1 ) t 】传送的第i 个数据符号，考虑到功率分 配和调整，进一步假设第七个用户的所有传送信号都具有发射功率调整因子最， 北京邮电大学硕士学位论文 l 峪a ) m a 系统性能分析 对应于幅度调整因子为夏。 接收到的等效基带信号可以表示为 r ( f ) 。善荟扛吒，强p ( 地，) ( f 一吒，) 吼( f t ，) + 玎( f ) n ( r ) 是双边功率谱密度为0 2 的加性白高斯噪声( a 、1 3 n ) 。 参考【1 4 】定义如下非周期相关函数 n 。小) = f l q ( f ) n j ( r ) 出，o s f c r a ，小) ；f 。q ( f ) 口；( f + f ) 出，o s f r 反，卜) = q ( f ) 4 j ( f + f ) 出，一丁c r t o “，p ) 一q ( r ) 4 ；( f + r ) 疵，一r c f t o ( 2 1 2 ) ( 2 1 3 ) ( 2 1 4 ) ( 2 1 5 ) ( 2 1 6 ) 假设小互s f 【胁+ 1 ) ，m 为整数，根据上述定义，可以得到如下关系式 a ，扛) = 吾( ( ( m + 1 ) t r ) q 。( 肺一) + 扛一小) c ；，( m + 1 一) ) ，o s f t r ( 2 1 7 ) 以。( r ) = 亭( ( ( m + 1 ) 互一f ) c ，( m ) + 卜一m t ) g ，( 埘+ 1 ) ) ，o s f c r ( 2 1 8 ) 群，- ) = 亭( ( ( m + 1 ) i f ) q ，( 胁+ ) + 卜一m i ) g ，( 研+ 1 + ) ) ，o s f t r ( 2 1 9 ) 。 小) = 事( ( ( 册+ 1 ) t f ) ( m ) + ( f m t ) c i ，( 肼+ 1 ) ) ，o s 百t r ( 2 2 0 ) 群( f ) 一虞i ( 吖1 ，一r r o( 2 2 1 ) “，( f ) = 以( 叶) ， 一丁 0 ，都有d 1 a d 2 ，则称 d 1 ，d 2 是s 的两个不同方向。当非空凸集s 的方向d 不能表示为它的两个不同方向 的凸锥组合时，该方向d 称为凸集s 的一个极方向( c x 仃锄e d i r c c t i o n ) 。 1 6 北京邮电大学硕士学位论文 凸分折基本原理 显然，有界多面体不存在方向，因而也不存在极方向。对十尢界多曲体才有 方向的概念。下面给出多面体的一个重要性质。 定理3 6 ( 多面体表示定理，m i n k o w s hn e o r c m ) 若多面体 p ； x 瓞4 ia 】【s b ，e g ，并且础( a ) 一n ，则 1 ) p 的极点时非空的有限集合，记为 r 。 2 ) 记p 的极方向集合为 d j 。( 当p 不存在极方向时，指标集，= g ) ，那 么 _ p = c 。删 fi 七k ) + d 。i ，j ) 十印叫轴乏科+ 蓍印 、 荟 2 1 ， 芑o ，七匿，弘，2o ， 3 ) 指标集，= 彩，当且仅当p 是有界集。 由多面体表示定理给出的结论可知，对于多面体，只需研究其极点和极方向。 3 4 凸函数 定义3 1 7 设s c 科为非空凸集，函数，：s r 。若v x ，y s ，v a ( o ，1 ) ， 总有 ，( a x + ( 1 一a ) y ) s a ，( x ) + ( 1 一 ) ，( y ) 则称函数，是凸集s 上的凸函数( c 0 v 坯f l m c t i o n ) 。若上面的不等式对于x y 严 格成立，则称，是s 上的严格凸函数( s 仃i c t l yc o n v c xf i 珊c t i 凹) 。 若一，是s 上的凸函数，则称，是s 上的凹函数( 咖c a v e f i l n c t i 衄) 。若一，是 s 上的严格凸函数，则称，是s 上的严格凹函数( s 舡i c t l y o c a v e f i m c t i 帆) 。 若s c 科为非空凸集，：s 一琏是凸函数，则函数，的水平集( 1 e v c ls c t ) 工( ，；a ) 一 x i x s ，( x ) s 口，a 酞 和上境图( 印i g r a p h ) e p i ( ，) 皇 ( x ，y ) f x s ，y 琏，y 壬，( x ) c 瓞”1 都是凸集。 凸函数的重要性在于下面的基本性质。 定理3 7 设s c 尉为非空凸集，：s r 是凸函数。则，在s 上的局部极小 点也是全局极小点，且极小点的集合为凸集。 1 7 北京邮电大学硕士学位论文 数学优化原理与算法 4 1 数学优化 4 数学优化原理与算法 数学优化要解决的问题是在等式和，或不等式约束下优化某个目标函数，求出 最优解，一般表示为 n i i n i m i z c ，o ( x ) ； s u 巧。c t t o 正( x ) so ，f 一1 m ，( 4 1 ) 一( x ) = o ，j = 1 ，p 其中x 对是优化变量( 叩咖l i z a t i o nv a i i a b l e ) ，0 ( x ) 为目标函数( o b j e c t i v e 硒l c d ) ，c 的和 j ( x ) 为约束函数( c 0 越t r a i n t f i m 甜) 。 约束条件可以写为集合约束形式，令 s = x l 正( x ) 蔓o ，f = 1 ，m ； j ( x ) = o ，= 1 ，p 称s 为优化问题的可行集( f e a s i b l es e t ) 或可行域( 砌如l er e 舀) 。 为可行点。这样( 4 1 ) 中的约束条件可以用集合约束形式表示为： m i n i i l i i z e ，( x ) ； s u b j e dt o x s 当时中所有的点均为可行点时，( 4 2 ) 即为： s 中的点称 ( 4 2 ) m i n i m i z e ，o 【) x 科 ( 4 3 ) ( 4 3 ) 称为无约束优化问题( 曲c o n s 仃a i i n e do p t i m i z a t i o np f o b l 锄) 。 下面给出最优解的概念。 定义4 1 设矗( x ) 为目标函数，s 为可行域，x s ，若对所有的x s ， 厶( x ) z ，0 ( x ) 均成立，则称x + 为( 4 1 ) 给出的极小化问题的全局最优解( 9 1 0 b a l l y o p t i l n a ls o l u t i o n ) 。 定义4 0 设，0 ( x ) 为目标函数，s 为可行域，x s ，若存在x 的e 邻域 m ( x ) 皇l x - x 8cs ，v ，o 使得对所有的x s n 虬( x + ) ，o ( x ) 芑，0 ( x + ) 均成立，则称x 为( 4 1 ) 给出的极小 化问题的局部最优解( 1 0 c a l l yo p t i m a l l u l i o n ) 。 对于极大化问题，可以类似的定义其全局最优解和局部最优解。 通常可以根据目标函数和约束函数的特征，将优化问题分类，按照适用范围 1 9 北京邮电大学硕士学位论文 数学优化原理与算法 由小到大依次是：线性规划、二次规划、二次约束二次规划、凸优化和非线性优 化a 若目标函数矗和约束函数五，；啊，j i l 。是线性函数，即v x ，y 科， v a ，卢琏，满足 五( 口x + 芦y ) = a 正( x ) + 芦正( y ) ，f = 1 ，m i l ( d x + 卢y ) 一a q ( x ) + 卢 j ( y ) ，t 1 ，p 则( 4 1 ) 给出的极小化问题是线性规划问题。否则，( 4 1 ) 给出的极小化问题是非线 性规划问题。 4 1 1 凸优化 凸优化问题具有以下形式 m i 血i 】血跹 ，o ( x ) ； s u b j e dt o正( x ) eo f = 1 ，m ， a ；x = 6 ，= 1 ，p 其中，0 ，丘是凸函数。与( 4 1 ) 给出的数学优化问题的形式相比较， 要求 目标函数必须是凸函数， 不等式约束函数必须是凸函数， ( 4 4 ) 凸优化问题 等式约束函数 j ( x ) = a j x 一6 j ，j = 1 ，p 必须是仿射函数。 凸优化问题的可行集是其定义域的交集，而其定义域是凸集，所以凸优化问 题的可行集是凸集。因此，凸优化问题就是在凸集上最小化一个凸目标函数。 凸优化问题的一个基本性质是，任意一个局部最优解同时也是全局最优解。 4 1 2 线性规划 当日标函数和约束函数都是仿射函数时，凸优化问题( 4 4 ) 称为线性规划 ( 1 i n e a f 舯咿锄) 问题。线性规划问题具有以下形式 m i n i m i z ec t x + d ： s u b j e c tt og x s h ( 4 5 ) a x = b 其中g r 一，a 瓞一。线性规划问题属于凸优化问题。 线性规划问题的可行集是一个多面体p 。因此，线性规划问题是在一个多面 体p 上最小化一个仿射函数c t x + d 。 4 1 3 二次规划 当目标函数是二次函数，并且约束函数是仿射函数时，凸优化问题( 4 4 ) 称为 北京邮电大学硕士学位论文数学优化原理与算法 二次规划( q u a d r a t i cp m g r a m ) 问题。二次规划问题具有以下形式 n 虹n i m i z e ( v 2 ) x t p x + q 7 x + r ； s u b j e c tt og x s h ，( 4 6 ) a x = b 其中p s ：，g r 一，a r ”。 二次规划问题的可行集是一个多面体p 。因此，二次规划问题是在一个多面 体p 上最小化一个二次函数2 ) x p x + q 。x + r 。 当目标函数和不等式约束函数都是二次函数，即 m i n ：h n i z e ( v 2 ) x t r x + q o t x + 吒； s u 巧e c t t o ( v 2 ) 】【t b x + 吼7 x + i ；e o ，f = 1 ，珊，( 4 7 ) a x 畜b 其中e ，f = 0 ，m 时，凸优化问题( 4 4 ) 称为二次约束二次规划 ( q i l a d 豫6 c a u y0 0 n s 仃a i i n e dq u a d m d cp m g r a m ，q o q p ) 问题。 线性规划是二次规划满足p = o 时的特例，二次规划是二次约束二次规划满 足e = 0 ，f = 1 ，m 时的特例。 4 1 4 二阶锥规划 二级锥规划问题( s 姗d _ 0 r d c r 咖ep r o 孕锄，s o c p ) 与二次规划问题关系 密切，具有以下形式 m i l 血n i z c f 7 x ； s u 巧c c t t o l i a i x + 乜i i ：蔓x + 唾，f = 1 ，m ， ( 4 8 ) g 垃薯h 其中a r ”，f = 1 ，州，g 琏一。称不等式约束 i 阻+ b 蚺c t x + 其中a 阱”，二阶锥约束( s e c o n d _ 0 r d 盱硒t r a i n t ) ，因为该约束等价于要 求仿射函数( a x + b ，c t x + d ) 在碾“内的二次锥内。 二次约束二次规划是二阶锥规划满足q ；o f = 1 ，小时的特例。 4 2 优化算法 4 2 1 无约束最小化问题 无约束凸最小化问题具有以下形式 m i i m i z e ，( x ) 2 1 ( 4 9 ) 北京邮电大学硕士学位论文数学优化原理与算法 其中，：瞅一r 是一个凸函数，并且具有连续的二阶导数。