（运筹学与控制论专业论文）非线性自治系统的吸引域估计.pdf

l i i f 。 i ，j a1 、h e s i si no p e r a t i t ) n a ll 之e s e a r c ha n dc y b e r n e t i c s e s t i m a t i n gd o m a i n s o fa t t r a c t i o no f 1 f a u t o n o m o u sn o n l i n e a rs y s t e m s ， b yc a o i 。i l i s u p e r v i s o r ：p r o f e s s o rl ic h u n j i n o r t h c a s t e r nu n i v e r s i t y 1 a n u ar v2 i ) 1 1 8j a n u a r vz i 儿，6 予 r 独创性l 声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 二也 思。 学位论文作者签名：嘻劫再厨 日期：础，哆 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师不同意网上交流，请在下方签名；否则视为同意。) 学位论文作者签名： 签字日期： 导师签名： 签字日期： 4 气1 东北大学硕士学位论文 摘要 非线性自治系统的吸引域估计 摘要 本论文研究了非线性自治系统的吸引域估计问题，介绍了三种估计方法，在前人研 究的成果上，研究了一类s i r s 传染病模型的稳定性及吸引域估计，给出了一类含参数 的二阶二次多项式系统的吸引域估计，全文由七章组成。 第一章简单介绍了非线性自治系统的吸引域估计的产生背景及研究现状。 第二章介绍了矩问题的概念、矩量矩阵的构造，以及l y a p u n o v 意义下的一些稳定 性定义、定理以及吸引域的概念，并把吸引域估计问题转化为最优化问题。 第三章介绍了多项式的最小值问题及相关结论，给出了基于矩量理论的吸引域估计 的l m i 最优化算法，并进行了数值验证。 第四章介绍了最大l y a p u n o v 函数的概念及相关结论，给出了吸引域估计的另一种方 法一有理多项式的递归算法，并给出了数值例子。 第五章介绍了吸引域估计的第三种方法一多项式系统的参数化方法，研究了一类含 参数的二阶二次多项式系统的吸引域。 第六章研究了一类具有常数输入的总人口变动的s i r s 传染病模型的稳定性及吸引 域估计。 第七章总结全文，提出了在研究中尚未解决的问题。 关键词：非线性自治系统；吸引域；稳定性；l y a p u n o v 函数；矩量矩阵；l m i 最优化 1 - ； l 1 i 一 一h - 东北大学硕士学位论文 a b s t r a c t e s t i m a t i n gd o m a i n so f a t t r a c t i o no f a u t o n o m o u sn o n l i n e a rs y s t e m s a b s t r a c t t h i st h e s i si sd e v o t e dt os t u d y i n ge s t i m a t i o no ft h ed o m a i no fa t t r a c t i o n ( d o a ) o f a u t o n o m o u sn o n l i n e a rs y s t e m s t h r e em e t h o d sa r ei n t r o d u c e df o ri t i m p o r t a n t l y ，t h es t a b i l i t y a n dd o ao fac l a s so fs i r se p i d e m i cm o d e la r es t u d i e da n dt h ed o ao fac l a s so fq u a d r a t i c p o l y n o m i a ls y s t e mw i t hp a r a m e t e r si se s t i m a t e do nt h eb a s i so ff o m e r r e s u l t s i tc o n s i s t so f s e v e nc h a p t e r s i nc h a p t e r1 ，t h eb a c k g r o u n da n dp r e s e n tc o n d i t i o n so fe s t i m a t i o no fd o a o fa u t o n o m o 。 u sn o m i n e a rs y s t e m sa r ei n 仰d u c e db r i e n y i i lc h a p t e r2 ，t h em o m e n tp r o b l e m ，m o m e n tm a t r i x ，s t a b i l i t ) ，d e f i n i t i o n sa n dt h e o r e m si n t h el y a p u n o vs e n s e ，t h ed e f i n i t i o no fd o a ，a n dt h ee s t i m a t i o no fd o a a sa no p t i m i z a t i o n p r o b l e ma r ei n t r o d u c e d i nc h a p t e r3 ，s o m ei m p o r t a n tr e s u l t sa b o u tp o l y n o m i a lm i n i m u mp r o b l e ma r ei n t r o d u c e d al m i ( 1 i n e a rm a t r i xi n e q u a l i t y ) o p t i m i z a t i o na l g o r i t h n lt oc o m p u t et h ed o ab a s e do nt h e t h e o r yo fm o m e n t si sg i v e n i nt h ee n d ，ac o 门r e s p o n d i n ge x a m p l e i sg i v e n i nc h a p t e r4 ，s o m ed e 厅n i t i o n sa n dt h e o r e m sa b o u tm a x i m a ll y a p u n o vf u n c t i o n sa r ei n t r - o d u c e d w h a t sm o r e ，a n o t h e rm e t h o d - r e c u r s i v ea l g o r i t h i no fr a t i o n a lp o l y n o m i a l si sg i v e n i t i si l l u s t r a t e dw i t ha ne x 锄p l e i nc h a p t e r5 ，m et h i r dm e t h o d - p a r a m e t e r i z a t i o nf o rp o l y n o m i a ls y s t e m si si n t r o d u c e d a n dt h ed o ao fac l a s so fq u a d r a t i cs y s t e mw i t hp a r a m e t e r si ss t u d i e d i nc h 印t e r6 ，t h es t a b i l i t ya n dd o a o fac i a s so fs i r se p i d e m i cm o d e lw i t hi m m i g r a n t s o fc o n s t a n tf o rp o p u l a t i o nw i t hv a r y i n gs i z ea r es t u d i e d i nt h el a s tc h a p t e r t h ew h o l ep a p e ri ss u m m e du pa n dt h ep r o b l e m sw h i c ha r es t i l l u n s o l v e dj nt h er e s e a r c ha r es h o w e d k e yw o r d s ：a u t o n o m o u sn o n l i n e a rs y s t e m s ；d o a ；s t a b i l i t y ；l y a p u n o vf u n c t i o n s ；m o m e n t 、， m a t r i x ；l m io p t i m i z a t i o n r 。 匐 l 0 t ， 各 东北大学硕士学位论文 目录 目录 独创性声明i 摘要i i a b s l 聪屺t i i i 第l 章绪论1 1 1 研究背景及其现状l 1 2 本文的主要工作2 第2 章预备知识3 2 1 矩问题3 2 2l y 印u i l o v 稳定性4 2 3 吸引域估计转化为最优化问题6 第3 章基于矩量理论的l 加最优化算法8 3 1 引言8 3 2 预备知识9 3 3 无约束的全局最优化问题1l 3 4 含有约束的最优化问题1 4 3 4 1 主要结论1 4 3 4 2 吸引域估计的l m i 最优化算法1 5 3 4 3 数值例子1 6 3 5 小结l7 第4 章有理l y a p u n o v 函数的递归算法1 8 4 1 预备知识1 8 4 2 吸引域估计的递归算法2 2 4 3 数值例子2 3 4 4 小结2 6 - i v 妒0 东北大学硕士学位论文 目录 第5 章一类含参数的二阶二次多项式系统的吸引域估计2 7 5 1 预备知识2 7 5 2 一类含参数的二阶二次系统的吸引域估计3 l 5 3 数值例子3 4 第6 章一类s r s 传染病模型的吸引域估计3 5 6 1 模型的建立及平衡点的稳定性3 5 6 2 基于矩量理论的吸引域估计3 7 6 3 小结4 1 第7 章总结与展望4 2 参考文献4 3 致谢4 7 v ， y 2 一 东北大学硕士学位论文 第1 章绪论 1 1 研究背景及其现状 第1 章绪论 系统的吸引域，即是系统的局部渐近稳定区域。上个世纪6 0 年初，z u b o v 川提出了 l y a p u n o v 第二方法的一些问题，并给出了系统渐近稳定的区域求解方法，即系统吸引域 估计的一种方法，之后，很多学者开始关注这个问题。1 9 7 1 年，d a v i s o n 和k u r a k 【2 】给 出了另一种方法，考虑吸引域内的一个超平面，对吸引域进行估计。1 9 7 8 年，l o p a r o 和b l a n k e n s h i p 【3 j 考虑系统多项式是解析的情况下，利用c a r l e m a n n 线性化方法给出了系 统吸引域一系列的子集。1 9 8 8 年，t h o 印【4 】提出了非线性系统吸引域的建设性的算法， 可以估计大系统的吸引域。1 9 9 2 年，l a l i l 提出了吸引域的概念。于是，系统吸引域的 估计已经有很清晰的轮廓。 目前为止，很多学者对系统吸引域的估计给出了建设性的方法【5 9 1 。h a h n 把吸引域 估计问题转化为最优化问题，从此开创了吸引域估计的新纪元。于是，很多学者围绕这 个最优化问题进行了研究。v a r l e l l i 提出了最大l y a p u n o v 函数的概念，选取有理 l y a p u n o v 函数，进行t a y l o r 展丌，给吸引域估计的最优化问题增加更多的约束条件， 从而实现吸引域扩大。l a s s e l l r e 根据矩量理论，把含约束的最优化问题转化为l m l 最优 化问题。随后，h a c h i c h o 给出了系统吸引域估计的l m i 算法，节省了大量的计算时间。 a t e s i 提出了多项式的参数化方法，利用基本的数学理论知识进行计算。系统吸引域的 估计已有很多方法，但是大多数方法还是不能准确地给出系统完整的吸引域，而且不适 于高阶系统【l o 】。 不像线性系统，自然界中的非线性系统是非常庞大的，研究所有可能的非线性系统 的吸引域是一个巨大的挑战。由于一些方法上的限制，上述成果主要集中在研究非线性 自治系统： 童= ( x ) ，z 乏”，x ( 0 ) = x o 本质上，许多科学现象和工程可以准确地描述为非线性自治系统，一些控制设计方法可 以转化为状态变量的多项式控制，而且一些大系统利用t a y l o r 展开，可以转化为低阶的 多项式系统】。所以，研究非线性自治系统是有实际意义的。 系统平衡点的吸引域估计是稳定性分析理论中的主要问题之一，在很多实际问题中 东北大学硕士学位论文第1 章绪论 也有着重要的意义。比如在生念系统中，本文给出了的s i r s 传染病模型，对系统的局 部稳定平衡点的吸引域进行了估计，目的是把疾病控制在期望范围内；在磁悬浮系统【1 2 】 中，应用点和胞一胞映射( p c c m ) 方法，研究了系统的全局动力学行为和随着参数变化的 稳定的吸引域，这对系统控制器的设计和实施稳定控制具有重要的意义；在欠驱动机器 人系统【1 3 1 中，改进平衡控制器增大了系统的吸引域，更快更稳地将系统稳定在期望的位 置。 1 2 本文的主要工作 本文主要研究了非线性自治系统的吸引域估计，讨论了三种方法，主要包括：基于 矩量理论的l m i 最优化算法法，有理l y a p u l l o v 函数的递归算法和多项式系统的参数化 方法。具体内容安排如下： 第1 章简单介绍了非线性自治系统的吸引域估计的产生背景及国内外的研究现状。 第2 章给出了一些预备知识，介绍了矩问题的概念、矩量矩阵的构造，以及l y a p u n o v 意义下的一些稳定性定义、定理以及吸引域的概念，并把吸引域估计问题转化为最优化 问题，给出了相应的例子。 第3 章介绍了多项式的最小值问题有关的一些定义及主要结论，给出了基于矩量理 论的含有约束的最优化问题转化为l m i 最优化问题的重要结论，再根据h a c h i c h o 提供的 算法，利用l m i 工具箱求出吸引域，接着进行了举例说明。 第4 章介绍了最大l y 印u n o v 函数的概念和相关结论，给出了吸引域估计的另一种方 法一有理多项式的递归算法，然后再利用基于矩量理论的l m i 最优化算法进行计算，给 出了相应的例子。 第5 章介绍了吸引域估计的第三种方法一刀阶多项式系统的参数化方法。通过研究 这类系统的结构，加入适当的参数，得到了一类含参数的二阶二次多项式系统，对其吸 引域进行了估计，并给出了数值例子。 第6 章给出了一类具有常数输入的总人口变动的s i r s 传染病模型，并求出了该模 型的基本再生数r 。我们得到了系统两个平衡点的存在性及稳定性，进一步，根据矩量 理论，利用l m i 工具箱，对地方病平衡点的吸引域进行估计。最后，利用g l o p t i p o l y 软 件和数学分析条件极值理论，我们验证了结果的j 下确性。 第7 章总结全文，指出了一些在研究中尚未解决的问题。 2 东北大学硕士学位论文 i 7 ， ” ， “p ， ，； # tr 。j ，i v 节- ：，一。、。 第2 章预备知识 2 1 矩问题 第2 “章预备知识 在力学中，若有一长为的细棒，兵线密度为( x ) ，绕一端点旋转，则 f 。x ”咖( x ) ，刀= l ，2 ， 分别表示该细棒的质量、静力矩、转动惯量。我们考虑其逆问题，即若已知一细棒的质 量、静力矩、转动惯量等一系列量，能否确定其密度函数呢? 实际上这就是矩问题。 1 8 9 4 1 8 9 5 年，s t i e l t j e s 【1 4 】提出并完全解决了这样的矩问题：在区间 0 ，o d ) 找到一个有界非 递减函数y ( x ) ，使得它的矩r ，d y ( x ) ，玎= l ，2 ，为一个指定的数值集合以，甩= 1 ，2 ， 即 r 矿如( x ) = 以，疗= l ，2 ， 尽管矩问题是从1 9 世纪丌始研究的古典问题，但是基于研究的重要性，它重新被越 来越多的数学家所重视。目前，矩问题的研究把算子理论、矩阵论及概率论相结合，同 时又与其它的研究方向相联系。因此，它具有很重要的研究价值。 r c u n o 和l f i a l k o w 【1 5 ，1 6 】提出了如下截断复矩问题：对于复数集 y 三y 2 ”：，l ，乃o ，2 ，门l ，儿o ，。2 。，7 1 2 ，如川1 ，儿。，o ( 2 1 ) 其中 o ，乃，= 乃。需要找到复平面c 上的正b o r e l 测度，使得 = 户。z 7 批( z ) ，o f 呵2 一 ( 2 2 ) 这时，称为y 的表示测度。此问题首先由r c u r t o 和l f i a l k o w 提出，并建立了一套理 论，称为c u n o f i a l k o w 截断复矩问题。 给定( 2 1 ) 中的截断矩量序列 儿) ，o f 刀，刀n ，令 聊( 门) 堕婴业 对于m ( 甩) m 吣) ( c ) ( 肌( 疗) 所( ”) 复矩阵) ，定义z z 7 行矛z 。列的元素是 m ( 刀) ( i ，) = 乃+ f ，j “ ( o 七+ ，刀，o f + s 刀) 3 囊 尊 ： 量 东北大学硕士学位论文 第2 章预备知识 则( f + 1 ) ( + 1 ) 阶矩阵m f ，】为m ( ，z ) 的第( f + 1 ，_ ，+ 1 ) 子块，且有 m 【f ，仆= 一+ l ，一l 乃。，+ 卜l 例如，当刀= l 时，对于y ：，l ，y 2 ，乃l ，托。的二阶矩量矩阵为 m ( 1 ) ：f ，州o ，o 】 “l m 【1 ，o 】 2 2l y a p u n o v 稳定性 l y 印u i l o v 意义下的稳定性是稳定性理论中非常著名的概念之一，主要应用在运动稳 定性的研究中。l y a p u i l o v 杰出的工作成果推动了动力系统稳定性研究的巨大进步，被广 泛应用在科学领域、工程学科和生态系统等。 利用l y a p u n o v 方法准确地研究动力系统的稳定性，我们可以把相应地数学模型写 成一般的状态空间中的微分方程系统： 戈= 厂( x ，f ) ，x 毫”，f r( 2 3 ) 使其满足一些条件，如系统( 2 4 ) 。 为了进一步研究系统的平衡点和极限环，以及吸引域估计问题等，研究这类非线性 动力系统的稳定性是不可避免的。当然，在非线性系统分析与控制领域中，平衡点的吸 引域估计问题也是非常重要的。 自然界中的非线性系统是非常庞大的，研究所有可能的非线性系统的吸引域是一个 巨大的挑战，所以我们考虑系统( 2 3 ) 的一个子集系统一非线性自治系统： 戈= 厂( x ) ，x 乏”，x ( 0 ) = x o( 2 4 ) 其中厂( x ) 的元素是x 的多项式。 定义2 1 如果厂( 而) = 0 ，点j c o r ”称作系统( 2 4 ) 的平衡点：如果j 占 0 ，使得 ( x ) o ，比 x l i k 一而8 0 ，b p ，x 0( 2 5 ) 峪t 、3 则y ( x ) 称作d 上正定函数；如果一矿( x ) 是正定的y ( x ) 称作负定的。 定义2 3 1 1 7 i 令y ( x ) 为定义在o d 上的连续可导实值函数，如果满足下列条件： ( 1 ) y ( x ) 在d 上正定； ( 2 ) 矿( x ) ：f ，盟箬 厂( x ) 在d 上负定， 锻 则y ( x ) 称作系统( 2 4 ) 的一个l y a p u n o v 函数。 定义2 40 1 7 1 令x ( ，妒) 表示系统( 2 4 ) 的解，初始时刻，初始点妒r ”，j 万 0 ，当 0 妒0 o ，使得 ，x 。) l l o ，当忙。0 o ) ( 2 8 ) 假设q 。包含原点且有界，如果矿( x ) 在q 。上负定，则原点是渐近稳定的，而且当，一时， 东北大学硕士学位论文 第2 章预备知识 q 。上的每个解都趋向原点。 定义2 6 1 1 9 l 一个方阵m 称为h u n i t z 矩阵，如果它的所有特征值具有负实部。 定义2 7 0 1 9 lx ( f ，x o ) 表示系统( 2 4 ) 的解，初始点x o r ”，系统( 2 4 ) 的原点的吸引域定 义为： s = x 。r ”l 熙x ( 啦。) 专o ( 2 9 ) 2 3 吸引域估计转化为最优化问题 y ( x ) y ( x ) = 0 l v j i ，、 、 、 r ! | 川 入、 j = c ，i _ - ，_ 图2 1 吸引域确保性估计问题 f i g 2 1t h ep m b l e mo fg u 孤丑n t e e de s t i m a t i o no ft 1 1 ed o a 我们知道，准确地确定非线性系统的整个吸引域是非常困难的，只能解决一些特殊 情况。然而根据定理2 3 ，我们可以计算系统吸引域( 2 9 ) 的子集。为了研究，我们假设刀 维空间中的原点是动态系统的一个渐近稳定的平衡点。在这一部分，我们考虑二次 l y a p u i l o v 函数： y ( z ) = x 7 段，尸= 尸7 r “，尸 0( 2 1 0 ) 根据图2 1 ，给出超平面： 6 东北大学硕士学位论文 第2 章预备知识 矿( x ) = o ，x ，0 ， ( 2 11 ) 定义了使矿( x ) 负定区域的边界，在这个区域里我们寻找吸引域q 。我们可以看到，二 次l y a p u n o v 函数的吸引域是一个椭圆面。 我们的目的是找到c 的最大值c + 使得q 。完全包含在矿( x ) 负定的区域内，c 由下面 的最优化问题【1 7 】定义： p = m i n y ( x ) k ( 2 1 2 ) 【y ( x ) = o ，x o 也就是说，我们在超平面( 2 11 ) 内寻找l y a p u n o v 函数y ( x ) 的最小值。 7 东北大学硕士学位论文 第3 章基于矩量理论的l m i 最优化算法 第3 章基于矩量理论的l m i 最优化算法 3 1 引言 吸引域估计问题是非线性系统理论研究中非常重要的部分，在工程和科学领域有着 广泛的应用。估计系统的吸引域有很多方法，但大多数方法只能计算系统整个吸引域的 子集，较好的方法是使吸引域的子集尽可能扩大，但是计算效率可能会很低。我们的目 的是计算方便，在有限的时间旱得到尽可能大的吸引域。本章是利用矩量理论知识，把 吸引域估计的最优化问题( 2 1 2 ) 转化为l m i 最优化问题，进而利用l m i 工具箱进行求解。 给定实值多项式p ( x ) ：r ”寸r ，考虑它的全局无约束最小值问题： 尸h p ：2 卿p ( x ) ( 3 1 ) 和含有约束的最小值问题： 最h 瓜：= m 啦p ( x ) ( 3 2 ) 其中k 是一个半代数集合但不一定凸，定义如下： k = 吕( x ) o ，f - 1 ，2 ，) ( 3 3 ) 二次、线性、0 1 规划属于这类问题。 一维的情况，s h o r 【2 1 1 把( 3 1 ) 转化为凸优化问题。n e s t e r o v 【2 2 】提出了非常著名的内点 算法，把非负多项式写成平方和的形式，计算出全局最小值。然而，多维不同于一维情 况，不是所有的非负多项式都可以写成平方和的形式，而且在n e s t e r o v 中提到，四次多 项式的全局无约束最小值问题是一个n p 问题。通过变量连续变换，利用一个标准的凸 l m i 递归方法，s h o r 提出了把( 3 2 ) 转化为二次约束最优化问题，并进行了很好的降阶。 通过添加充分的二次约束条件，可以继续降阶，也可能得到最优值。 在本章中，我们介绍了全局无约束最小值问题( 3 1 ) 的解决方法。一维的情况下，通 过求解有限次的凸l m i 优化问题，可以得到( 3 1 ) 的近似值或者精确解。若k 是一个紧凑 集，但不一定凸，含有约束的全局最优化问题( 3 2 ) 也有类似的结论，不同在于多项式是 非负还是严格正定。对于后者，多项式如果是平方和的形式【2 3 之8 1 ，则有多种表达式，而 前者几乎没有。含有约束的情况下，非负二次多项式p ( x ) 一以可以用一般k a m s h k u h n - t u c k e r 乘数【2 9 】表示，它的全局最小值就是原始的k a n i s h k u h n t u c k e r 标量乘数。 r 碍辽 t ， 东北大学硕士学位论文 。趣 - ，f 一、一。 ：“4 第3 章基于矩量理论的l m i 最优化算法 通过特殊的l m i 递归得到最优值，含有约束的拿县最优化问题有一个原始的l m i 公 q 妒：、 。 “ 式，最优解就是全局最小值，对偶l m i 问题最优解就是p ( x ) 一p r + 的k a r u s h k u h n t u c k e r 乘数。所以，原始的和对偶l m i 问题则把矩量问题和正定多项式完美地结合起来。 n e s t e r o v 提到，一维的情况f ，口 以把非负多项式p ( x ) 一p + 写成平方和形式。考虑 对偶问题，我们可以把( 3 1 ) 和( 3 2 ) 转化为下面的最优化问题【2 9 ，3 0 】： p 卜专p ：= 固i 旦，l p ( x ) ( ( & ) ( 3 4 ) p e p ( r ”) j 、 、 和 p kh p ：2 卿j p ( x ) ( 出) ( 3 5 ) 其中p ( 瞅) ( p ( k ) ) 表示r ”( k ) 上的有限维b o r e l 测度空间，表示某个概率测度。很显然， p 和p 是等价的，因为p ( x ) p + ，则p ( z ) d p ，所以i n f p p ，反之，如果x 是尸 的一个最优解，则对p ，：= t 是可能的。 擎 3 2 预备知识 令 l ，x l ，屯，矗，x ? ，x l x 2 ，x i 矗，x ；，x 2 屯，x ：，砰 ( 3 6 )膏 为朋次实值多项式p ( x ) ：r ”一r 的一组基，s ( 肌) 表示其维数。利用多指数变量口，多 项式p ( x ) 可以写成： p ( x ) = 儿矿，口：= ，口2 ，矿：= 矸x 话，q 聊 ( 3 7 ) h s m ，= 其中p = 儿) 酞咖是p ( z ) 的系数向量。如果需要，我们可以把肌次多项式写成更高次 的形式，系数向量p r 小，次数高于研的单项式系数假设为0 。 给定s ( 朋) 维向量y ：= 虼 ，令第一个元素为蜘o = 1 ，令m 。( y ) 为s ( 朋) 维矩量矩阵。 为了说明帆( y ) ，考虑胛= 2 时，帆( y ) 的矩阵块 m ( y ) 吲“脚定义为： - 9 - 东北大学硕士学位论文 第3 章基于矩量理论的l m i 最优化算法 m ，j ( y ) = 其中只，表示第( f + ) 阶矩： y l j q m + 一l ，l y l 。j 咒一l ，川 ”，咒+ j 一1 。l j + 只，= 卜。y ( d ( x ，y ) ) 为某个概率测度。当玎= 2 ，朋= 2 时，我们可以得到 鸠( y ) = 对于三维情况，可以类似写出m 。( y ) ，矩阵块定义为 m 小，( y ) ) 晒鲥。 ( 3 8 ) ( 3 9 ) ( 3 1 0 ) 令4 表示最高次数为册的实值多项式g ( x ) ：r ”寸r 的向量空间，令( 3 6 ) 为它的一 组基，用g r 咖表示g ( x ) ：r ”jr 的系数，定义一个双线性形式( ，) y ：厶以寸r ， 例如 ( g ( x ) ，p ( x ) ) y = ( g ，m 。( y ) p ) = ( 印) 口儿= 扣( x 咖( x ) y ( 出) ( 3 11 ) 则对所有g ( x ) 以， y = ( g ，帆( y ) g ) = ( 9 2 ) 口儿= 卜2 ( x ) 以( 出) o 根据矩量理论，可能找到某个概率测度，使得m 。( y ) o 。 k 是r ”的一个b o r e l 子集，我们把乓等价转化为下面的凸优化问题p k ： p kh 罂毋j p ( x ) 咖 定义在b o r e l 概率测度空间上，在k 内有支点，则有如下定理。 定理3 1 例问题p 足和最是等价的，即： ( 1 ) i i l f 最= i n f p r ： 1 0 ( 3 1 2 ) ( 3 1 3 ) 霜 i ； 2 2 3 2 3 4 n儿儿 圯 m 山 j m j 0儿乃儿儿儿儿 j l 2 l 2 3 山 m j 山 j &蜘乩圯。圯 、 一。，i 。 7，_ “ 查! ! 垄兰塑主兰堡论文第3 章基于矩量理论的l m i 最优化算法 一一- ：- ： =：= ：= ： ( 2 ) 如果x 是足的一个最优解? 则：= t 是p k 的一个最优解； ( 3 ) 假设最存在最优解，则对于p k 的每一个最优解，几乎处处存在； ( 4 ) 如果x 是& 的唯一最优解，则：= t 是p k 的唯一最优解。 由于p ( x ) 是聊次多项式，则f p d 的最高阶为肌，所以可以用矩量变量线性表示， 对应于表示测度，有限矩量序列少= 儿 可以写成： 儿：= p 础，窆q = 七，七：o ，1 ，聊 ( 3 “) 当然，并不是每一个序列都有表示测度，也就是给定一个序列j ，不一定能找到概率测 度。一维的情况下，序列少在某个区间上有表示测度称为h a m b u 唱e r 矩量问题【3 。表 示测度存在的充分必要条件是h a n k e l 矩量矩阵3 2 1 是半正定的，即 风( y ) = y oh y 、y 1 y my m “ y m 虼+ l y 2 m o ( 3 1 5 ) h i l b e r t 提出了在一维的情况下，非负多项式可以写成平方和的形式，但是多变量情 况下，不是所有的非负多项式都可以写成平方和的形式。相对于一维的情况，多变量的 情况下，虽然存在向量y 使得矩阵帆( 少) o ，但不一定存在表示测度以。 3 3 无约束的全局最优化问题 令p ( x ) ：r ”一r 为次数聊的实值多项式，系数向量p r 咖) 。我们可以假设常数项 为零，即岛= o ，给出下面l m i 凸优化问题： 等价于 qh i n f 儿虼 7 口 s ，： ( 3 1 6 ) 肘。( y ) o 东北大学硕士学位论文第3 章基于矩量理论的l m i 最优化算法 f i 学以虼 。 口 q h s r ： i 儿吃一岛 l 口o 其中矩阵玩和吃可以由坂( y ) 得到。 q 的对偶问题q 定义为下面的l m i 凸优化问题： q h s u p ( x ，一鼠) ( = 一x ( 1 ，1 ) ) x s f ： ( x ，岛) = 儿，口0 x o 其中x 是实值对称矩阵，( 么，b ) = ( 彳b ) 的迹。 定理3 2 1 2 9 l 假设q 有一个可行解，则q 是可行的，且没有对偶差距，即 i n f q = m a x q + 定理3 3 1 2 9 l 令p ( x ) ：酞”寸碾为所次实值多项式，有全局最小值p = m i n 尸，则 ( 3 1 7 ) ( 3 1 8 ) ( 3 1 9 ) ( 1 ) 如果非负多项式p ( x ) 一p 可以写成平方和的形式，则尸等价于( 3 1 6 ) 中的凸l m i 问题q 。更准确的说，m i nq = m i nj f i ，如果x 是尸的一个最优解，则 y ：= = ( x ? ，。c ：，( x ? ) 2 ，c ? 。r ；，( ，r i ) “_ ，( ，c ：) 4 ) ( 3 2 0 ) 是q 的一个最优解。 ( 2 ) 反之，如果q 有一个可行解，则m i n q = m i n 尸当且仅当p ) 一p 可以写成平方 和的形式。 推论3 1 1 2 9 l 令p ( x ) ：r ”_ r 为2 m 次实值多项式，假设q + 有一个可行解，则 p ( x ) 一p = 吼2 ( x ) 一【m i n 尸一i n f q 】 ( 3 2 1 ) 其中g i ) ：r ”jr 是最高次数为聊的实值多项式。 考虑一般情况，当p ( x ) 一p 不是平方和形式时，我们先给出一些概念：g ( x ) ：r “jr 为w 次实值多项式： 1 2 硬 j ) 。 t 东北大学硕士学位论文 第3 章基于矩量理论的l m i 最优化算法 g ( x ) = 邬r 。 ( 3 2 2 ) 其中为多指数变量。令口( f ，) 表示矩阵m 。( y ) 的( f ，) 位置元素的下标，矩阵m 。( ) 定 m m ( ) ( f ，) 2 ；部i 小p ( 3 2 3 ) 彳c y ，= ：| ：誊蔓! ，x 卜g c x ，= 口一彳一x ； i 口一儿，o 一。2 奶，o 一弘，o m ，2 毗，i j ，2 ，i 一，3l m ( 秒) = l 缈l o 一弘o m ，2，o 一乩，o 一奶，2 明。l 一乃，l m ，3i ( 3 2 4 ) l ，l 一儿。l 一。3 毗，l 一乃j m ，3 砜，2 一儿，2 一。4j 一 若存在某一概率测度以，相应的s ( m ) 维矩量向量 虼 ，= 1 ，对于每个次数为棚 的多项式v ( x ) ：r ”jr ，系数向量v r 3 ，则有： 、 ( v ，m 。( ) v = 卜( x ) v 2 ( x 址，( 出) ( 3 2 5 ) 令心：= x r ”i g ( j c ) o ，如果一在巧内有支点，则m 。( ) o o 假设p ( x ) 的全局最优值x 满足：妒| i o ，令xh 口( x ) = 口2 一h 1 2 ，则在 k ：= x r ”l 臼( x ) o ) ，有p ) 一p ( x ) o 。考虑k 上严格正定多项式p ( x ) ，若可以写 p ( x ) ：圭g ，z ( x ) + p ( x ) 壹o z ( x ) ( 3 2 6 ) 其中g j ( x ) f _ 1 ，2 ，和f ，( x ) ，= l ，2 ，吩为适当的多项式，对所有朋，q ：可以写 q ：h i n f 儿儿 口 “： ( 3 2 7 ) m ( y ) 0 m 川( 砂) 0 1 3 东北大学硕士学位论文 第3 章基于矩量理论的l m l 最优化算法 令m 州( 砂) = 虼q ， q 为适当的矩阵，则q ：的对偶问题可以写成下面的l m i 最优 化问题： ( q ：) + h s u p ( 一x ( 1 ，1 ) 一口2 z ( 1 ，1 ) ) x z 2 0 j r ： ( 3 2 8 ) ( x ，吃 + ( z ，q ) = 以，口o 则有下面的定理。 定理3 4 1 2 9 l 令p ( x ) ：r ”一r 为m 次实值多项式，有全局最小值p + = m i np ，最优解 为z ，且州卜口，口 o ，则： ( 1 ) 当_ 时，有 i n f 创个p ( 3 2 9 ) 如果足够大，q ：和它的对偶问题( q ：) + 没有对偶差距，且( q ：) + 是可行的。 m i n q ：= p + 当且仅当 p ( x ) 一p ：童吼：( x ) + 秒( x ) 壹中( x ) = i，= l ( 3 3 0 ) 其中多项式g j ( x ) ，江1 ，2 ，最高次数为，多项式0 ( z ) ，= l ，2 ，吒，最高次数为 一l 。 3 4 含有约束的最优化问题 3 4 1 主要结论 考虑含有约束的最优化问题： 足一成：= i 期p ( x ) ( 3 3 1 ) 其中p ( x ) ：r “专r 为聊次实值多项式，k 是一个紧凑的半代数集但不一定凸，定义如下： k = 吕( x ) o ，江1 ，2 ，) ( 3 3 2 ) 其中蜀( x ) ：r ”专r 为w j 次的实值多项式，定义厩= | - 等 为 的最小整数，则吸引 1 4 建 东北大学硕士学位论文第3 章基于矩量理论的l m i 最优化算法 域估计的最优化问题原始公式( 2 1 2 ) 等价于下面的l m i 最优化问题q 羔： 。 其中 声 i q 萎h i n f 耽儿 口 s f ： m ，( y ) 0 m | 一氟( g ，少) o ，f = l ，2 ， - 詈 且m 彬 w 加蝴加眇脚m 卅叫，= ( 刀十) = 错 则q 羔的对偶问题为： ( q 墨) h ( 3 3 3 ) ( 3 3 4 ) s u p ( 一x ( 1 ，1 ) 一( o ) z j ( 1 ，1 ) ) 掌 x 。z 1 2 0，= i s 7 ： ( 3 3 5 ) ( x ，吃) + ( z ，c j 口) = 以，口o ，f - 1 ，2 ， 口 其中m ( y ) = 玩+ 吃儿，m 一哪( g 。j ，) = e 口儿，吃和c i 口为适当的矩阵。， 口0口 定理3 5 1 2 9 i 令p ( x ) ：r ”专r 为小次实值多项式，k = 蜀 ) o ，江l ，2 ，) 是一个 紧凑的半代数集，菇= 啦尸，则有： ( 1 ) 当一o 。时，有 如果足够大，且k 有非空内点，则q z 和它的对偶问题( q 冬) + 没有对偶差距。 ( 2 ) 如果p ( z ) 一p ：有下列形式： p ( x ) 一p ：= g ( x ) + g ，( x ) ，2 ( x ) j i ( 3 3 6 ) ( 3 3 7 ) 其中多项式g ( x ) ，最高次数为2 ，多项式，( x ) ，f - l ，2 ，最高次数为2 一w ，都 是平方和的形式，则m i n q 羔= 菇= m a x ( q z ) 。 15 东北大学硕士学位论文第3 章基于矩量理论的l m i 最优化算法 3 4 2 吸引域估计的l m i 最优化算法 步骤l ：把q 。( 2 8 ) 重新写成： q = x iy ( x ) u x 1 y ( x ) c ) ，c o o ( 3 3 8 ) 使得矿( x