（信号与信息处理专业论文）基于凸优化理论的自适应波束形成技术.pdf

中国科学技术大学博士毕业论文 摘要 阵列信号处理作为信号处理领域的一个重要分支，其应用涉及雷达、 声纳、通信以及医疗诊断多个领域。通过对信号在时间和空间上的采样 和处理，能够更加充分地发掘信号中蕴含的信息，有效地抑制干扰，提 高系统的效率。虽然自适应阵列信号处理在理想的情况下可以达到良好 的性能，但是实际系统存在的误差会严重影响阵列信号处理最后的输出 性能。所以，寻求稳健的自适应信号处理算法一直是广大研究者追求的 目标。本文通过对阵列信号处理中现有算法的研究，提出和改进了些 现有的算法，使之更具有稳健性，适应更加复杂和恶劣的环境。本文所 做的主要工作概述如下： 1 针对传统波束形成算法对指向误差敏感的缺点，提出了一种基于概 率约束的有效设计方法，它在假定随机的方向矢量符合高斯分布的前提 下，保证其指向约束以一定的概率大于单位响应，并将概率约束的优化 问题通过凸近似的方法转变成一个迭代的二阶锥优化问题，从而可以利 用内点法求解。此外，迭代过程的收敛性也在文中进行了分析和证明。 与现有的算法相比，文中提出的算法具有较低的复杂度，更易于实现， 且算法的性能较好，因而具有较高的实用价值。 2 通信中的大部分信号具有循环平稳特性，利用信号的循环平稳特 性已经在阵列信号处理中形成了很多算法。它们无需事先己知信号的指 向，因此属于盲波束形成算法。本文分析了当系统存在循环频率误差时 基于梯度下降的循环平稳算法，由于存在s i n c 的零点效应，算法的性能随 着快拍数的增加而出现周期性的恶化。基于上述现象，文中提出了一种 利用共轭梯度求解的稳健算法，它利用共轭梯度算法快速收敛的特点， 首先寻求一个粗略的解，并求出大致的方向矢量作为信号的指向，进而 利用传统的波束形成算法求解，避免了循环频率误差对其的影响，仿真 实验证明了算法具有较好的性能。 3 近期，基于多输入多输出系统的线性接收技术也得到了较多的关 注，其核心思想与波束形成算法类似，在提取感兴趣用户信号的同时抑 中国科学技术大学博士毕业论文 制其他用户对它的干扰。然而，其算法的性能同样依赖于信道状态信息 的精确程度。因此，文中提出了一种基于随机规划理论的稳健线性接 收算法。在已知信道误差统计信息的情况下，利用切比雪夫不等式求解 最差分布情况下的概率约束表达式，并将其转化成迭代的凸优化问题求 解，同时，本文还证明了算法的收敛性。与现有的稳健接收算法相比， 文中提出的算法通过允许小的溢出概率和更具一般性的不确定模型来提 高算法的性能，并在文末给出了一些有意义的结论。 关键词：波束形成，线性接收，稳健性，凸优化，循环平稳。 a b s t r a c t ln ea n a ys l g n a lp r o c e s s i n ga sa ni m p o n a n tb r a j l c ho ft h e s j g n a lp r o c e s s 1 n gd o m a l ni sa p p l i e df o rm a n ya r e a ss u c ha sr a d a r s o n a r c o m m u n i c a t j o na n d b l o m e d l c a lt e s t i n g i tc a n e x p l o i ts u 瓶c i e n t i yt h ei n f o r m a t i o no fm es i g n a lb v s a m p l i n gt 1 1 es i g n a l i nc i m e s p a t i a ld o m a i nt os u p p r e s st h ei n t e r f e r e n c ea n di n c r e a s et h es 噜n a lt oj n t e e r e n c ea 1 1 dn o j s er a t i oo ft h e s y s c e m t h ea d a p t i v ea 盯a y s l g n a lp r o c e s s l n gc a no b t a i ng o o dp e r f 6 n 1 1 a n c ei n 吐l ei d e a lc a s e s b u t h ee 1 1 o r s l nt i l es y s t e ma l w a y s s e v e r e l ya 髋，c tt h ep e r f o n n a n c e0 ft h e 鲫r a ys i g n a lp f o c e s s i n g s 0m a n yr e s e a r c h e r sa r et q i n gt or e s e a r c hr o b u s ta r r a ys i g n a lp r o c e s s i n g a 1 9 0 r i t h m s t h i sp a p e ri n c r o d u c e ss e v e r a ia l g o r i t h m st oi m p r o v e t h er o b u s t n e s s ， w n j c nm a k e st h es y s t e mm o r ef o b u s ff o rt h ec o m p l i c a c e ds c e n a r i o t h em a j n w o r ki nm i sp a p e ri sl i s t e da sf 0 1 l o w s ： l ap o w e r f h la d a p t j v eb e a m f o n l l j n g a l g o r i t h mj nt h ep f s e n c eo ft h ep o i n c - l n ge i i r o rl sp r o p o s e db yp r o b a b i l i s t i cc o n s 仃a i n t s ，a j m j n ga tt h es h o r t c o m i n go f t h es e n s l t l v l t yt ot 1 1 e p o i n t i n ge 盯o r i ti su n d e rt h ea s s u m p t i o nt h a tt h e 啪 d o ms t e e r i n gv e c t o rm i s m a t c hh a sg a u s s i a nd i s t r i b u t i o n ，w eg u a r a n t e et h a tt h e p o 】n c l n gc o n s t r a i n ti sg r e a t e rt h a nu n i tr e s p o n s ew i t hs o m es e l e c t e dp r o b a b i l i t y jn e nb yc o n v e xa p p r o x j m a t i o n ，c h e 鲥g i n a lp r o b l e mi s c o n v e n e dt 0a ni t e r a t l v es e c o n d o r d e rc o n ep r o g m m i n i n gp r o b l e m ，w h i c hc a n b es o l v e de 硒c i e n t l v v i aw e l l 。e s t a b l i s h e di n t e r i o r - p o i n tm e t h o d f u n h e 唧o r e ，a 眦t h e m a t j c a lc o n v e r g e n c ea n a l y s i so ft h ei t e r a t i v es o i u t j o ni sa l s op r o v i d e d c o m p a r e dt oe x i s t i n g a p p f o a c h e s ，o u rp r o p o s e dm e c h o de n j o y st h ea d v a n t a g e so fe a s i e ri m p l e m e n t a n o na n dl o w e rc o m p u t a t i o n a lc o m p l e x i t y a n dh a sb e t t e rp e r f o r m a n c e s o i ti s m o r ea p p r o p “a t ei np r a c t j c e 2 n em o s ts i g n a l si nt h ec o m m u n i c a i o ns y s t e mh a v et h ec y c l o s t a c i o n a r y p r o p e r t y m a n ya l g o r i t h m sb a s e do nt h ec y c l o s t a t i o n a 巧o ft h es j g n a lj nt h ea 肋y s l g n a lp r o c e s s l n gh a v eb e e ne x p l o i t e d t h e yc a nw e l lw o r k e dw i t h o u tk n o w j n 2 t h es t e e d n gv e c t o ro fi n t e r e s t e ds i g n a l ，t h u st h e ya l lb e l o n gt ot h eb l i n da l g o n t n m s i nt h ep r e s e n c eo fc y c l ef r e q u e n c ye r r o r am a t h e m a t i c a ia n a i v s i so f l l i j 必坐堕主堡些墼 g 瑚d l e n cd e c e n t b a s e da l g o d t h mi sp r 0 v i d e d i tp o i n t so u tt h a td u et ot h ee 腑c t o fm es m c f u n c t i o n ，t h ea b o v ea p p r o a c hh a v e p e r i o d i cz e r o sp o i n ca st h en u m b e r o | s n a p s h o t1 n c r e a s i n g h e n c e ，an o v e lr o b u s tc y c l o s t a t i o n a 巧b e a m f o m l e r b a s e d o nc o n j u g a t eg r a d i e n ta l g o f i t h m ，w h i c hc a n b eu s e dt oe x t r a c ts i g n a i sw i t hc v c l o s t a t l o n a r l t yl nt h ep r e s e n c eo fc y c l ef k q u e n c ye r r i 噶i sp r o p o s e d b e c a u s eo f j t s t a s tc o n v e 唱e n c e ，p e r i o d i cn u l l sc a n b ec i r c u m v e n t e d ，a n dc h e s t e e r i n gv e c t o r 甜i n t e r e s t e ds 逸n a li se s t i m a t e d t h e nw eu s et f a d i t i o n a ib e a m f o r m e rt o a v o i d t h em f l u e n c eo f c y c l ef b q u e n c ye 1 1 r o r s i m u j a t i o n ss h o wt h a to u rn e wa l g o r i t h m p e 雨咖sw e l lu n d e rc y c i ef r e q u e n c ym i s m a t c h e s 3 0 l nt h eo t h e r h a n d ，m a n yr e s e a r c h e r sa r ea i s ot 拶i n gt 0r e s e a r c ht l el i n e a rr e c e l v e rb a s e do n m u l t i p l e - j j l p u tm u 】t j p l e - 0 u t p u ts y s t 锄t h ek e yi d e ao fi t 1 ss l m l l a rt oa d a p t i v eb e a m f o r r n j n ga l g o r i t h m s b o t ho ft h e ma r e t 删j n g oe x r a c tt h ei n f o 肿a t i o no fi n t e r e s t e du s e r w h i l er e j e c t i n gt h e i n t e r f e r e n c ea n dn o i s e c o m p o n e n t h o w e v e r t h ep e 0 咖a n c eo f1 i n e a rr e c e i v e r h j 曲l yd e p e n d so nt h e c h a n n e ls t a t ei n f o 啪a t i o n h e n c e ，b a s e do np r o b a b i l i t y c o n s t f a i n e do p t i m i z a c 1 0 n ，ar o b u s ti l n e a rr e c e i v e rw i t hw o r s t - c a s ep r o b a b i l i t yg u a r a n t e ei sp r o p o s e d 1 nt h l s p a p e r u s j n gt h em u l t i v a r i a t ec h e b y s h e vi n e q u a l i c y ，t h ed e t e n n i n i s t i c e x p r e s s i o n so ft h ew o r s t - c a s ep m b a b i l i s t i c e n c eo fs t a t i s t i c a lp r o p e r t yo fc h a n n e ls t a t e c o n s t r a i n t sa r ed e v e di nf h ep r e s i n f o r m a t i o n t h e na ni t e r a t i v ec o n v e xp r o g r a m m i n ga l g o t h mi sd e v e l o p e dt oo b t a i nt h er o b u s cs 0 1 u t i o n s ，a n dt h e m a t h e m a t i c a lc o n v e 略e n c ea n a l y s i si sa l s op r o v i d e d c o m p a r e dt ot h e e x i s t j n g r e c e i v e f s ，o u rp r o p o s e dr e c e i v e ri m p r 0 v e st h ep e e 白砷a n c eb ya l l o w i n gs m a l l o u t a g ep r o b a b i l i t ya n dm o r eg e n e r a lu n c e r t a i n t ym o d e l ，a n ds o m es i g n i f i c a n c c o n c l u s i o n sa r ea l s oo b t a i n e d k e y w o r d s ： b e a m f o r m i n g ，l i n e a rr e c e i v e r r o b u s t n e s s ，c o n v e xo p t i r n j z a t i o n a n d c y c i o s c a t i o n a t y 一l v 中国科学技术大学学位论文相关声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的 成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或 撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作 了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学校有权按 有关规定向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅，可以将学位论文编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名：堡垒益 如口睁夕月珈日 中图科学技术大学博士毕业论文 1 1 研究背景及意义 第一章绪论弟一早 三百y 匕 所谓阵列信号处理是指将多个传感器放置在空间的不同位置而组成的传感 器阵列，用传感器阵列来接收空问信号并对接收的信号进行处理f 1 5 j 。阵列信 号处理的应用涉及到雷达、声纳、通信、射电天文以及医疗诊断等多种领域， 是信号处理领域中的一个重要分支。 阵列信号处理的目的是进行空域滤波，在增强期望信号功率的同时滤除其 它干扰和噪声，以达到提高系统输出信噪比的目的。所以阵列信号处理中核心 的技术之一是波束形成技术，将天线阵列的接收信号通过一定的加权，使阵列 方向图在期望信号方向的增益恒定，而系统总的输出功率最小，从而完成空域 滤波的目的。同时自适应波束形成算法可以根据信号环境的变化，来自适应调 整各阵元的加权因子，达到增强信号同时抑制干扰的目的1 6 7 j 。 波束形成系统由空域若干个采样点即传感器组成阵列，对每一个阵元进行 采样而得到时间序列，再经过线性组合处理后，得到一个标量输出的序列。所 以波束形成器实质上是一个多输入单输出的多维系统。波束形成方法基本上有 两类【12 】：一类是统计最优方法；另一类是非数据依赖方法。其中非数据依赖方 法波束形成的设计与接收信号无关，类似于一般的有限冲激响应滤波器l 殳计。 统计最优方法的设计依赖于接收信号的随机统计特性。自适应波束形成是通过 对各阵元传感器加权进行空域滤波，而且它可以根据信号环境的变化，来自适 应地改变各阵元的加权因子，属于统计最优方法的一类。 自适应波束形成技术在理论上具有十分优良的性能，但是由于实际阵列天 线的非理想化，导致实际应用存在诸多缺陷。造成阵列天线误差的因素主要有 阵元响应误差、通道频率响应误差、阵元位置扰动误差、互耦等。自适应波束 形成技术对这些因素较为敏感【8 9 】，尤其是利用信号加干扰和噪声协方差矩阵 求逆的自适应方法，当信噪比较大时，虽然干扰零点位置变化不大，但是在信 号方向上也可能形成零陷，导致输出信干噪比严重下降，因此自适应波束形成 技术的稳健性成为人们十分关心的问题i l 0 t l l 】。 凸优化( 1 3 j 作为数学规划理论中的重要组成部分，近几十年来受到很多关 注，很多研究者对此进行了深入而详尽的研究，取得了不少卓有成效的成就。 上世纪九十年代以来，凸优化理论作为一个有效的数学工具，被广泛的应用到 中国科学技术大学博七毕业论文 许多工程领域，例如自动控制系统、估计与信号处理、通信与网络、电子电路 设计、数据分析和建模、统计与金融等。 凸优化理论作为一种数学工具，为何会收到如此多的青睐呢? 首先，在利 用凸优化求解相应的优化问题时，能够很好地避免陷入局部极值点，进而获取 令人满意的稳定数值解。其次，利用凸优化理论求解问题也有许多理论和概念 上的创新，例如，它能够将原始的优化问题转化为对偶问题求解，这样的转化 有时能够有效地利用分布式方法求解，从而带来工程上的更广泛的应用价值。 近期自适应波束形成理论的进展也得益于凸优化理论的成熟与应用。 z ：l l i q u a nl u o ，g e r s h m a n ，b o y d ，j i a nl i ，e l t a r 等人应用凸优化理论从不同角度 推进了自适应波束形成算法的研究工作，并有相关研究论文陆续发表于i 觅 r m n s o ns i g n a lp r o c e s s i n g ，i e e et r a n s 彻c o m m u n i c a t i o n s ，s i g n a lp r o c e s s i n g 等 信号处理界的权威期刊中。 1 2 自适应波束形成发展简介 阵列信号处理中自适应波束形成理论最早可追溯到二十世纪六十年代，迄 今己有近五十年的历史，其间主要经历了三个阶段：早期主要集中在自适应波 束控制上，如自适应相控阵列、自适应波束操控天线等。上世纪七十年代主要 集中在自适应零点控制上，如自适应滤波，自适应置零技术，自适应副瓣对消 等。八十年代以后的研究则主要关注于空间谱估计，如子空间谱估计、最大似 然谱估计等等。随着研究的加深，自适应波束形成算法已日趋完善。 自适应阵列的优良性能是通过自适应算法来实现的，有四种流行的准则来 确定自适应权。它们是： ( 1 ) 最小均方误差准则： ( 2 ) 最大信号干扰噪声比准则； ( 3 ) 最大似然比准则； ( 4 ) 最小噪声方差准则。 在理想条件下，这四种准则得到的权是等价的。因此在自适应算法中选用 哪一种性能度量并不重要，选择什么样的算法来调整阵列波束方向图进行自适 应控制是非常重要的。其原因在于各种自适应控制算法虽然都能收敛到相同的 稳态解，但它们却直接决定着阵的暂态响应速度和实际电路的复杂程度1 3 j 。 当系统存在误差或快拍次数有限时，提高自适应波束形成性能的方法很 多，目前研究较多的主要有以下方法： ( 1 ) 基于特征空间的自适应波束形成方法“锄j 。经过对有限次快拍和系统误 一2 一 中国科学技术大学m 士毕业论文 差存在情况下的自适应波束形成技术研究表明，自适应波束形成性能的下降主 要是由噪声子空间的扰动引起的，因此人们便摒弃自适应权矢量在噪声子空间 的分量而仅保存留在信号子空间中的分量，从而提高波束形成的性能，这种方 法被称为基于特征空间的自适应波束形成方法。该方法具有较快的收敛速度和 对误差较强的稳健性。 ( 2 ) 正交投影方法1 2 2 ，2 3 l 。由于期望信号的存在严重影响自适应波束形成的稳 健性，人们便先用其他方法去掉期望信号，然后再用剩下的数据求得干扰子空 间，最后把约束导向矢量向干扰子空间的正交补空问投影来得到自适应权系 数，这就是干扰对消方法。由于自适应权系数与干扰子空间正交，所以该方法 有较好的干扰抑制性能，同时有较快的收敛速度。 ( 3 ) 线性约束方法【2 4 1 。通过增加适当的约束条件，使自适应加权向量能满 足这些约束条件，从而达到算法的稳健性，如导数约束算法使得波束主瓣变 宽，从而可以在一定程度上克服对指向误差的敏感性。但由于在算法中增加了 许多的约束条件，不仅占用了系统的自由度，并且增加了系统的复杂性，而且 如果约束条件不适当，则可能使算法变得不收敛或者收敛速度缓慢。 ( 4 ) 对角加载方法1 2 2 6 i 。这种方法是在相关阵上加一对角矩阵，从而克服小 特征值发散造成的波束畸变，但是加载量的确定仍然是一个问题。在后续的工 作中，许多学者提出了对角加载方法的推广，具有代表性的是j i 锄l i 等人提出 的双约束的稳健的自适应波束形成，根据导向矢量的不确定集合可以确定最优 的加载量。z h i q u a nl u 0 等人的最差性能下的波束形成算法，将凸优化理论中 的二阶锥优化( s o c ：s e c o n d o r d e rc 0 n ep r o g r a 删嘶n g ) 应用到求解稳健的自适应 波束形成。 上个世纪7 0 年代，g a r d n e r 等人发现具有相同循环频率的信号可能循环相 关，不同循环频率的信号循环相关为零，并且将信号的这一特性引入到波达方 向( d o a ：d j r e c t i o no fa 盯i v a l ) 估计中1 2 7 l 。即用阵列接收数据的循环互相关代替自 相关，然后利用基于信号子空间与噪声子空间的方法估计信号的d o a ，这种算 法具有较好的噪声抑制特性和方向分辨率，并且可以在一定的条件下估计大于 阵元数目的信号。此后，利用信号循环平稳特性的许多d o a 和波束形成算法得 到了充分的研究，对存在循环平稳误差时的基于信号循环平稳的盲自适应波束 形成算法的稳健性研究近年来也很活跃。其中最具代表性的是j h l 朊等人提出 的稳健的自适应循环平稳波束形成算法【孤冽，该方法只使用循环频率的粗略估 计值，在自适应算法的每一步修正权值的同时在线更新信号的循环频率。上述 研究进一步拓展了自适应波束形成算法的适用范围。 一3 一 中国科学技术大学博士毕业论文 此外，随着多天线技术在无线通信系统中的广泛应用，多输入多输 出( m i m o ：m u l t i p l ei n p u tm u l t i p l eo u t p u t ) 系统中的自适应波束形成技术也得到了 广泛关注【3 3 i 。m i m o 系统中的自适应波束形成技术又可细分为发射波束形 成和接收波束形成技术两类。m i m o 系统发射波束形成将自适应阵列系统接 收波束形成技术推广到空域和时域，其基本原理就是利用信道状态信息( c s i ： c h a n n e ls t a t ei n f 0 釉a t i o n ) ，对发射信号进行波束形成处理，做到有方向性地发 送信号，同时，在发射功率约束条件下，优化分配发射功率，以最大化系统服 务质量( q o s ：q u a l i t yo fs e r v i c e ) ，或在保证系统q o s 的条件下，最小化总的发射 功率，从而减少对其他用户的干扰。近期，y e l d a r 和w 萌y u 等人以凸优化理论 来求解下行链路发射波束形成问题，将问题转化为二阶锥优化或者半正定规划 问题来求取预编码矩阵的最优解，突破了传统的波束形成方法无法求取其全局 最优解的局限，显著地提升了系统的性能。另一方面，m i m o 系统中的接收波 束形成技术与传统的阵列信号处理技术比较类似，其性能很大程度上依赖于信 道状态信息的精确程度。因此，非精确信道状态信息下的m i m o 系统稳健线性 接收算法也得到了很多研究者的关注【托3 5 】。其中，g e r s h m a n 等人应用凸优化理 论将稳健的线性接收问题转化为凸优化问题，并且利用内点法求取其全局最优 解，以保证系统性能的稳健性。 1 3 本文主要研究内容及结构安排 根据前面的论述可知，自适应波束形成是一个非常有意义的研究课题。因 此，本文以凸优化理论作为数学工具，重点对自适应波束形成算法进行研究。 例如：循环平稳波束形成算法，稳健自适应波束形成和最优线性接收机等。 在研究过程中，通过分析讨论自适应波束形成算法的优缺点，提出了一些 不同的算法去扩展自适应波束形成算法的应用范围，得出了一些有参考价值的 结果。 全文安排如下： 第二章介绍了凸优化的理论基础，主要包括凸优化的发展历史，一些基本 的定义和定理，求解凸优化问题的基本方法，以及非凸优化向凸优化转变的基 本方法。最后给出了实际应用中常见的特殊凸优化问题。 第三章着重考虑稳健的自适应波束形成算法。首先对现有的稳健波束形成 算法进行了回顾，并重点分析基于凸优化理论的稳健波束形成算法。针对基于 概率约束的稳健波束形成算法计算复杂度高，仍然需要加载因子的缺点，提出 了一种新的稳健波束形成方法，它可以利用二阶锥优化迭代求解，在保证解的 一4 一 中国科学技术大学博士毕业论文 可靠性和稳健性前提下，显著降低了算法的计算复杂度。 第四章重点研究基于信号循环平稳特性的稳健白适应波束形成技术。对基 于梯度下降( g d b ：c h d i e n td e c e n t - b a s e d ) 循环平稳波束形成算法的原理和优劣 进行了详尽的介绍和讨论，并据此提出了一种快速求解的循环平稳波束形成算 法。更进一步，对于实际应用中可能出现的循环平稳出现误差时的g d b 算法性 能进行了理论上的分析，进而提出了一种对循环平稳误差不敏感的稳健波束形 成算法。 第五章研究多输入多输出系统中的稳健线性接收问题。针对基于高斯误差 分布假设的稳健多用户接收算法，提出盯一种适用于任何分布并且存在最差概 率保证的稳健多用户线性接收算法，并且证明了该算法的严格收敛性，改善了 稳健线性接收算法的性能，同时拓展了算法的适用范围。 最后对全文的工作进行总结，并指出今后可能的研究方向。 一5 一 中国科学技术大学博士毕业论文 第二章凸优化导论 在本章中，我们将主要关注优化问题的一个特例一一凸优化。它主要包括 最小二乘、线性规划和二阶锥优化问题等1 1 3 3 6 3 7 1 。众所周知，最小二乘和线性 规划问题都已经有了系统完整的理论，在众多领域有了广泛的应用，并且能够 用数值方法迅速有效地求解【3 8 1 。作为更一般化的凸优化问题，近几十年来受到 很多关注，很多研究者对此进行了深入而详尽的研究，取得了不少卓有成效的 成就。其中，内点法作为求解凸优化问题的基本方法，在上世纪八十年代被提 出。由于它能够求解几类新的凸优化问题，例如半正定优化问题和二阶锥优化 问题，因此，被认为凸优化理论发展史上的第一个里程碑。从上世纪九十年代 开始，凸优化理论作为一个有效的数学工具，被广泛的应用到许多工程领域， 例如自动控制系统、估计与信号处理、通信与网络、电子电路设计、数据分析 和建模、统计与金融等。此外，凸优化理论与方法在组合优化和全局优化问题 的数值求解中也具有很高的应用价值1 3 9 ，删。 将一般的数学优化问题转化为凸优化问题具有很多意想不到的好处【4 3 1 。 它最突出的优势在于，该问题可以利用内点法或者其它数值方法稳定有效地求 取其最优解。这些解足够可靠并且能够装备到计算机辅助设计、数值分析工 具，甚至于实时反应或自动控制系统中。当然，凸优化问题的求解也有许多理 论和概念上的创新，例如，它能够将原始的优化问题转化为对偶问题求解，这 样的转化有时能够有效地利用分布式方法求解，从而在工程上具有更广泛的应 用价值。 2 1 凸集 2 1 1 定义 集合c 是凸的当且仅当c 内任意两点所连成的线段依旧在c 内，亦即如果对 任意z 1 ，z 2 c ，且任意口满足0 口s1 ，我们有 如l + ( 1 一口) z 2 c ( 2 - 1 ) 概括地说，如果集合内的每个点都能够被集合内的其它任意点，沿着它们之间 的一条无阻碍的直接路径所达到，并且该路径依1 日在集合内，则该集合就是凸 一6 一 中国科学技术大学博士毕业论文 图2 1简单的凸集与非凸集示例 r _ l j 一 的。图2 1 表示了一些r 2 内的简单的凸集与非凸集。其中，左图为凸集，中图 和右图均为非凸集。 我们把具有如下形式的口l z l + + 以瓢的点，其中p l + - + 以= 1 ， 且以0 ，z = 1 ，后称作点z l ，。2 ，的凸联合。一个集合如果是凸的，当且仅 当它包含了它内部所有点的凸联合。一个凸联合的点可以看作一些点的混合或 者加权平均，其中巩表示对应于戤的权值。 集合c 的凸包络，定义为集合c 内所有点的所有凸联合，表示为c o n v c = ( p l z l + + 以z 七i c ，以o ，i = l ，尼，口l + + 以= 1 ) 就像其名字所暗示的，一个凸集的包络仍然是凸的。它是包含c 的最小凸 集：如果b 是包含c 的任意凸集，则c 彻v c b 。 2 1 2 常见凸集 2 1 2 。1 直线与线段 假定z 1 ，z 2 是集合础上的两个点，且z 1 z 2 ，则具有如下形式的点集 矽= p 。1 + ( 1 一护) z 2 ( 2 2 ) 构成了通过点z l ，z 2 的直线，其中口r 。参数值p = o 对应于秒= ，沈，参数值 p = 1 对应于可= o l ，0 和1 之间的参数口值构成了z 1 ，z 2 之问的线段。 2 1 2 2 仿射集 如果通过集合c r n 内任意两个不同点的直线依然在c 内，则称c 为仿射 集。例如，如果对任意z l ，z 2 c ，p r ，我们都有如1 + ( 1 一p ) z 2 c 。亦 即c 包含了c 内任意两点的线性联合，且在线性联合中其参数和为1 。 上述思想可推广到多个点的情况。具有臼l z l + 斗以弧形式的点，其 中口1 + + 以= 1 ，被称作点z 1 ，z 2 ，瓢的线性联合。利用前面关于仿射集的介 绍，我们可以得到，一个仿射集包含它内部所有点的每个仿射联合：如果c 是 一个仿射集，z 1 ，z 2 ，吼c ，且口1 + + 靠= l ，则点秽1 2 1 + + 以z 七c - 一7 一 、 ， ，叱 ， _，j。产； ? ，一vv 中国科学技术大学博士毕业论文 对某些集合c 础的点的所有仿射联合所构成的集合，被叫做c 的仿射 包络，记为折c = _ 【p l z l + + 巩巩l 。1 ，z 2 ，钆c ，口l + + 巩= 1 ) 。仿 射包络是具有如下含义的包含c 的最小的仿射集：如果s 是任意的仿射集且 c s ，则a 厅c s 。此外，我们把集合的仿射维数定义为它仿射包络的维 数。 2 1 2 3 锥 集合c 被称作一个锥，如果对任意的z c 且口 o ，我们有如c 。此 外，若集合c 满足凸集条件，即对于z 1 ，z 2 c ，且口l ，p 2 0 ，有p l z l + 如z 2 c ，则c 被称作一个凸锥。具有这种形式的点集能够被几何描述成具有定点o 和 通过z 1 ，。2 的边缘所构成的切片所形成。 一个具有如下形式的p l z l + + 巩瓢的点，其中p 1 + + 以= 1 ， 且以0 ，i = 1 ，后被称作z 1 ，z 2 ，钆的一个锥联合。如果是凸锥c 内的点， 则甄的每个锥联合依旧在c 内。反过来说，集合c 是凸锥，当且仅当它包含了它 内部任意元素的所有锥联合。 集合c 的锥包络被定义为c 内的点的所有锥联合所构成的集合。例如 口l z l + + 以z 七l 以c ，俄o ，z = 1 ，七) ，它也是包含的最小凸锥。 2 1 2 4 超平面和半空间 一个超平面被定义为具有如下形式的集合： xi a r x = 6 ) ( 2 3 ) 其中，a r n ，a o ，且6 r 。从几何上解释，超平面 xl ，x = 6 ) 能够解释 为给定矢量a ，具有和a 的内积为常数的点构成的集合，或者它还能够解释成一 个超平面，其具有法线矢量a 而常数6 决定了超平面与原始平面的偏移。 这个几何解释也可以做这样的理解，它被具有如下形式的超平面所表述 xi ，( x x o ) = o ) 其中x o 是超平面内的任意一个点。这种表达也能转化为 ( 2 - 4 ) xl ，( x 一) ( 0 ) = o ) = ) ( 0 + a 上 ( 2 - 5 ) 一8 一 中国科学技术大学博士毕业论文 其中a 上表示a 的正交分量：对任意矢量v ，a 上均满足 a 上= v i ，v = o ) 这就意味着超平面由一个偏移x o ，加上所有与法线矢量a 正交的矢量所构成。 图2 - 2 半空间示例 一个超平面将础划分为两个半空间，一个( 闭合的) 半空间是具有如下形式 的集合 xl ，x 6 ) 其中，a 0 。一个半空间是凸集。 半空间( 2 7 ) 也能够表示成 x i ，( x 一) ( 0 ) = o ) ( 2 - 7 ) ( 2 8 ) 其中) c 0 是超平面内的任意一个点。表达式( 2 - 8 ) 暗示了如下一个简单的几何解 释：半空间由) c 0 加上任意和矢量a 构成钝角的矢量所组成。 2 1 2 5 欧几里德球与椭球 r n 上的欧几里德球具有如下形式 j e 7 ( x c ，r ) ：x 一) 【c 峪r ) - ： xi ( x x c ) t ( x x c ) 户) ( 2 - 9 ) 一9 一 中国科学技术大学博士毕业论文 其中，r o ，且1 2 表示欧几里德范数。矢量x c 是球的中心，r 为球的半 径。b ( x c ，r ) 是由所有和中心x c 的距离小于等于7 的点构成。另一种通用的欧几 里德球表示形式为 b ( x 。，r ) = x 。+ r u f i i u l l 2 1 ) ( 2 - 1 0 ) 欧几里德球是一个凸集。 一个与欧几里德球类似的凸集是椭球，其具有如下的表达形式 ：f xi ( x x 。) tp 一1 ( x x 。) l1 ( 2 一l1 ) llj 其中，p = p t 卜o ，也就是说，p 是一个对称正定矩阵。矢量x 。是椭球 的中心，矩阵p 决定了在中心) ( c 的每个方向上椭球所拓展的距离。的半 轴长度为瓜，其中，九表示p 的特征值。欧几里德球也是一个椭球，其矩 阵p = 7 _ 2 i 。 另一种通用的椭球表达形式为 = k + a u 川u l l 2 1 ) ( 2 - 1 2 ) 其中，a 是一个非奇异方阵。在这种表达式中我们能够不失一般性地假设a 是 对称正定的。如果( 2 1 2 ) 中的a 是对称半正定阵，则我们称( 2 1 2 ) 为退化椭球， 它的仿射维数等于a 的秩。退化椭球也是凸的。 2 1 2 6 范数球与范数锥 假定j f 1 | 表示a n 上的任意范数，则从范数的一般特性我们可以看出一个中心 为x c ，半径为r 的范数球可以表示为扛i j i x x 。0 r 】，它是凸的。而范数锥具 有如下形式的表达式 c = ( x ，t ) i | i x l i ) r 1 ( 2 1 3 ) 它是一个凸锥，图2 3 表示了r 3 上的二阶锥。 2 1 2 7 多面体 一个多面体被定义为具有有限数目的线性等式或者不等式的解集： p = xi 巧x ，歹= 1 ，2 ，m ，c 歹x b ，歹= 1 ，2 ，p ) ( 2 - 1 4 ) 一l o 中同科学技术大学博士毕业沦义 l 旺 、。 一一。1 l i 、 一，一f 一 1 。4 您 一l r i 图2 3r 3 上的二阶锥示例 因此，一个多面体因此是有限数只的半空问和超平面的交集。仿射集( 例如子空 间，超平面，直线) ，射线，线段，都是多面体。很容易可以看出，多面体是凸 集。 一个多面体也可以很方便地表示成更简介的形式 其中， p = xl a x5b ，c x = d ) ( 2 - 1 5 ) a = 矸 积 c = c c 三 ( 2 一1 6 ) 且u5v 表示对r m 上的矢量u 、v ，满足u v t ，i = 1 ，2 ，m 。 单体是另一种重要的多面体。假定尼+ 1 个点，仇r n 是仿射独立的， 这就意味着u l 一咖，班一钉。线性独立。南它们所决定的单体具有如下表达式： c = c o n v 伽，) = ( 岛功+ + 以锹j p2o ，1 r 口= 1 ) ( 2 1 7 ) 其中，1 表示所有元素均为1 的矢量，单体的仿射维数为后。 2 1 2 8 半正定锥 我们使用s n 表示n 几对称矩阵的集合 s n = x r n ni x = x 丁) ( 2 1 8 ) 中国科学技术大学博士毕业论文 o ，e 5 私一tl l l 图2 4 s 2 上的半正定锥示例 这是一个几( 凡+ 1 ) 2 维的矢量空间。 我们使用s 至表示对称半正定矩阵的集合 s 军= ( x s 竹i x o ) 且使用s 华+ 表示对称正定矩阵的集合 (