（运筹学与控制论专业论文）求解二次规划的微分方程方法.pdf

大连理工大学硕士学位论文 摘要 二次规划是一类重要的优化问题，二次规划是非线性规划的一种特殊形式，它在运 筹学、经济数学中有着广泛的应用，因此，对二次规划算法的研究具有重要意义。本论 文着重研究了求解二次规划的微分方程方法。 为了给出求解二次规划的微分方程方法，前两章给出了二次规划的基本知识和其它 预备知识：包括与二次规划相关的基本概念、微分方程的稳定性理论、最优化问题的最 优性条件。 第3 章分别给出了求解具有等式约束的二次规划的微分方程系统障碍投影方法、 求解具有不等式约束的二次规划的微分方程系统一障碍投影方法、求解二次规划的微分 方程系统障碍牛顿方法。通过空间转换技术来建立微分方程系统，并且证明在一定的 条件下，二次规划的解就是微分方程的平衡点，还证明了微分方程系统的稳定性。 关键词：微分方程系统；二次规划；空间转换；拉格朗1 3 函数：平衡点 垄墼兰盗塑型竺燮坌立堡查垫 d i f f e r e n t i a le q u a t i o nm e t h o d sf o rq u a d r a t i cp r o g r a m m i n g a b s t r a c t q u a d r a t i cp r o g r a m m i n gi sa n _ i m p o r t a n tb r a n c hi nm a t h e m a t i c a lp r o g r a m m i n g ，q u a d r a t i c p r o g r a m m i n gi sa ns p e c i a lf o r mi nn o n l i n e a rp r o g r a m m i n g ，w h i c hh a sw i d ea p p l i c a t i o n si n m a n yf i e l d ss u c ha so p e r a t i o n sr e s e a r c h ，e c o n o m i c a lm a t h e m a t i c s t h e r e f o r e ，i ti ss i g n i f i c a n tt o s t u d yt h ea l g o r i t h m s f o rs l o v i n gq u a d r a t i cp r o g r a m m i n g p r o b l e m s t h et h e s i sm a i n l y f o c u s e so nt h es t u d yo f d i f f e r e n t i a le q u a t i o nm e t h o d ，f o rq u a d r a t i cp r o g r a m m i n g i no r d e rt o d e v e l o p e d i f f e r e n t i a l e q u a t i o n m e t h o d sf o r q u a d r a t i cp r o g r a m m i n g p r o b l e m s ，t h ef i r s tt w oc h a p t e r sg i v ep r e l i m i n a r i e sa b o u tq u a d r a t i cp r o g r a m m i n ga n do t h e r t o p i c s ，w h i c h i n c l u d eb a s i cc o n c e p t sr e l a t e dt oq u a d r a t i cp r o g r a m m i n g ，s t a b i l i t yt h e o r yo f d i f f e r e n t i a le q u a t i o ns y s t e m 。a n do p t i m a l i t yc o n d i t i o n sf o ro p t i m i z a t i o np r o b l e m s c h a p t e r3c o n s i s t so ft h r e ep a r t s ，t h e f i r s ti sd i f f e r e n t i a le q u a t i o ns y s t e mf o rs o l v i n g q u a d r a t i cp r o g r a m m i n gw i t he q u a l i t yc o n s t r a i n t ，n a m e l yb a r r i e rp r o j e c t i o nm e t h o d ；t h es e c o n d i sd i f f e r e n t i a l e q u a t i o ns y s t e m f o r s o l v i n gq u a d r a t i cp r o g r a m m i n g w i t h i n e q u a l i t y c o n s t r a i n t n a m e l yb a r r i e rp r o j e c t i o nm e t h o d ；t h et h i r d i sd i f f e r e n t i a le q u a t i o ns y s t e mf o r s o l v i n gq u a d r a t i cp r o g r a m m i n g ，n a m e l yb a r r i e rn e w t o nm e t h o d t h ed i f f e r e n t i a le q u a t i o n s y s t e mi se s t a b l i s h e db ys p a c et r a n s f o r m a t i o nt e c h n i q u e s m o r e o v e r ，i nc e r t a i nc o n d i t i o n s ，a s o l u t i o nt oq u a d r a t i cp r o g r a m m i n gi sp r o v e dt ob et h ee q u i l i b r i u mp o i n t st ot h ed i f f e r e n t i a l e q u a t i o n t h es t a b i l i t yo f t h e d i f f e r e n t i a le q u a t i o ns y s t e mi sd e m o n s t r a t e d k e yw o r d s ：d i f f e r e n t i a le q u a t i o ns y s t e m q u a d r a t i cp r o g r a m m i n g ；s p a c e t r a n s f o r - m a t i o n ；l a g r a n g ef u n c t i o n ；e q u i l i b r i u mp o i n t s 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特另f j j j r l 以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：歪笪竺坌日期：丛! 乏么：箩 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名： 导师签名 大连理工大学硕士学位论文 1 引言 二次规划是非线性规划的种特殊类型，它的目标函数是二次的而约束条件是线性 的。它的一般形式为： 其中d 是月”中的一个多面体，c r ”，h 是一个”的实对称矩阵。该二次规划有许 多方面的应用，在统计学中一个典型的应用是线性回归问题：此外，二次规划也是流行 的序列二次规划问题的基本方法。在过去的几十年里，二次规划已经成为运筹学、经济 数学、管理科学、系统分析和组合优化学科的基本方法。因此，对二次规划的研究引起 了专业人员和学者们的广泛兴趣。 求解二次规划常用的算法有：l a g r a n g e 1 方法、l e m e k 方法 1 、有效集方法 2 、 k a r m a r k a r 3 算法、路径跟踪法等，本文研究的方法是二次规划的微分方程方法。为了 讨论所研究的问题，我们先看下面的非线性规划问题 f i x ) g ( 石) 0 ( z ) = 0 其中函数厂：r “寸r 1 ，g ：r ”专r ”和h ：r ”斗r7 都是二次连续可微的。 求解上述非线性规划问题有许多方法：序列极小化方法( s u m t ) 、无约束极值问题 的内点法、乘子法，线性约束的可行方向法、梯度投影法、既约梯度法等。用微分方程 方法求解非线性规划问题，最早由a r r o w 和h u r w i z ( 1 9 5 6 年) 4 3 提出，他们考虑的是 等式约束规划问题( 即在n l p 中m = 0 ) 。f i a c c o 和m c c o r m i c k ( 1 9 6 8 年) 5 以及 e v t u s e n k o 和z h a d a n ( 1 9 7 3 1 9 7 4 年) 6 也进行了研究，后由y a m a s h i t a ( 1 9 8 0 年) 1 2 、 p q p a n ( 1 9 9 2 年) 1 3 及e v t u s e n k o 和z h a d a n ( 1 9 8 5 ，1 9 9 4 ，1 9 9 5 ) 7 卜 1 1 对该方 法进行了发展和充实。特别是e v t u s e n k o 和z h a d a n 从1 9 7 3 年开始，利用微分方程的稳 定性理论，对( n l p ) 问题和一般闭集上的约束问题作了大量的研究，丰富了非线性规 划的微分方程方法，形成了系统的理论。 非线性微分方程方法的主要思想是：一个数值优化算法通常与一个微分方程系统相 关联，所构造的这个微分方程系统具有这样的性质：它的平衡点( e q u i l i b r i u mp o i n t s ) 恰好是等式约束问题的解。 rc+脚r 一2 d i i d z (厂 占 nm ，j、【 )p q( n m “ ，、【 求解二次规划的微分方程方法 下面我们来看一下该方法的研究情况。 对等式约束问题( n l p 中m = 0 ) r m l n 【“ ，( x ) ( x ) = 0 x r ” 其中函数f ：r ”寸r 1 和h ：r ”斗r7 都是二次连续可微的。 y a m a s h i t a ( 1 9 8 0 年) 与e v t u s e n k o 和z h a d a n ( 1 9 7 4 ，1 9 8 5 ，1 9 9 4 ) 年定义了相似 的系统 m ) 妄一阿( 小吣山( z ) ) 掣一帅) ( 1 1 ) 其中b ( x ) r “”是对称正定矩阵，h x ( x ) 是函数 ( x ) 在x 点处的雅可比矩阵，f 0 为常 数。 系统( 1 1 ) 中，y a m a s h i t a ( 1 9 8 0 年) 1 2 对f ；1 时b ( x ) 的情况进行了研究。 若取b ( x ) s i 时，系统( 1 1 ) 描述的轨迹x ( ，) 在奇点x 附近十分复杂，是一严重的 缺陷 1 2 。 若取b ( x ) ；v2 三。( x ，“( z ) ) 时，系统( 1 1 ) 被称为牛顿法，它克服了上述困难，使 在x 附近的解变成：z ( f ) 兰x + ( 工( o ) 一x ) p 。并且该方法具有二阶收敛性。由于收敛的 区间被严格限制在点工的邻域内，于是y a m a s h it a 利用迹连续的技术，扩大了收敛的区 域。 若取b ( x ) = i t f 。nr 0 ，则得到e v t u s e n k o 和z h a d a n 8 的微分方程系统障碍投 影法( b a r r i e rp r o j e c t i o nm e t h o d ) 。 张立卫( 1 9 9 9 ) 1 4 对等式约束问题提出下述微分方程系统 等一鼬凡地，删 掣：庐( h ( x ) ) ( 1 2 ) d t 其中b ( x ) r “为正定矩阵，：r7 斗r7 满足条件 大连理工大学硕士学位论文 1 妒( ) 在r7 的原点领域u 上可微，雅可比矩阵v 。妒( ) 7 的所有特征值在u 上有负实部。 2 ( ) 在u 上有唯一不动点，即妒( z ) = z 当且仅当z = 0 成立。 系统( 1 2 ) 是系统( 1 1 ) 的推广。 本文的主要工作 借鉴以上对各种约束规范和系统形式的研究，本论文主要将以上的研究结论用于求 解二次规划问题，得到下述结果： 1 ) 构造用障碍投影方法求解具有等式约束的二次规划的微分方程系统，分析其稳定性： 2 ) 构造用障碍投影方法求解具有不等式约束的二次规划的微分方程系统，分析其稳定 性： 3 ) 构造用障碍牛顿方法求解具有等式约束的二次规划的微分方程系统，分析其稳定性。 求解二次规划的微分方程方法 2 预备知识 2 1 基本概念 定义2 1 1 ( 梯度的定义) 设函数f ( x ) 存在一阶偏导数，x r ”，则称向量 v f ( ，) ：f 望竺，_ o f ( x ) ，- o f ( x ) 1 为厂( x ) 在点工处的梯度。 l 出l o x 2 o x 。j 定义2 1 2 ( h e s s i a n 矩阵的定义) 设f ( x ) 存在二阶偏导数，x r ”，则称矩阵 v 2 ，( x ) = a 2 厂 良? a 2 ， 融2 良i a 2 ， 苏。锄l a 2 j r 彘l 苏2 a 2 良： a 2 苏。毋2 a 2 厂 缸i 矗 a 2 舐2 缸。 a 2 ， 嬲 为f ( x ) 在点x 处的h e s s i a n 矩阵。 2 2 微分方程的稳定性理论 考虑如下形式的常微分方程组 冬= 厂( 圳) ， ( 2 2 1 ) a l 其中厂：r “，+ 卜r ”关于工连续可微，关于，连续。 在这种情况下，初始条件x ( o ) = x 。定义了系统( 2 2 1 ) 的唯一解，表示为x = x ( x 。，f ) 。 定义2 2 1 我们说系统( 2 2 1 ) 是拉格朗日稳定的( l a g r a n g es t a b l e ) ，如果对所有的 x ，满足下述条件 a 对所有的f i + ，解x ( x 。，f ) 存在； b i i x ( x 。，f ) 0 在，+ 上有界a 定义2 2 2 称( 2 2 1 ) 的解工( x ，r ) 为当f jo o 李雅普诺夫稳定( 或简称为稳定) ，如果 对任意的s 0 存在艿= 占( s ) 使得 a 满足下列条件的系统( 2 3 1 ) 的每一个解x ( x 。，f ) 对0 ， o o 有定义。 大连理工大学硕士学位论文 忙一x l l s ； ( 2 2 2 2 ) b 对这些解我们有不等式： 卜( 一t ) - x ( 工，) l | 0 , 3 8 = j ( ) 使 得l v ( x ，f ) i 0 使得 8 ( ，) 4 sk e 一，其中中( ，) = e “。 则我们有 i i x ( o i l - c k l l x 。扩4 + t i e - p ( , - , o 愀x ( x o , s ) ，s ) 怯。 对任意的 0 ，存在占 o 使得对每一个占及任意的f 0 有 愀x ，) 忙占l l x l l k ， 令i n - 0 ，使得对所有的o rc r 不等式愀粕， 占成立，并且 。9 敝，, ) l l - k t 卜占j e ”k ( 孙s 壮， 由引理2 2 ，1 可得下面的估计式 1 l x ( x 。，o l i k l l x 。l i e 5 7 “， ( 2 2 7 ) 对r ( o ，r ) 成立。我们选取充分小的占使得s 7 7 。则由( 2 2 7 ) 当肛( 工。，i i 占 时有愀，| m 成立。 定理2 3 1 在系统( 2 2 1 ) 中f ( x ，r ) 关于z 连续可微，关于t 连续。系统( 2 2 1 ) 拉哥朗 日稳定( 1 a g r a n g es t a b l e ) 的充分条件是：在月”l 上，存在一个函数v ( x ，f ) 使得 a w ( x ) v ( x ，) ，其中w ( x ) 是一个连续无穷大函数。 b 对系统( ( 2 2 1 ) 的每一个解，函数v ( x ( x 。，r ) ，) 关于变量f 非增。 证明：对任意的f 0 ，我们有 w ( x ( x o ，f ) ) v ( x ( x o ，f ) ，f ) v ( x o ，t o ) ， ( 2 3 1 ) 解x ( x 。，r ) 有界。事实上，如果不然，我们可以找到一个序列k ) t l 芟敛至l j t 兰m ，使得 ! 粤愀孙r * ) 1 1 = c o ， 并且对无穷大函数w 可得 l i r a r w ( x ( x o , f 女) ) = o o ， 这与( 2 3 1 ) 矛盾。因此解x ( x 。，) 是无界可( 向右) 延拓的且 s u p l l x ( x o ，f ) 0 0 。称v ( x ) 在u 上负定，若v ( o ) = 0 ，且当x u 0 时v ( x ) 0 。如果不等式v ( x ) 0 任0 ) 在u 上 成立，我们说函数v ( x ) 在上非负( 非正) 。 下面介绍两个记法： s 。= 每尺“i i i x l l = f 以= & e r ”肛i i 1 1 2 2 ，y 3 ( x ) = x - - x * | | 2 2 ， 如果点x 是f ( x ) 的孤立极小点，则存在一个邻域u ( x ) ，使得上面三个函数在其中 正定。通过系统( ( 2 3 3 ) 对它们进行微分得 i 。= - t l v f ( 工 1 1 2so ，1 。2 = 一v f ( x ) 7 v 2 ，( x ) 可( x ) ，v 3 = 一( w ( x ) ，x - - x ) 。 如果在点x = x + 处，可v f ( x ) = 0 且v 2 f ( x ) 正定，则函数v j ，v 2 在工u ( x + ) 为负， 并且由l y a p u n o v 渐进稳定定理2 3 3 可得方法( 2 3 3 ) 到点工= x 的局部收敛性。 如果厂( x ) 是严格凸的，则对x u ( x ) 有v 3 蔓f ( x 。) 一，( x ) 0 。v ，在u ( x ) 上负定 且方法( 2 3 3 ) 局部收敛于工。 如果用一阶逼近的稳定性定理( 定理2 2 1 ) ，考虑下面的系统： 皇 = v 2 ，( x ) ) ，x ( 工。，f ) = x + y ( f ) ， e l l v 2 f ( x ) 的正定性意味着方法( 2 3 3 ) 的局部指数收敛性。 令f ( x ) 二次可微，v2 f ( x ) 在r ”上非奇异。则我们可以考虑用下面的系统来求它 的极限点，即把牛顿法应用到微分方程的方法上。 等一v f ( 矿v f ( m 我们用l y a p u n o v 函数的方法来证明收敛性 v ( x ) = ( v f ( x ) ，v f ( x ) ， 大连理：【大学硕士学位论文 可得 了d v = 一2 v ( x ) , v ( o ) = ( v f ( x 。) ，v f ( x 。) ) ， 讲 。 积分得v ( t ) = v ( o ) e 。因此当t _ o 。时，方法收敛到f ( x ) 的不动点( s t a t i o n a r y p o i n t s ) 。 2 4 一般约束问题的最优性条件 约束优化问题的最优性条件指出最优化问题的目标函数与约束函数在最优解处应 满足的必要条件、充分条件和充要条件，它们是最优化理论的重要组成部分，对包括本 文在内的最优化算法的构造及算法的理论分析都是至关重要的。本节针对形如( n l p ) i h i 题的一般约束问题给出其最优性条件。由于篇幅所限，证明略。 考虑下面的非线性规划问题 ( n l p ) m i n f ( x ) s 1 g ( x ) 0 。 h ( x ) = 0 x r n 它的拉哥明日函数为： z ( x ，“，v ) = 厂( x ) + “7g ( x ) + v7 。 ( 工) 。 约束指标集j o ) = i b ( x ) = o , i = l ，m 。 一阶必要条件 定理2 4 1 ( 广义拉哥朗日乘子存在定理) 若( 1 ) 函数f ，g ，h 是连续可微的，即f ，g ，h c l ( r ”) ： ( 2 ) x + q ，q = j r ”i g ( x ) o ， ( x ) = o 为可行域； 则z = 铮k t 条件成立，即： 存在“r ”，v r 7 ，满足 fg ( x ) so 。，h ( x ) = 0 “o ，“? 吕( x ) = o ，i = 1 ，m l v ，l ( x 。，“，v ) = 0 。 求解二次规划的微分方程方法 其中z = zer ”i v g 如) t z o ，f ，( x ) ，v h ( z ) 7z = 0 ，v f ( x f z 0 j 磁，( z ) 7 y 0 l ( x ) e ( x ) 的y 0 ，成立着y 7 v 二( z ，“，v 。) y 0 ，则t 是孤立的局部解。 定理2 4 6f 雅可比唯一性条件) 若( 1 ) ，g ，h c 2 ( 贾。) i ( 2 ) 在x 点处k - t 条件成立； ( 3 ) 严格互补松弛条件成立： o ，i l ( x ) ； ( 4 ) 线性无关约束规范成立，即 阮，( x 。) l f j ( 工) j u 扣 ，( x ) j ，= 1 ， 线性无关： ( 5 ) 0 ：v h ( x ) 7y = o ，v g ，( x ) 7y = 0 i l ( x ) ， y r v 二( x ，“，v + ) y 0 ， 则工+ 是孤立局部极小点，且系统 f ( z ) v ，l ( x ，“，v ) “，g ，( x ) w 。g 。( x ) 0 ) 的雅可比阵在z = ( 工+ ，“，v ) 处非奇异。 = 0 。+ 求解二次规划的微分方程方法 2 5 二次规划的最优性条件 下面考虑具有等式约束的二次规划问题 其中b r ”，a r ，r ( a ) = 卅( a 歹0 满秩) ， 它的l a g r a n g e 函数为 l ( x ，”) = 去x 7 月譬+ c t 工一“7 ( 一z 一6 ) 。 等式约束二的次规划的一阶必要性条件，即k t 条件为 f 上，( x ，“) = 爿l + c a r u = 0 ， ll 。( x ，“) = a x b = 0 ， 其矩阵形式为 三一甜州舟 s 固 在上热系数矩阵称世= 日一卅为k t 矩阵瓤一e 矩阵。 定理2 5 1 假设a 为列满秩矩阵，r ( 爿) = m ，若投影h e s s i a n 矩阵z 7 h z 0 ，则二 次规划( 2 5 1 ) 的k t 矩阵是非奇异的，从而存在唯一的k t 对( x ，“+ ) 满足方程组( 2 5 2 ) 。 定理2 5 2 假设彳为列满秩矩阵，矗( 爿) = m ，若投影h e s s i a n 矩阵z 7 h z 0 ，则二 次规划( 2 5 1 ) 的k t 矩阵有n 个正的特征值，m 个负的特征值，并且没有零特征值。 定理2 5 3 假设a 为列满秩矩阵，r ( a ) = m ，若投影h e s s i a n 矩阵z 7 h z 0 ，则满 足方程组( 2 5 2 ) 的k t 对( x ，“) 中x + 是问题( 2 5 1 ) 的唯一最优解。 下面考虑具有不等式约束的二次规划问题 j m i nm ) = 圭x 7 胁z ， 【“ a x b ， 其中b r ”，爿凡”，r ( a ) = m ( a 列满秩) ， u2 x，+胀， 1 2 = 6 力= 八叙 m n ，【 大连理工大学硕士学位论文 它的l a g r a n g e 函数为 地= 三x 7 胁+ c t x - l d r ( 一x _ 6 ) 。 不等式约束二的次规划的一阶必要性条件，即k t 条件为 h x + c a 7 “= 0 a x b 0 ， ( 出一6 ) 甜f = 0 ，i = i ，m “0 若记a x b w = o ，w = ( w l ，) 7 0 ，我们可将上述k t 条件写成 h x + c a 7 u = 0 a x b w = 0 y ，w i = 0 ，i = 1 ，肌 d w 0 。 求解二次规划的微分方程方法 3 微分方程方法求解q p 问题 3 1n l p 问题的微分方程方法 考虑如下的非线性规划问题 r a i n u ) ， s d 石x = x r 4 ：g ( x ) = 0 。，x p 。 ( 3 1 1 ) 其中函数厂：r ”一r 1 , g ：r ”一r ”都是连续可微的，0 。是m 维的零向量，可行域非空。 接下来考虑新的空间坐标【y 1 ，y “ 作可微的变换x = f ( y ) ，掌：r ”斗尸，p = c l f ( r ”) ，则原始的问题( 3 1 1 ) 可转换为下面 的非线性规划问题： r a i n 7 ( y ) = 厂( 善( y ) ) s j y y ， ( 3 1 2 ) 其中y = y r ”：季( y ) = g ( f ( y ) ) = 0 。 。 问题( 3 1 1 ) ，( 3 1 - 2 ) 的拉格朗日函数分别为 l ( x ，“) = f ( x ) + “7 9 ( x ) ， z ( y ，“) = 7 ( y ) + “7 季( y ) 。 为了得到问题( 3 1 2 ) 的数值解，我们寻求下列微分方程系统的解的极限点 等一孤删， ( 3 1 3 ) 其中t ( 弘“) = 元( y ) + 彩“，z = 害正，彰= 石d x ，若令了= 石d x ，则有 ，y = j r , ，童y = g , j ， 函数u ( y 1 满足下列条件 警一引，) 己( 删y ) ) 一曲) ，f o 。 ( 3 1 4 ) 若了( y ) 是非奇异矩阵，则存在逆变换y = j ( z ) ，j ( 工) = 了( 占( x ) ) ， 大连理工大学硕士学位论文 由( 3 1 3 ) ，( 3 1 4 ) 可得到下面的形式 鲁= 等等= ，( x ) 象- g ( x 心( t “( 瑚，尸r ( ，5 ) i ( 工) “( z ) + g ，( x ) g ( 工) 正( x ) = r g ( x ) 。 ( 3 1 6 ) 喜中r ( x ) = g x ( x ) g ( x ) g ：( x ) ，g ( x ) = j ( x ) j 7 ( 工) 。 记岷。月( ) = m ，其逆阵w + = w7 ( w w 7 ) ，厅( ) = ，一w + w ，i 。是单位阵 k e r = z r ”：w z = 0 m ) 。 若乳( x ) 满秩，则由( 3 1 6 ) 求解可得到“( z ) ，把“( 石) 带入到( 3 1 5 ) 式中则有下 列式子成立 _ d x = 一j ( x ) 仿【g ，( x ) ，( x ) 】，7 ( x ) 正( x ) + r g ；( x ) ，o ) rg ( x ) ( 3 1 7 ) d t 、 x ( t ，) 是具有初值x ( o ，) = ，p 的柯西问题( 3 1 7 ) 的解。 若问题( 3 1 1 ) 中没有条件z p ，若z 或者r = 0 ，则问题( 3 1 7 ) 为梯度投 影方法，此方法已经被许多国内外专家和学者研究了。 对于下面的非线性规划问题 m i n 厂( x ) ， s 1 工= 工p = r ：g ( x ) = 0 m ) 。 作变换j = f ( y ) ，1 i s 门，r ”一j p ， ( 3 1 8 ) j ( y ) = 记5 ( y ) 是逆变换 ，o ) = f ( y 1 ) 占2 p 2 ) 害( y 1 ) f ”( y ”) 舌2 ( y 2 ) = d ( f ) ， f ”( y 。) j l ，：。( ；， 求解二次规划的微分方程方法 g ( x ) = j2 ( x ) = d ( 口( 工) ) ，臼( x ) = 【( 善1 ( y 1 ) ) 2 ，( 善2 ( _ y 2 ) ) 2 ，( 芋”( y ”) ) 2 】| 。 y = o i j l 空间变换f ( 力满足下列条件 c ，矩阵g ( x ) 是有定义的，在点x p 处是连续的，仅在点x b d r y p 处是非奇异的。 c 2 0 ( 工) = 0 亡，x = 0 ，1 s f r l 。 c 3 f ( y ) 满足条件c 2 ，口( x ) 在u ( r 2 ) 有定义、可微的且扫( o ) 0 , 1 i n 。 c 4 j 口 0 ，朔寿足0 ( x ) = ( x ) 。+ d ( ( x ) 。+ 。) ，l i 竹。 例：x = f ( y ) = 去c y r ，( z ) = d ( x ) ，g ( x ) = d ( x ) 。 ( 3 1 1 0 ) i f = f ( y ) = e 7 ，( z ) = d ( z ) ，o ( x ) = d2 ( 功。 ( 3 1 1 1 ) 以上两个例子中，在6 奶俨上雅可比矩阵是奇异的，两个转换都满足c 。，c ：，转换 ( 3 1 ，1 0 ) c 3 也成立。 应用e u l e r 方法解微分方程系统( 3 1 5 ) ，得到 x “i = z 一h k g ( x ) 三，( x t ，u ( x i ) ) ，x o p ， ( 3 1 1 2 ) 其中步长 0 。 定义3 1 1 ：当或( x ) ( 1 i h ) 是线性无关的，约束规范( c q ) 成立。 定义3 1 2 ：如果在点x 处c q 成立，则点x 是问题( 1 ) 的正则点。 方程( 3 1 6 ) 可以写成 g ，( x ) g ( x ) 上，( 工，“( x ) ) = 刁 ( x ) ， ( 3 1 1 3 ) g ( x ) t ( x ，“( x ) ) = 0 。 ( 3 1 1 4 ) 引理3 1 1 ：孝( j ，) 满足c 1 ，c q h 戋立( 1 ) ，x p 证明：r ( x ) = g x ( z ) g ( x ) ( x ) 可 逆、正定的，其中，g ( x ) = j ( x ) j 7 ( 工) 。 证明：b ( x ) = ，7 ( x ) g f ( x ) ，只要证明r ( 曰) = m 即可。 若z i n t p ，j ( x ) 非奇异，g ，( x ) 行满秩，显然结论成立。 若x b d r y p ，假设r ( b ) 0 。) 。 应用方法( 3 1 5 ) 和( 3 1 1 2 ) 解决问题( 3 2 1 ) ，我们得到下面连续和离散的两 种微分方程形式 去一g ( 川胁+ c - a r u ( 圳， 邶，砌铀 o ， ( 3 2 2 ) r i + l = x i h k g ( x i ) 【m + c a 。u ( x i ) 】，x 0 0 。 ( 3 2 3 ) 其中函数“( 工) 可以由( 3 1 6 ) 得到 a g ( x ) a 7 u ( x ) 一a g ( x ) ( h ( x ) + c ) = v ( b a x ) 。 ( 3 2 4 ) 鲁= 正妄= ( 胁+ 矿石d r = 一慨坝胁+ c - a r u ( 砌4 2 + 纠7 ( 曲( 6 一爿功。 因此当t 0 时f ( x ( t ，x 。) ) 是单调递减函数，若x ( t ，x 。) e x 或者迹接近于z ( 当，j 时) ，则l a x ( t ，) - b i i 是充分小的，即系统是渐进稳定的。 若空间转换善( y ) 满足( 3 1 8 ) ，条件c ，c ：成立，系统( 3 2 4 ) 对所有的x 0 有唯 一解，( 3 2 2 ) 的迹不会离开彤，空间转换函数起到了障碍的作用，因此，称( 3 1 7 ) 和( 3 2 2 ) 为障碍投影方法。 微分方程( 3 2 2 ) 有下面的积分 塞竖三姿塑型塑塑坌塑堡互鲨 一一一 a x ( t ，j c o ) = b + ( i x o - b ) e 一。 ( 3 2 5 ) 定理3 2 1 设x ) 是问题( 3 2 1 ) 的唯一解，孝( j ，) 满足条件c 2 ，c ，那么当f 0 时，系统( 3 2 2 ) 在x 处是渐进稳定的。菇f 且3 h 0 ，当0 0 。 因此根据李雅普诺夫线性原则，平衡点x 是渐进稳定的且下式成立 ，1，im。sup掣一五。 记向2 寺，其中z2 。m 。a x 。 f ， 】。h k 6 = 0 。 ( 3 3 6 ) 引理3 3 1 设妒( y ) 满足c 5 ，在z p 处q 2 成立，则r ( z ) 是可逆、正定的。 其中r ( z ) = m ：( z ) g ( p ) 中；( z ) 。 若坼，= i g x 坳o m ) ，c g = 。 证明：若能证明h ( z ) 是行满秩的即可 r ( z ) = h ( z ) h7 ( z ) ，记仃( p ) = l ，2 ，s k o s - 0 p o ，v ? = 0 。 引理3 3 2 设引理3 3 1 的条件在z r ”r ：处都满足，则z 是( j 3 5 ) 的平衡点 证明：已知鲁= - l x ( z ，吣) 鲁- _ g ( p ) v ， 若z 是( 3 3 5 ) 的平衡点j g ( p ) v = 0 ，即j ( g ) j 7 ( p ) v = 0 j j 7 ( p ) v = o ，v k e r j ( p ) ， d ( p ) v ：o ，壁里婴：一。：( z ) 6 ( p ) ：( z ，w ( z ) ) = 一椰( z ) j 。( z ) = o 。 口f 充分性是显然的。 口 切锥霞( x ) ：往r ”：g 。( x ) 更= o 。；( ：，i = o ，f c k h ( x ) ) 。 定理3 3 i ( 渐进稳定性定理) i m z , w ) 是( 3 3 2 ) 的k t 点，在( z ，w + ) 处c q ，s c c 成立，妒( y ) 满足c 2 ，c 3 ，对晰g ( x ) ，i 0 ，都有i 7 l 。( x ，w + ) i 0 ，那么当f 0 时， 在局部孤立极小点z 处系统( 3 3 5 ) 渐进稳定：当步长纸为充分小的常数的时候，k 求解二次规划的微分方程方法 假设沿着系统( 3 3 5 ) 的迹f 列条件成立 h ( x ( t ，z o ) ) + p ( t ，z o ) i 0 。 从上式我们可以定义p 作为h 的函数，n n ( 3 3 5 ) 不考虑p 进行积分，得到 鲁一驰，w ( 砌， ( 3 3 8 ) 其中 r c x ，w c x ，+ 。，c x ，正c x ，= r _ ， c ，s 。， 而 “膏，= 中，c x ，中：c r ，+ 2g 。：o r e 。! x ， 。 沿着迹( 3 3 8 ) 可以得到 鲁= 一曙( n 面d h = _ g ( 叫枷v ( 班 ( 3 3 1 0 ) 对f 关于t 进行微分得 警= 啦( 圳( 哪叫州x ) 8 2 + 俐7 ( 班( m 对v r o ，x o x ，解x ( f ，) x 。其中j ( 一 ( x ) ) 起了障碍作用阻止z ( f ，x o ) 超越表面 ( x ) = 0 。当f _ 田时，x ( t ，) 接近于边界点。如果在边界上，则整个系统( 3 3 8 ) 的 迹属于边界。 3 4 障碍牛顿方法用于求解含有等式约束的q p