（运筹学与控制论专业论文）非线性最优控制粘性解的应用.pdf

摘要 摘要 本文主要讨论非线性最优控制的粘性解的应用，包括应用最优控制的粘性解 方法求无约束多项式优化问题的全局最优值，以及求一般的二次规划问题的最优 值。 对于无约束多项式的全局优化问题的最优值，l a s s e r r e ( 1 ) 曾证明：对一个 偶数次多项式，若已知其某个全局最小点在某个开球内，则其全局最小值可以通 过半正定规划序列来逼近。因此，在多项式的全局优化问题中，全局最小点的模 的估计是很关键的，它是解决问题过程中重要的一环。但是l a s s e r r e 并没有给出 全局最小点的模的估计方法。本文根据j i n g h a oz h u 在文献 2 中给出的一个估计 多项式全局最优点的模的公式，将原来的无约束多项式优化问题转化为一个有约 束的多项式优化问题，再将这个有约束的多项式优化问题转化为一个最优控制问 题，证明这种转化是等价的。进而利用最优控制并结合粘性逼近的方法，求多项 式优化问题的全局最小值。主要工作是利用粘性逼近并结合有限差分方法数值求 解这个最优控制问题所对应的h a m i l t o n j a c o b i b e l l m a n 方程，从而求得原无约束 多项式全局优化问题的全局最优值。最后通过几个数值例子来验证该方法的有效 性。 由于二次规划问题是一类特殊而重要的约束优化问题，它在许多约束优化问 题中常常作为子问题而被提出来。因此二次规划问题不管在理论上还是在实际中 都具有重要作用。若h e s s e 矩阵是正定或半j 下定的，则为凸二次规划问题。对于 凸二次规划问题理论上和算法上都已经比较成熟。而当h e s s e 矩阵不定时，则为 非凸二次规划问题。非凸二次规划问题的求解异常困难。本文首先将一般形式的 二次规划问题转化为一个最优控制问题，再利用粘性逼近方法和有限差分方法来 求二次规划问题的最优值。并用数值例子验证该方法的有效性。 关键词：多项式全局优化；最优控制；粘性逼近；有限差分；二次规划：h a m i l t o n - - j a c o b i - - b e l l m a n 方程 a b s t r a c t a b s t r a c t t h i sp a p e rs t u d i e st h ea p p l i c a t i o n so fv i s c o s i t ym e t h o do nn o n l i n e a r o p t i m a lc o n t r 0 1 t h e s ea p p li c a t i o n sm a i n l yi n c l u d es o l v i n gt h eg l o b a l m i n i m u mo f p o l y n o m i a l a n dt h em i n i m u mo ft h e g e n e r a lq u a d r a t i c p r o g r a m m i n gp r o b l e mb yt h ev i s c o s i t ym e t h o d f o rt h ep o l y n o m i a lo p t i m i z a t i o np r o b l e m ，l a s s e r r e ( 1 ) p r o v e dt h a t i fag l o b a lm i n i m iz e ro fap o l y n o m i a lo fe v e no r d e rd o e ss t a yi na no p e n b a ll ，t h e nt h eg l o b a lm i n i m a lv a l u eisa p p r o a c h e db ys o l v i n ga ns e q u e n c e o fc o n v e xi i n e a rm a t r i xi n e q u a l i t yp r o b l e m s t h e r e f o r ei t i sv e r yk e yt o e s t i m a t et h eb o u n d so fn o r mo fag l o b a lm i n i m i z e ro f p o l y n o m i a l b u t l a s s e r r ed i dn o tg i v e a n yi n f o r m a t i o no nt h i si s s u e t h i sp a p e ru s e sa f o r m u l ag i v e nb yj i n g h a oz h ui n 2 t oe s t i m a t et h eb o u n d s o fn o r mo fa g l o b a lm i n i m i z e ro fap o l y n o m i a l t h u sw ec a nc o n v e r tt h eu n c o n s t r a i n e d p o l y n o m i a l o p t i m i z a t i o np r o b l e m i n t oac o n s t r a i n e d p o l y n o m i a l o p t i m i z a t i o np r o b l e m t h e nw ec o n v e r tt h ec o n s t r a i n to p t i m i z a t i o np r o b l e m i n t oa no p t i m a lc o n t r o lp r o b l e ma n dp r o v et h a tt h e ya r ee q u i v a l e n tt oe a c h o t h e r w eu s ev i s c o s i t ya p p r o x i m a t i o na n df i n i t ed i f f e r e n c em e t h o d st o s o l v et h eh a m i i t o n j a c o b i b e l l m a n e q u a t i o nc o n c e r n i n gt h eo p t i m a l c o n t r o lp r o b l e m s o m ei ll u s t r a t i v ee x a m p l e sa r ep r o v i d e dt os h o wt h e e f f e c t i v em e t h o di nt h i st h e s i s i ti sw e l l k n o w nt h a tq u a d r a t i cp r o g r a m m i n gp r o b l e m sa r ew i d e l yu s e f u l i nm a n y a s p e c t so ft h e o r e t i ca n dp r a c t i c a l i ti so f t e nc o m eu pw i t ha s s u b p r o b l e m s i n s o l v i n g n o n li n e a rc o n s t r a i n t o p t i m i z a t i o n s i ft h e h e s s em a t r i xi s p o s i t i v e d e f i n i t eo r s e m i p o s i t i r ed e f i n i t e ，t h e q u a d r a t i cp r o g r a m m i n gi sa c o n v e xp r o b l e m f o rt h ec o n v e xq u a d r a t i c p r o g r a m m i n g ，i ti sa l r e a d yv e r ym a t u r ei nt h e o r ya n da l g o r i t h m b u tw h e n t h eh e s s em a t r i xi si n d e f i n i t e ，t h eq u a d r a t i cp r o g r a m m i n gi sn o tc o n v e x an o n c o n v e xq u a d r a t i cp r o g r a m m i n g p r o b l e mi sv e r yd i f f i c u l tt ob es o l v e d t h i sp a p e rc o n v e r t saq u a d r a t i cp r o g r a m m i n gi n t oa no p t i m a lc o n t r o l a b s t r a c t p r o b l e mw h i c hi ss o l v e db yt h em e t h o do fv i s c o s i t ya p p r o x i m a t i o na n d f i n i t ed i f f e r e n c e s o m ei 1l u s t r a t i v ee x a m p l e sa r ep r o v i d e dt os h o wt h e e f f e c tiv em e t h o d k e y w o r d s ：p o l y n o m i a lg l o b a lo p t i m i z a t i o n ：o p t i m a lc o n t r o l ；v i s c o s i t y a p p r o x i m a t i o n ； f i n i t e d i f f e r e n c e ； q u a d r a t i cp r o g r a m m i n g ： h a m i l t o n j a c o b i b e l l m a ne q u a t i o n i i i 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的e i j ) 吊i j 本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名： 年月日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 年月 日年 月日 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 签名： 年月 第一章引言 第一章引言 1 1最优控制粘性解理论介绍 最优控制理论是研究和解决从一切可能的控制方案中寻找最优解的一门学 科。它是现代控制理论的重要组成部分。这方面的开创性工作主要是由贝尔曼 ( b e l l m a n ) 提出的动态规划和庞特里雅金( p o n t r y a g i n ) 提出的最大值原理。这 方面的先期工作应该追溯到维纳m w i e n e r ) 等人奠基的控制理论。1 9 4 8 年维纳发 表了一篇题为控制论一关于动物和机器中控制与通讯的科学的论文，第一次 科学地提出了信息、反馈和控制的概念，为最优控制理论的诞生和发展奠定了基 础。钱学森于1 9 5 4 年所著的工程控制论直接促进了最优控制理论的发展和 形成。 实际中，人们发现，最优控制问题就其本质来说是一个变分学的问题。然而 经典变分学只能解决控制作用不受限制的情况。实际上常常碰到控制作用受到限 制的情况，这就要求人们丌辟求解最优控制的新途径。1 9 5 3 年至1 9 5 7 年间美国 学者贝尔曼创立了动态规划理论，发展了变分学中的哈密顿一雅可比( h a m i l t o n - - j a c o b i ) 理论。1 9 5 6 年至1 9 5 8 年间前苏联学者庞特罩雅金等创立了最大值原 理。这两种方法成为了目前最优控制理论的两个柱石。 动态规划、最大值原理和变分法是研究最优控制理论的基本方法。 动态规划是贝尔曼于2 0 世纪5 0 年代中期为解决多阶段决策过程而提出来 的。这个方法的关键是建立在他提出的“最优性原理”基础上的。这个原理归结 为用一组基本的递推关系式使过程连续地最优转移。这个多级决策过程的最优策 略具有这种性质，不论初始状态和初始决策如何，其余的决策对于由初始决策所 形成的状态来说，必定也是一个最优策略。但在求最优解时要按照倒过来的顺序 进行，即从最终状态开始到初始状态为止。动态规划对于研究最优控制理论的重 要性在于：( 1 ) 它可以得出离散时间系统的理论结果；( 2 ) 它可以得出离散时间系 统最优解的迭代算法：( 3 ) 动态规划的连续形式可以给出它与古典变分法的联系， 在一定条件下，也可以给出它与最大( 小) 值原理的联系，这就使得三种解决最优 控制的基本方法在一定条件下得以沟通。 第一章 引言 庞特里雅金于1 9 5 6 年至1 9 5 8 年间创立的最大值原理是经典最优控制理论的 重要组成部分和控制理论发展史上的一个里程碑。它是解决最优控制问题的一种 最普遍的有效方法。由于它放宽了求解问题的前提条件，使得许多古典变分法和 动态规划无法解决的工程技术问题得到了解决。同时庞特里雅金在他的著作中已 把最优控制理论初步形成了一个完整的体系。 对于最优控制问题，由动态规划方法以及最优性原理可以得出其值函数所满 足的h a m i i t o n - - j a c o b i - - b e l i m a n 方程( 简称h j b 方程) ，解h j b 方程相当于解 一个最优化问题和一个偏微分方程问题。但是由于在求解的过程中这两个问题是 有机结合无法分离的，也就是要求解一个带有优化问题的偏微分方程，这显然超出 了一般微分方程的研究范围，也是一般的优化理论无法解决的，这就增加了问题 的难度，所以研究最优控制问题的数值计算在实际中具有重要的意义。由于h j b 方程一般没有解析解，所以要转而研究其数值解法。m g c r a n d a l l 和p l l i o n s 在文献 4 】中引入了h a m i l t o n j a c o b i 方程的粘性解，并证明了它的唯一性。 m g c r a n d a l l ，l c e v a n s 和p - l l i o n s 又在文献【5 中讨论了粘性解的一些性 质。h a l i lm e t es o n e r 在文献 6 】中讨论了有约束的粘性解的存在唯一性( 有关粘性 解的理论也可参阅文献【9 一【1 2 1 ) 。而近几年来，人们发现利用粘性逼近并结合有 限差分方法求解h j b 方程是求解值函数的近似值的一个有效方法。从实际数值 计算的角度，这就加快了非线性最优控制问题数值解的发展速度。其中c s h u a n g ， s w a n ga n dk l t e o 在文献 3 】中提出的m o d i f i e dm e t h o do fc h a r a c t e r i s t i c s 方法 ( 简称m m o c 方法) 就是求解h j b 方程的数值解的一个有效方法。( 其他方法 也可参阅文献 1 3 1 1 1 4 1 1 3 6 1 - - 3 9 1 ) 1 2 多项式全局优化问题的介绍 给定一个实值多项式p ( x ) ：r ”jr ，主要考虑如下的无约束优化问题 ( p ) p = m i n 。p ( x ) ( 1 1 ) j e “ 即求出p ( x ) 的全局极小值p + ，如果可能的话，还可以求出p ( x ) 的全局极小点x 对于一维情况下的多项式优化问题，s h o r ( 1 5 ) 首先说明无约束优化问题( 1 1 ) 可以归结为凸问题，n e s t e r o v ( 1 6 ) 提出将非负多项式表示成多项式的平方和。 然而，多维情况明显不同于一维情况，这是由于多维情况下并不是每一个非负多 2 第一章引言 项式都能写成一些多项式的平方和，而且n e s t e r o v ( 1 6 】) 提出即使一个四次多项 式的无约束优化问题也是一个n p 困难问题。s h o r ( 1 7 ) 提出通过一系列的变量变 换可以将有约束的多项式优化问题转化成一个带有二次约束的二次规划问题，通 过解标准的半正定规划问题可以得到最优点的一个好的下界。通过增加额外的二 次约束或许会改进这个下界值，有时还可以求得最优值。而l a s s e r r e ( 1 ) 说明多 项式的无约束优化问题( 1 1 ) 可以通过半j 下定规划问题的序列来逼近。l a s s e r r e 首 先利用m o m e m 理论( 可参阅文献 1 8 】一 2 4 】) 将原多项式优化问题转化为半正定规 划问题，又利用对偶理论将半正定规划问题转化为对偶问题，通过解对偶问题求 得原多项式优化问题的全局最优值。( 有关多项式优化问题的理论可参阅 2 5 】一 【3 4 ) l a s s e r r e 在文献 1 】中的主要定理是若次数为2 m 的多项式p ( x ) 的全局极小值 为p + ，有全局极小点x 满足对某个常数口 0 有忙口，则最优值p + 可以通过 半正定规划序列来逼近，但是l a s s e r r e 并没有给出全局极小点界值的估计方法。 本文根据文献 2 给出的一个估计多项式全局最优点的界值的公式，将原来的无 约束多项式优化问题转化为一个有约束的多项式优化问题，再利用最优控制并结 合粘性逼近的方法，估计出多项式优化问题的全局极小值。 1 3 一般的二次规划问题的介绍 二次规划问题不仅本身具有相当广泛的实际应用背景，而且在求解其他类型 的约束优化问题中也有着重要应用，例如在序列二次规划方法( s q p ) 和增广 l a g r a n g e 方法中，常常需要求解一系列作为子问题出现的二次规划问题。因此， 不论从理论上还是从实际上，研究二次规划问题都具有重要意义。二次规划能在 有限次迭代中被解或被证明是不可行的，但寻求解的效果非常依赖于目标函数的 特性和不等式约束的个数。如果h e s s e 矩阵是正定或正半定的，则为凸二次规划 问题，对于这类问题理论上和算法都比较成熟，有时并不比解线性规划更困难。 而当h e s s e 矩阵不定时，则为非凸二次规划问题，因为此规划可能有多个稳定点 和局部极小点所以求解起来更为困难。已经证明一般的二次规划问题是n p 困难 的。作为非线性约束优化问题的特例，自然可以用解约束非线性规划的某种方法 求解二次规划问题，但由于其特殊性，我们还可探讨新型求解方法。f l e t c h e r 在 第一章引言 文献 3 5 中讨论了一般二次规划问题的求解。近年来也有许多人致力于这方面的 研究并取得了可喜成果。 由于二次函数是特殊的多项式函数，因此二次规划问题也是多项式优化问题 的特例。本文中我们借助最优控制方法并结合粘性逼近方法来估计一般形式的二 次规划问题的近似最优值。 1 4 本文的结构 本文的结构是如下安排的：第二章主要求解无约束的多项式全局优化问题的 最优值。首先，根据文献 2 】中给出的估计多项式优化问题的全局最优点的界值 的公式，将原来的无约束多项式优化问题转化为一个有约束的多项式优化问题， 再利用最优控制、粘性逼近和有限差分方法求出这个多项式优化问题的全局最优 值；第三章主要介绍利用最优控制和粘性逼近方法估计一般形式的二次规划问题 的最优值，并给出了相应的算法，最后通过几个数值例子验证上述方法的有效性。 4 第二章最优控制的粘性解在无约束多项式优化问题中的应用 第二章最优控制的粘性解在无约束多项式优化问题中的 2 1 问题的提出 应用 这一章主要应用最优控制的粘性解求解以下无约束的多项式的全局优化问 题 ( p ) p m 瑚i n 。p ( x ) ( 2 1 ) 其中p ( x ) 是一个次数为2 m 的n 元多项式，这里, ，m 为正整数。 对于这样的无约束多项式优化问题，l a s s e r r e 在文献【1 】中利用m o m e n t 理论 将其转化为半正定规划问题，通过一列半正定规划问题逼近原多项式的全局最小 值。l a s s e r r e 证明：若次数为2 m 的多项式p ( x ) 的全局极小值为p ，并有全局极 小点x + 满足对某个常数口 o 萑j - i l x + 忙口，则最优值p 可以通过半f 定规划序列来 逼近。但是l a s s e r r e 并没有给出全局极小点的模的上界的估计方法。最近， j i n g h a oz h u 在文献 2 中给出了一个估计界囿多项式全局极小点的球的半径的公 式，其中还涉及一个单位球面上的优化问题，从而得到多项式全局极小点的模的 上界值a 这样，将原来的无约束多项式优化问题转化为一个有约束的多项式优 化问题，再利用最优控制并结合粘性逼近的方法得到线性方程组，以求出原多项 式优化问题的全局极小值。 这罩介绍j i n g h a oz h u 在文献 2 中给出的一个关于估计无约束多项式( 2 1 ) 最优点的模的界值的公式。在当z + 1 f 2 m 时1 ，= 0 ，且， 0 的情况下，最优 点的界值为 ax1，堡(n一2 第二章最优控制的粘性解在无约束多项式优化问题中的应用 其中蚝= m a x | 而厶是如下优化问题的最优值 - 姚辄和耶，z ) ，且如| ， i t = m i n c s ，2 ，立，善，岛s 。乏器q j 如s b 。2 2 ， s t 0 s l l 2 = s ? + s ；+ + s ：= 1 下面的例子以此公式考虑一类重要的多项式优化问题( 【2 】) 。 例1 考虑如下一类多项式优化问题最优点模的上界值 m i n x ? ”+ x 2 2 ”+ + x 。2 ”+ g ( x ) j 其中g ( x ) 是一个次数不超过2 聊一1 的多项式。首先求解如下优化问题 ，2 。= m i nj 2 。( s ) = ( 2 ，竹) ! ( s ；! ”+ s ；”+ + s 。2 ”) s 1 s ；+ s ；+ + s ：= 1 这样，我们可以将原来的无约束多项式优化问题转化为如下一个有约束的多 项式优化问题 伊：嚣 仁3 ， s ，0 x | i 以 、。 对于问题( 2 3 ) ，我们首先将其等价为一个最优控制问题，再利用粘性逼近和 有限差分方法，求出这个最优控制问题的值函数所满足的 h a m i l t o n - j a c o b i b e l l m a n 方程在某个时刻某个状态点处的近似值，从而求得问题 ( 2 3 ) 的近似最优值。 6 第二章最优控制的粘性解在无约束多项式优化问题中的应用 2 2 一个等价的最优控制问题 对于问题( 2 3 ) ，我们用最优控制方法求解。首先考虑如下问题 r a i n p ( x 。( 1 ) ) s t x = “，f o ，1 】 ( 2 4 ) x ( o ) = o ，“u = “忙口 f 面结果说明l 司题( 2 3 ) 与i 司趑( 2 4 ) 是等价的。 定理2 1 求解问题( 2 3 ) 的最优解等价于求解问题( 2 4 ) 的最优控制。 证明：( 必要性) 若x 是( 2 3 ) 的最优解，取乏- - - - - x * 为( 2 4 ) l 揪w j ，而x a 是相应 于。的轨道，则有以，即会是( 2 4 ) 的允许控制，导x a ( 1 ) = ，0 二( ，) 衍= x 4 壬g v , ( 2 4 ) 的一个允许控制磊，；是相应于云的轨道，则有i ( 1 ) = ，0 l 万( f ) df ， 忙( 1 ) | f = i ij ：云( f ) d r i l j ：l | 云( f ) 忙f 口， 则；( 1 ) 是( 2 3 ) 的可行解， 因此有 尸( ；( 1 ) ) p ( x + ) ：尸( x a ( 1 ) ) ，则二是( 2 4 ) 的最优轨道，从而“a 是( 2 4 ) 的最优控制。 ( 充分性) 若会是( 2 4 ) 的最优控制，安是相应于鑫的最优轨道，则有 三( 1 ) = r 会( ，) 办，取x = x a ( 1 ) ，则有k j | = 忙( 1 ) 忙驯( ，) l 卜口，任取( 2 2 ) 的一个 可行解；，则有例口，取二= ；为( 2 4 ) 的一个控制，二是相应于二的轨道，则有 二( 1 ) = c 二( ，) 衍= ；，由于尸( ；) = p ( 三( 1 ) ) p ( 安( 1 ) ) = p ( x + ) ，则x + 是( 2 3 ) 的最优解。 证毕 由于p ( 吒( 1 ) ) 一尸( x ( o ) ) = r v 7 1 p ) 甜d t ，则( 2 4 ) 的目标函数可转化为 m ，c ：v7 尸( x ) 材a c t ，则相应的h a m i l t 。n 函数为 h ( t ，x ，甜) = 2 r u + v7 p ( x ) u = 以+ v 尸( x ) ) r “ 由于h 。= 0 ，可见这个最优控制问题为奇异最优控制问题，最优控制必取值于 榨制区域u 的边界k 。 7 第二章最优控制的粘性解在无约束多项式优化问题中的应用 n 题i ( 2 4 ) 的值函数定义为 瞰，x ) = 鼯 即“) ) ) = i 鹾 j ：1 v 7 1 m ) ud r + p ( x ) ( 2 5 ) 其中x 。( f ) 是满足方程二= 扰( f ) ，u “p ) 1 1 0 ，在 上述方程左边增加一个扰动项刃：矿( 其中v ：为l a p l a c e 算子) ，则得至l j ( 2 6 ) 的 粘性方程为 刃：y 一詈+ 凹 _ v 妒t “) 。一一 o ，1 】q( 2 7 ) 【v ( 1 ，x ) = p ( x ) ，x q 文献【4 5 】中已经说明当s 专0 + 时，问题( 2 7 ) 的解收敛到问题( 2 6 ) 的解。因此我 们将转而求解问题( 2 7 ) 并以此来逼近问题( 2 6 ) 的解。 下面我们将按照文献 3 o e 的思想，利用修j 下特征函数法( m o d i f i e dm e t h o do f 第二章最优控制的粘性解在无约束多项式优化问题中的应用 c h a r a c t e r i s t i c 简称m m o c 法) ，建立线性差分方程来求( 2 7 ) 的解。由于方程( 2 7 ) 是一个初值问题，只能用显式方法求解。为了使用隐式方法求解需要添加一定的 边界条件。而在方程( 2 7 ) 中我们只能利用终端时刻的条件矿( 1 ，x ) = 尸( x ) ，x q 来 获取一定的边界条件，为获得圪( 1 ，x ) ，v ：y ( 1 ，x ) a q 的信息，要将状态区域q 进 行适当扩展。设扩展后的区域为q ，添加适当的边界条件( d i r i c h l e t 型边界条件) ， 贝j j ( 2 7 ) 可化为 刃：y 一罾+ 哿 - v ”“ - o 【o ，l 】孬 v o ，x ) = p ( x ) ，x q( 2 8 ) v ( t ，x ) = p ( x ) ，( f ，x ) 【0 ，l 】a q 进一步将粘性h j b 方程分成一个偏微分方程和一个优化问题，n ( 2 8 ) 可化为 砂一( 詈代t 胁) - 0 ，小 o ，1 】五 甜+ = a r g s u p - v ：v 甜 “ 一 ( 2 9 ) v ( 1 ，x ) = 尸( x ) ，x q v ( t ，x ) = 尸( x ) ，( f ，x ) 【0 , 1 】a q 这是一个对流扩散方程，可以用m m o c 方法求解。 应用文献 3 中用特征函数法求解对流一扩散方程解的方法。设 妙( f ，x ，甜) = ( 1 + “2 1 2 ， 记特征方向为r = r ( x ) ，定义算子 昙= 歹瓦l _ 万( 昙+ “v ) ，则( 2 9 ) 中的对流一扩散方程可化为 刃，2 y 一沙( f ，x ，甜) _ o v ：0 ，( f ，x ) 【0 ，1 】五 ( 2 1 0 ) 首先离散时间区f n j 【0 , 1 】，将【0 , 1 】进行n 等份，则时间间隔岔= i n , 时间点 t ”= 1 一n a t ，i 1 = 0 , 1 ，2 ，则有 沙(乙x，“)。ca3vf，、7，u*一2 1 ：g 二学 其中x = z + u a t ，而v ( t 川，x ) 可由( ，川，x ) 处的二阶t a y l o r 展式近似为 9 第二章最优控制的粘性解在无约束多项式优化问题中的应用 矿o ”，；) = y ( t n - i ，x ) + 【v ，y ( t n - i ，x ) 】r 甜+ f + i 1 ( “+ ) 7 v ：y ( t n - i ，x ) ( “+ ) ( f ) 2 ， 则问题( 2 9 ) 以及边界条件关于时间可离散为 刃弘鲨n-学1 n = o ，【0 l 】五 ；：x + “a t “= a r g s u p 一v ：y “ 川，i ) ：川，功+ v ，t y v n - l ，功甜+ 出+ 昙 ) r v ：矿( f 川，功 ) ( 出) z ( 2 1 1 ) 以f o ，曲= h 功，x 五 v ( t ”，力= 尸( 功，聆= 1 , 2 ，x o f 2 对状念空间q 可以按照一定的规则进行剖分，设剖分后的差分网格上有m 个点，记为而，x 2 ，x m 在f ”时刻，对状态点z ，有近似状态点x ，= x ，+ a tu ( t ”) ， 则求解方程( 2 1 1 ) 可以转化为以下优化问题和差分方程问题： 当月= 0 时， y ( x ，) = 尸( x ，) ，“? = a r g s u p - v ：v ( t 。, x ，) “li = x ，+ a t u 。， y ( ，o ，x ，) = p ( x ，) 当，2 = 1 , 2 ，时 刃：v ( t g l9 x i ) = 鲨学“r ta r g s 廿v w 朋o x ，= 誓+ a t u 7 ， y o ”，x 。) = 矿 ”，x ，) + v t v ( t ”，x ，) “? ，+ 去( 甜? ) r v ：矿o ”，x ，) ( “? ) ( ，) 2 若把v ，矿和v ，2 y 分别进行一阶和二阶中心差分近似，则可在预定的网格上 建立一个可解的线性方程组，经过迭代可得到值函数在所有点 ( f ”，x ，) ( ，z = 0 , 1 ，2 ，n ；i = 1 , 2 ，m ) 处的值，并进而得到问题( 2 2 ) 的最优值 p + = v ( o ，0 ) ，而具体的差分格式随着空问维数的不同而异，下面我们以二维情况 为例说明具体的求解过程。 l o 第二章最优控制的粘性解在无约束多项式优化问题中的应用 2 4 二维情况下的粘性逼近 由于我们只需求p = v ( o ，0 ) ，因此对于二维情况可以设定状态区域为 q = 【一1 ，1 2 ，对于高维空间可类似地讨论。首先将状态区域q = - 1 ，1 2 扩展为 孬= 一l 一口，1 + a 1 2 ，a 0 ，并添加d i r i c h l e t 型边界条件，则h j b 方程( 2 8 ) 可化 为 其中 刃，2 矿一百o v + s 心u p ， - v , r v “) = o ( ，x ) o ，1 】孬 r o ，x ) = 尸( x ) ，x q( 2 1 2 ) v ( t ，x ) = p ( x ) ，( f ，x ) 【0 , 1 】a q a 五= - 1 一口) 卜1 一口，1 + 口】u 【一1 一口，1 + 口】 - 1 一口) u 1 + a x - 1 - a ，1 + 口 u 【一1 一a , 1 + 口】 1 + 口) 进一步将h j b 方程分解成一个偏微分方程和一个优化问题，则( 2 1 2 ) 可化为 砷一( 詈代f + ) = o ，以小【0 ，1 x 孬 “a r g s 川u p ， - v ：v 曲 ( 2 1 3 ) v ( 1 ，x ) = p ( x ) ，x 五 v ( t ，x ) = 尸( x ) ，( f ，石) 【o 1 a 五 对于这个对流一扩散方程，可以用如上讨论的m m o c 方法并对时问离散后转化 为求解如下问题 蹦y 一型塑尝幽：o ，x 磊刀：l 2 , ， 随 ；：x + l g * 应 甜= 盯嘤妒 ( 2 1 4 ) v ( t n - 1 ，蜀= w ，力+ v t v n - i ，x ) u + 出+ 去 ) 丁e 2 、t n - t ，功 + ) 2 比o ，功= 只功，x 五 y ( f ”，功= 双曲，玎= 1 ，2 ，mx a 五 现在用有限差分法离散v ，v ，v ：矿首先，将扩展区域孬= 卜1 一口，1 + 口】2 ，口 0 沿 第二章最优控制的粘性解在无约束多项式优化问题中的应用 水平方向和垂直方向等分成m 一1 份，则步长为办= 夸笋半，状态点为 葺。，= ( 一1 一a + ( f o h , 一1 一a + u - 1 ) h ) ，= 1 ，2 ，m 记y 的一阶中心差分和二阶中 心差分分别为 彤：= ( 2 办) 一【：u 一杉：，杉：! ，+ 。一k ：! ! 一。) 万2 杉：= 办( v l n 。，j + 二，j 一4 ：! ：+ _ ：+ 。+ k ：一。) f ，j = 2 ，3 ，m 一1 则( 2 1 4 ) 关于状态变量可离散为 毋一警- - n - i ：o ，沪珈，吼夸， i ，严+ 吒 嘭2 璎尹彤。彩 ( 2 1 5 ) 磋：1 = 吁1 + 呀1 吃1 出+ 芝1 ( 呖1 ) r 铲吁1 j 1 ) 2 吃= 盹，af ，= l ，2 ，3 ，m 曙，= 舷，) ，嵫，= p ( x m ，) ，瑶= 地。) ，= 盹m ) ， = ，mi , j1 , 2 3 , 由于( 2 1 5 ) 中包含矿：一项，所以( 2 1 5 ) 仍然是一个耦合系统，在计算中可以用“? j 取代( 2 1 5 ) 的第二式中的甜? ，来解耦合系统( 2 1 5 ) ，而( 2 1 5 ) 中的差分方程可以转化 成一个线性方程组，但这个线性方程组的形式是与未知量的排列方式有关的。未 知量的排列方式不同，所得到的方程形式就不同。下面给出了未知量的两种排列 方式，但却得到了计算量差别很大的两种方程。因此，未知量的排列方式也是很 重要的。首先看未知量的第一种排列方式 令口：_ a f t ，定义向量 ，2 。 矿”= ( 嵫，形3 ”, 2 ，喙l 2 ，嵫，形3 ”, 3 ，1 3 ，聪_ 一l ，一，唿。朋一i ) 7 则向量矿”实际上是给定了( m 一2 ) 2 个未知量k ?( f ，j = 2 ，3 ，m 1 ) 的一种自 然次序，这里采用的是网格结点的自然次序，即从左往右( f 个) ，由下而上( ，个) ， 贝l j ( 2 1 5 ) 可以写成如下形式的线性方程组 p v ”= b 川 ( 2 1 6 ) 1 2 第二章最优控制的粘性解在无约束多项式优化问题中的应用 其中 p = c lc 2 c 2c lc 2 c 2 = c 2c l c 2 c 2c l ，c l = 1 4 a t口 口 l 一4 口 口 ，b ”一： 一 一l 矿2 ，2 一a e ( x 2 1 ) 一a e ( x 1 2 ) - - y n 3 ，- 2 i a p ( x 3 , 1 ) m y m n - _ 2 ，i2 一a p ( x m - 2 - 1 ) - - 矿m n - - l ，i 2 一( z p ( x m - 1 1 ) 一a p ( x m , 2 ) 一”一l v z 3 4 一l c r p ( x 2 ) 一a p ( x l 朋一1 ) - - y n 3 - i l o t p ( x 3 3 4 ) 一7 1 - - l v m - 2 3 4 一l a p ( x m - 2 m ) 一n 一1 矿m l 朋一l 一( z p ( x m - i 朋) 一z p ( x m m 1 ) 。口 口1 4 a t ，k = 3 , 4 ，m 一2 = ，卜l 坎乒一娥五) - - n - i 儿j - - i - l 玩和2 j - - n - 毗 一卯( ) k = 3 4 ，m 一2 矿? j 1 = y 叫n - - 1 + 6 v u l l - - il l ? j 1a t + 了1 ( “? j 1 ) 丁万2y 叫l i r a l ( 甜叫? l - - 1 ) ( r ) 2 i ，j = 2 ，3 ，m 一1 ，疗= l ，2 ， 其中矩阵尸是分块三对角矩阵，c 。是三对角阵，c ，是对角阵，因此尸是一个五 对角阵。 由于线性方程组( 2 1 6 ) 的计算量随着网格结点的加密而迅速增大，因此求解 方程组( 2 1 6 ) 并不容易。而方程组( 2 1 6 ) 的形式是与未知量 ： ( f ，j = 2 ，3 ，m 一1 ) 的排列方式有关的，因此我们可以通过改变未知量的排 列方式而寻求减少计算量的方法。下面给出文献 7 】中通过将未知量排列成矩阵 的方法将求解线性方程组( 2 1 6 ) 的问题转化为求解一个矩阵方程。而对于矩阵方 程可以通过s m i t h 方法求解。下面就给出未知量的第二种排列方式 第二章最优控制的粘性解在无约束多项式优化问题中的应用 若将未知量排列成如下矩阵的形式 v ”= 则( 2 15 ) 可以转化为求解如下的矩阵方程 么y ”+ v ”a ：b ”一1 其中 a = 1 一一z 口 口 2 1 a 一一z 口 2 b 川：豳一毯。1 而口，b ! ，b ；，n - 一i i 的定义如上。 口 1 仪 一一z 伐 2 剐。】 ( 2 1 7 ) 对于矩阵方程( 2 1 7 ) ，我们可以用s m i t h 方法求解。下面首先介绍用s m i t h 方法求解矩阵方程删+ x b = c ，a r 肼”，b r ”，x r “肌，c r 删”的过 程。在此之前先介绍如下定理( 参见 8 】) ： 定理a 设丑( z = 1 , 2 ，疗) 是彳的特征值，t ，( ，= 1 , 2 ，聊) 是的特征 值，则矩阵方程从+ 船= ca r 删月，b r 删埘，x r 删所，c r 删脚 有唯一解的充要条件是五，+ a t ，0 下面根据定理a 介绍用s m i t h 方法解一般矩阵方程趔+ 船= c 的过程。 若( 1 ) 彳，b 均稳定( 即a ，b 的特征值的实部均为负值) ；( 2 ) 一a ，一b 均稳定中有 一个成立。对( 1 ) 取a t 0 ；对( 2 ) 取a t 0 的情况，设a 的特征值为九= p 4 + i o - 4 ，则一彳的特征值 为一九= 一成) 一i e r a ，由于么稳定，则p 一 0 ，则 1 4 巴。 t p 第二章最优控制的粘性解在无约束多项式优化问题中的应用 允山一彳0 ，从而二彳可逆，同理一b 可逆。贝j j g v j - ( 2 1 8 ) 式左乘( 一么) ， 右乘( ，一b ) ，并移项整理得 x = ( 一彳) 一1 ( + a ) x ( d + b ) ( 一b ) 一一2 t ( 比i 一彳) c ( p i b ) - 1 ( 2 1 9 ) 令u = ( 一彳) 一1 ( + 彳) ，v = ( 1 + b ) ( 一b ) - i , w = - 2 2 ( 2 一彳) 一c ( 一b ) ，则 ( 2 1 9 ) 式可化为x = 唧+ 形，则x m = u x v + w 就是s m i t h 方法的递推公式。 下面利用s m i t h 方法求解矩阵方程( 2 1 7 ) 对于矩阵4 ，取适当的占，a t ，h 可以使一彳稳定，即一彳的特征值的实部全部 小于零，则取 0 ，