（计算数学专业论文）一类约束序列极大极小问题的凝聚同伦方法.pdf

大连理工大学硕士学位论文 摘要 无约束和约束的序列极大极小问题是一类常见的、重要的不可微优化问题。由于这 类问题结构上的非光滑性和非凸性，无论是理论分析还是计算上都存在一定困难，至今 尚缺少有效的算法。解非光滑优化的传统方法主要有基于次梯度法的捆集法及其变体， 这类方法是基于非光滑凸情形建立起来的，对非凸问题可能收敛性较差。p o l a k 等人曾 做过一些研究，他们主要讨论了带极大极小约束的优化问题，建立了它和一种光滑约束 规划问题的等价关系。然而，这种转化以引入若干额外变量为代价。 刘国新在博士论文【1 】中讨论了更一般的无约束和约束序列极大极小问题，他构造了 求解无约束序列极大极小问题的凝聚同伦方法和约束序列极大极小问题的凝聚同伦内 点法：在适度的假设条件之下，证明了同伦路径是存在的、有界的和收敛的。僵文【1 】 没有设计算法及数值实验来验证此方法是否有效。 本文在文【1 】的基础上，深入讨论了约束序列极大极小问题的凝聚同伦方法。文【1 】 基于弱法锥条件利用凝聚组合同伦内点法从理论上讨论了约束序列极大极小这类非光 滑非凸问题广义点的存在性。考虑到实际应用中验证弱法锥条件通常比较困难，本文在 【1 】的基础上，进一步探讨了文【1 】中假设条件的验证方式，设计了凝聚同伦内点法的具 体实现算法，给出了一类满足文【1 条件的约束序列极大极小问题。同时，本文分析了 e p o l a r k 解这类问题的光滑约束优化算法( 详见文 2 】) ，并将它与凝聚同伦算法作了对 比。最后的具体数值例子表明凝聚同伦算法可以解决某些不满足e p o l a r k 光滑约束优化 算法假设条件的问题，同时对于约束中函数g 。个数较多的问题，要比等价光滑化算法快， 这说明凝聚组合同伦内点法对于序列极大极小问题是行之有效的。 关键词：组合同伦；凝聚函数；m a x m i n 约束；非光滑非凸优化 一类约柬序列极大极小问题的凝聚同伦方法 t h ef o r m a tc r i t e r i o no f m a s t e r sd e g r e ep a p e ro f d u t a b s t r a c t s e q u e n t i a lm a x - m i no p t i m i z a t i o np r o b l e mi sat y p i c a lk i n do fn o n c o n v e x ，n o n s m o o t h p r o g r a m m i n g 1 1 1 e ya r i s ei nt h ed e s i g no fe l e c t r o n i cc i r c u i t s ，i nt h ed e s i g no fp a t hf o rr o b o t s i nt h ep r e s e n c eo fo b s t a c l e sa n dv l s ic i r c u i t s ，e i 【c t oo u rk n o w l e d g e ，t h el i t e r a t u r ed e a l i n g w i t ht h i sp r o b l e mi sr e l a t i v e l ys m a l l t h em a i nt h e o r yr e s u ri so ni t sq u a s i - d i f f e r e n t i a lt h e o r y a n dt h em a i na l g o r i t h mi st h a tg i v e nb ye p o l a ke ta 1 t h e yc h a n g e dt h ep r o b l e mt oak i n do f s m o o t hp r o g r a m m i n g t h ea d v a n t a g eo ft h e i rm e t h o di st h a ti tc a nu t i l i z ee x i s t i n gs o f t w a r e f o rs o l v i n gs m o o t ho p t i m i z a t i o na n d , t h ed i s a d v a n t a g ei st h a ti tn e e d st oi n t r o d u c em a n y a u x i l i a r yv a r i a b l e s g u o x i nl i uc o n s t r u c t e da na g g r e g a t eh o m o t o p ym e t h o df o ru s m m pa sw e l la sa n a g g r e g a t eh o m o m p yi n t e r i o rp o i mm e t h o df o rc s m m p i nh i sp a p e r a g g r e g a t eh o m o t o p y m e t h o df o r s o l v i n gs e q u e n t i a l m a x m i n p r o b l e m s ， c o m p l i m e n t a r i l y p r o b l e ma n d v a r i a t i o n a li n e q u a l i t i e s ”u n d e rm i l da s s u m p t i o n s ，e x i s t e n c ea n dc o n v e r g e n c eo ft h es m o o t h p a t ht ot h es o l u t i o no fg e n e r a l i z e dk - 1 0 ts y s t e mi sp r o v e d h o w e v 盯h ed i d n tg i v e n u m e r i c a le x p e r i m e n tt os u p p o r tt h ev a l i d i t yo f m e t h o d s b a s e do nt h ew e a kn o r m a lc o n ec o n d i t i o n , a r t i c l e 【1 】p r o v e dt h ee x i s t e n c eo fk k - t p o i n to f c o n s t r a i ns e q u e n t i a lm a x - m i np r o b l e m s c o n s i d e r i n gt h ed i f f i c u l t i e so f v a l i d a t i n gt h i s c o n d i t i o n , t h i sp a p e rd i s c u s s e st h ec o n v e n i e n tw a yt ov a l i d a t et h ew e a kn o r m a lc o n ec o n d i t i o n , a n dd e s i g n sa r i t h m e t i c m e a n w h i l e ，t h i sp a p e ra n a l y z e st h em e t h o di n 【2 】t oe o m p u r ew i t h a g g r e g a t eh o m o t o p ym e t h o d s t h e l a s tn u m e r i c a l e x p e r i m e n t s h o w st h a t a g g r e g a t e h o m o t o p ym e t h o dc a ns o l v ep r o b l e m sw h i c hd o n ts a t i s f yc o n d i t i o n si nf 2 】，i fn u m b e r so f c h o s ef u n c t i o na r el a r g e ，a g g r e g a t eh o m o t o p ym e t h o di sf a s t e rt h a ns m o o t h i n gm e t h o di n 【2 】， t h i ss u p p o r tt h ev a l i d i t yo f a g g r e g a t eh o m o t o p ym e t h o d s k e yw o r d s ：h o m o t o p ym e t h o d ；a g g r e g a t ef u n c t i o n ；m a x - m i nc o n s t r a i n t s ；n o n c o n v e x i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：瑙l 幻a 习 日期：丝望垒塑三d 日 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位 论文版权使用规定”，同意大连理工大学保留并向国家有关部门或机构送 交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理 工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也 可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名：丝二签2 盈重 导师签名：霎! 睦 翠d 月出 大连理工大学硕士学位论文 1绪论 1 1 数学规划问题模型简介 数学规划问题是在满足约束条件下求目标函数的最优值问题。在生产实际中，有大 量的问题都可化为数学规划问题来处理。例如，关于物质运输的组织，在一定要求之下 厂房建筑的最优结构、厂址的选择、水利资源的分析等等。这些实际问题中，一般的优 化模型统称为数学规划模型。 按照数学规划模型的具体特征，可以将数学规划分为： 线性规划模型( 目标函数和约束条件都是线性函数的优化问题) ； 非线性规划模型( 目标函数或者约束条件是非线性的函数) ； 整数规划( 决策变量是整数值得规划问题) ； 多目标规划( 具有多个目标函数的规划问题) ； 目标规划( 具有不同优先级的目标和偏差的规划问题) ； 动态规划( 求解多阶段决策问题的最优化方法) 。 数学规划问题的基本形式为： m i n ( m a x ) 户( 贾) 砒 召( 贾) ( ) o 其中贾为决策变量向量，户为目标函数( 单目标规划只有一个函数，多目标规划可 以理解为一个向量函数的最优化问题) ，6 ( 贾) ( ) o 为约束条件，记 d = 牙l g ( 牙) 茎( ) o 为可行集，因此规划的本质就是在可行集中选择使得目标最优的点 若d = r ”，则该问题为无条件约束问题。 本文主要研究如下形式的数学规划问题 m l n 删2 髅跳踹。感姐w o ) ) ) 8 g ( 功2 学癌躐- - 。m 。i n 缸w ( 劝) ) o 虬1 ) 其中x e r ”，厶。( 芏) 是连续可微函数。 对于上述序列极大极小问题，当厶。( x ) 的下标的个数为m 时，称( 1 1 。1 ) 为带 极大极小约束的m 层序列极大极小问题。 一类约束序列极大极小问题的凝聚同伦方法 本文进一步讨论求解问题( 1 1 1 ) 的凝聚组合同伦内点法， 论m = 2 的情形，即 血n 俐。懋勰姊) 8 t g ( 力= m a x 。r a i ，n n g , ：( x ) ) o 其中 ，岛于中连续可微。 所有方法和结论对任意m 2 2 均适用。 1 2 同伦方法及同伦内点法简述 但为论述简洁，只讨 ( 1 1 2 ) 在非线性分析中，同伦方法( 或称连续延拓法) 是证明解的存在性定理的经典方法。 同伦方法的思想简单：为推断所研究问题解的存在性，先选择与之相似的适当问题，称 为同伦映射，当参数取适当值时，同伦映射的解即为所研究问题的解确切地，视同伦 映射为含参数方程，当解为该曲线上一点，追踪该曲线，可以得到所需解上述论述表 明，同伦算法是解的存在性的一种构造性方法进一步，通过对同伦映射的解曲线的跟 踪，则可实际求出问题的解因而，同伦算法实际给出求非线性方程组的一种算法一路径 跟踪算法 同伦本身是拓扑学中的一个概念，自从1 9 7 6 年，k e l l o g g ，l i 和y o r k e 利用微分拓 扑工具解决了同伦算法的全局收敛性问题【3 】，并用之给出了b r o u w e r 不动点定理的构造 性证明，于是引起了人们对同伦方法的重新研究接着s r n a l e 4 】发表了全局n e w t o n 法的 文章，c h o w ，m a l l e t - p a r e t 和y o r k e 利用他们构造的同伦给出了一系列重要定理的构造 性证明【5 ，同时给出了可用的算法，此后同伦算法的研究蓬勃发展，几十年来，人们成 功地把它用于经济学、电子线路设计、自动控制、计算机辅助设计和制造等许多领域中， 成为引人注目的算法。 同伦算法的基本思想是： 为求解非线性方程组f ( x ) = 0 ，其中f ：q c r “一r “是光滑映射，构造一个带参数f 的映射日( x ，f ) ：q ( 0 ，l 】一r “，称为同伦映射，使之满足 h ( x ，1 ) = g ( x ) ，h ( x ，o ) = f ( 曲 而方程组g ( 石) = 0 易于求解。若日构造的合适，在一定的条件下，同伦方程 h ( x ，) = 0 可以确定一条从0 妒，i ) o t o ) 是g o ) = o 的解) 出发，趋向于超平面t = 0 的光滑 大连理工大学硕士学位论文 曲线，称为同伦路径，该曲线另一端的任一极限点的工的分量x 是f ( x ) = o 在q 中的解。 从而，我们可以通过数值跟踪该曲线得到f ( x ) = 0 的解。 同伦映射形式 不动点同伦：h ( x ，p ) = ( 1 - i z ) f ( x ) + i z ( x - x o ) 牛顿同伦：h ( x ，) = ，( 功一，( 妒) 线性同伦：h ( x ，) = ( 1 - i z ) f ( x ) + g g ( x ) 自扶k a m a r k a r 内点法发表之后，入们在研究内点法的同时又重新研究同伦内点法。 近十几年来，众多的研究者吸收和发扬了障碍函数法、中心路径方法的优点，特别是融 入了具有整体收敛性的同伦方法的思想，使得求解的各种内点路径跟踪算法或同伦内点 法层出不穷。 1 9 8 6 年，g i l le ta l 首先证明了算法本质上等价于对数障碍函数法，并给出一种 实用的内点法，把内点法与利用障碍函数的路径跟踪算法联系在一起，出现了所谓的内 路径跟踪方法( 内点同伦算法) ，由于极值问题没有同伦不变性，因此同伦算法一般用 于其一阶必要条件求解。无约束优化闯题可以直接转化成方程组求解，但对于约束优化 问题就困难了，因为约束优化问题的一阶必要条件既包括等式又有不等式。 考虑如下非线性规划问题 m i nf ( 工) s t g ( 工) 0 ( 1 2 1 ) q = x 彤：g ( z ) o 为可行域。q o = z 肜：g ( 刁 0 局部l i p s c h i t z 的。如果存在某个 o 使得 l 厂( ) ，) 一s ( z ) i - “i i y z 0 ，砂，：b ( x ，s ) ( 2 ) 函数f ：r ”斗r 于x f 沿着方向1 ，仨r ”的方向导数定义为 。，( 础) ：船业掣 ( 3 ) 函数，( x ) 于x 处是关于常数k o 局部l i p s c h i t z 的，则厂：r ”斗r 于 x r ”沿着方向v r “的方向导数定义为 作，v ) 地恶j 。世竿型p w + u i ( 4 ) 若函数i ( x ) 于x 肜处是关于常数，c o 局部l i p s c h i t z 的，称函数，( 曲于 x 掣处是正贝u 的，如果所有的方向r 掣，f 的方向导数厂x ，v ) 都存在，且满足 ，o ( x ，v ) = ，x ，v ) 大连理工大学硕士学位论文 ( 5 ) 正则性定义( 2 0 ) ：设9 ：d c r ”- 十r ”是光滑映射，对任意y r “，记 9 4 0 ) 2 仕d 缈( 。奶为y 在映射9 下的逆像若9 在工( o 亡d 处的j a c o b i 矩阵 掣行满秩，则称x 是映射9 的正则点。否则称工晰是9 的l 豳界点若对所有的 盘 x ( 妒一1 ( ) ，o ) 都是映射妒的正则点，则称y p 是映射咿的正则值否则y 是妒的临界 值 ( 6 ) 外法锥条件( 6 ) ：对于任意的工a q 。若q 于善的外法锥和q 不相交，即 缸+ “v 岛( x ) o ，“ o ，吻 o , i a ( x ) ，j a d d , ( x ) n q = c p 则称 j j l ( x )j e i ，) j e l l ( x )，e 奶( j ) q 满足外法锥条件。 ( 7 ) 弱法锥条件( 7 ) ：存在非空闭子集q cq o ，对于任意的x e a q ，若q 于工 的外法锥和q 不相交，即 扛+ l a , b v 岛( 工) 弘 - 0 ，“ o ，峋 o ，f e 盯( 力，j z ( 功) n q = 西 l e l l ( x ) j e o j , j ) e ( j 】，叫，( o j 则称q 满足外法锥条件。 ( 8 ) 隐函数定理( 2 0 ) ：设p ：r ”r ”一r ”是光滑映射，( x ，y ) r ”x r ”满足 妒( 为力= o ，如果9 对毒的j a c o b i 矩阵彰0 ，力非奇异。则存在，y ) 的开邻域n i r ”， 2 矗”及函数x ：1 一n 2 ，使得x l v ) c 1 ，对每个方程妒( x ，y ) = 0 有唯一解 x ( y ) c 1 。 ( 9 ) s a r d 定理( 2 0 ) l 如果uc - r ”为开集，9 ：u 寸震，矿c 7 ，这里 r m a x 0 ，n p ) ，则妒的临界集的l e b e s g u e 测度为0 。 ( 1 0 ) 参数化s a r d 定理( 2 0 ) ：v c r ”，u c r ”，均为开集，9 ：v x u 哼r 9 是 c 7 映射，这里， m a x o , m - 办， 如果0 e r p 是9 的一个正则值，那么对几乎所有口v ，0 是驴( 口? ) 的一个正则值。 ( 1 1 ) 逆映像定理( 2 0 ) ：如果0 是映射9 ( 口 ) 的正则值，那么逆映射9 4 ( 4 ，) 由 有限条一维光滑流形组成。 ( 1 2 ) 一维流形分类定理( 2 0 ) ；一维带边光滑流形的每个连通分支，或者微分 同胚于单位圆周，或者微分同胚于实数区间( 0 , 1 】，【o ，1 ) 及【o ，1 】这三者之一 大连理工大学硕士学位论文 2 约束序列极大极小问题的凝聚同伦方法 2 1带n m x m in 约束序列极大极小问题综述 本文考虑如下问题： 卿 ，( 功= m - 圳a x m 洲i n ( 堋 ( 2 1 1 ) s t g ( 力= m 。，a 。xi s j n f i ：n n g , , ( x ) 0 其中兀，g , j 于彤中连续可微 q = x r “：g ( x ) = m 。a 。x r a 。i ：n 。( g - ，( x ) ) o j 为问题( 2 1 1 ) 的可行区域， q 0 2 i x r “：嚣鹏 岛( x ) o j 为问题( 2 ) 的严格可行区域，铀= f l d 。为问题 ( 2 1 1 ) 的可行区域边界。 记蜀( x ) = 姥k ( x ) ，盯( x ) = ( f ：g ( 工) = g ，( x ) ，以( x ) = ，：g 心) = g 。( x ) 问题( 2 1 1 ) 是典型的非光滑优化问题。它在工程设计 2 1 、电子线路设计 2 2 、 机器人路线设计 2 3 、热交换 2 4 和化学反应设计 2 5 、以及v l s i 电路布局设计 2 6 等领域中有广泛应用。此外，带互补约束的数学规划是它的特例。还有些规划问题，例 如，随机规划、多目标规划的一些特殊情形，都可化为这类问题，有关讨论参见 2 7 。 在文献 2 8 中有问题( 2 1 1 ) 的解存在的拟微分形式，但没有给出具体表达式， 不便于应用。而关于此问题的数值求解，至今针对问题( 2 1 1 ) 的有效的算法相对甚 少。制约这类问题的相应的算法发展的主要障碍是问题结构的非光滑性和非凸性。尽管 人们通常使用l e m a r e c h a l 捆集法的各种变体处理这种类型的问题，例如，割平面法、 捆集信赖域法等。捆集法对非凸问题不但表现出相当差的收敛性，而且他们不能利用问 题具体的组合结构。 下面给出e p o l a k 针对m a x m i n 约束的优化问题的光滑约束优化算法。 2 2e p o l a k 的光滑约束优化算法 e p o l a k 等人利用如下简单的事实将原非光滑问题变形为一个光滑问题( 详见文 【2 】) ：实数集 乃 二包含一个非正元素，当且仅当它的凸包 窆幽：艺p k l ，p ，巩1 s j a 一类约束序列极x - 极d , 问题的凝聚同伦方法 包含一个非正元素：也就是说，实数集 乃) 2 。包含一个非正元素，当且仅当存在一 fn、p? 个向量r 4 ，i z e r 皇 一e r 竹i 肼7 - - 1 ，“。o ，1 ，b ，使得e l , 7 y ，- 0 。另一方面， l ，t l j ，- i x f 满足嬲 岛( x ) ) s o ，当且仅当实数集 岛( 瑚：包含一个非正元素。因而，x r ” 满足勰 岛( 工) o ，当且仅当，存在一个向量以。使得j - i 以岛( 刁o 口从而闯 题( 2 1 2 ) 可转化成光滑约束规划问题： 1 ( ；忠似) g ( 工) ：孙岛( x ) - o , z , 。胚融 2 卫1 对每p l i _ k ，记一( z ) = 姥岛( x ) ，乒( x ) - l 0 ，f ( x , i z ) 关于x 彤是，次连续可微函数，且 v , f ( x ，p ) = 谚( 工，乒) 九( 工，弘) 砀乞( 工) 其中 玩( x ，p ) = ，气( 工，芦) = ( c ) 对任给的p o ，f ( x ，) 关于x 掣的h e s s i a n 矩阵有如下形式： 大连理工大学硕士学位论文 v ? f 【毛p ) = 一吉l 善西( 毛p ) ；九( p ) ( d jl 善反( 五) ；( 五芦) 百乃【工j 1r 。 7 厂_ + 4 ( 并，p ) 乃( x ，i ) v 2 ( x ) 一告主6 肛，_ u ) 窆九( 训) ( x ) 7 瓢( x ) + 云喜t ( 毛p ) 妻九( b p ) 、巧( x ) 7 妻九( 五p ) 1 ( 功 利用修正的二次凝聚函数，文【1 】构造如下凝聚同伦方程： m 山卟叫h r 篙茹荔譬孑“卜p 卜 晓s 其中w = 似力，w 0 弋- - 。0 ，y 。) eq o 砖+ ，y e 砖，和9 ( o ，l 】是事先给定。令日( 破扩，) 的 零点集为 吲( o ) = ( w ，p ) q 趟( o ，l 】：胃( w p ) = o 当= 1 时，凝聚同伦方程( 2 3 2 ) 变为 x = o i ) g ( 苫，即) 一p 矿g ( 工o ，口) = o 因此，凝聚同伦方程( 2 3 2 ) 有唯一解 = w o 定理2 3 3 ( 1 ，定理3 4 4 ) 如果假设2 1 - 2 3 成立，日( w ，w 。，p ) 定义如( 2 3 2 ) ， 可选取适当小的常数8 e ( o ，1 】，则对几乎所有的扩印足+ ，0 是映射日( w ，p ) 的 正则值。从而凝聚同伦方程决定了一条起始于( w o ，1 ) 的光滑曲线ocq 。吐x ( o ，1 】， 且当p - , o + 时，f 矿的极限点集，记为r o ) c q 砖 o ) ，一定是非空的，且设( x ，y + ) 是r 中的任意点，和彰= y + p f ，j = l ，2 ，七，贝u ( x - ，并，磊) 是广义k - k - t 方程的 解，面z 为问题( 2 1 1 ) 的广义k - k - t 点。 有定理2 3 3 知，对几乎所有的矿e f t 。砖+ ，凝聚同伦方程( 2 3 2 ) 生成一条光 滑曲线r 矿，此曲线称为同伦路径，从( 矿，1 ) 出发数值跟踪r 矿直到芦专o + ，即可得到 大连理工大学硕士学位论文 3 一类约束序列极大极小问题的凝聚同伦方法 文献【1 】给出一般的约束序列极大极小问题的凝聚同伦方法。给出了同伦路径存在、 收敛的条件，即假设2 1 - 2 3 ，其中验证边界正则性条件( 假设2 23 ) 和弱法锥条件( 假 设2 3 ) 通常比较困难。本章我们讨论类特殊的序列极大极小问题，证明对这类问题 假设2 2 和2 3 成立，于是可以用凝聚同伦方法来求解，为符合这类问题模型的一些实 际问题的凝聚同伦求解提供了理论依据。 对于问题( 2 1 1 ) ，假设函数岛( x ) 是凸函数，并由所有岛( x ) 围成的约束区域内 部非空，下面证明文【1 仲的假设条件2 2 - 2 3 是成立的。 弓l 理记盎= 岛( z ) o ，l f 七，1 ，只 ，6 0 = 岛( x ) o ，l g i 七，1 j p ， 当 g , a , 0 为凸函数并且r i o o 时，假设条件2 2 和2 3 成立。 证明：由g o ( x ) 凸以及甜a ：美盎o ，x 寸v x e 弛，有： 一x ) v g 。( 算) o 则有 l e 口j，叫wi e z l ( x )；e , u a s ) 一x ) v g 。( 对2 0 ，这与( 3 1 ) 式推出的只7 7 0 ( 量一对( 力 o 矛 j e 以恤)l e 月o ) j “ 耐 盾，所以条件2 3 成立，证毕。 一类约束序列极大极小问题的凝聚同伦方法 由引理我们知道，存在这样一类特殊的序列极大极小问题( 铂x ) 凸并且分a ) 满足文【1 中给出的假设条件，于是可以用凝聚同伦方法来求解。 对问题( 2 1 1 ) ： 记q = x r ”：g ( 工) o ，q o = x r ”：g ( x ) 田 记壶= 岛( 工) o ，1 f 七，l ，b ， = 岛( x ) o ，l i k ，1 _ ，s 只) 记( p ) = 扛r “：g ( 薯舡) o ，瓯( 舢) 。= x ：g 朗) o 假设3 1 q 是有界连通集，q o 是非空的 假设3 2 岛( x ) 为凸函数并且6 0 g 3 1 一阶必要条件 定理3 1 1 在假设3 1 3 2 之下，若，( 茸) 于x q 处在q 之上达到局部极小值， 则存在q o 成o ， o ，v f ，o ，使下式成立。 ，岛( 工) + v 。v g y ( x ) = o l “f )j 叫( ， 蚓 e q ( ，) 以岛( x + ) - - o ， o ，- g j ( x ) o ，f = 1 2 七 ( 3 2 ) 呸= 1 ，岛- - 1 , 心= 1 t “( ，)j 叫( ，)j e 珥( i - ) 其中 咚) = 1 ，2 ，。磅：砸) = m 。i 。n ( f ，, ( x ) 以( x ) 。 _ ， 1 ，2 ， ：船( 乃( 工+ ) = ( 工) 彤( x ) 2 ， l ，2 ，。a 妇r a i n i & 小) = 岛( x ) j 称( 3 1 1 ) 为问题( 2 1 1 ) 的广义k - k - t 方程，而满足( 3 1 1 ) 的x 称为问题( 2 1 1 ) 的广义k - k - t 点。 证明：由引理和定理2 3 1 可直接导出。 3 2 二次凝聚函数 与2 3 中定义的二次凝聚函数一致，有同样的性质。 大连理工大学硕士学位论文 3 3 同伦路径的存在性和收敛性 利用二次凝聚函数，同样构造如下凝聚同伦方程： m 山) ( 1 叫h e 篙茹g 裟努“卜p 卜 s ， 其中w = ( x ，y ) ，w o = ( 妒，y o ) 甜吐，y 砖，和日( o ，1 】是事先给定。令日( 嵋w o ，p ) 的 零点集为 彬( o ) = ( w p ) q 疋( o ，1 】：日( 鸭p ) = o ) 当l = 1 时，凝聚同伦方程( 3 3 ) 变为 j ， j x 。= o l 粥( x ，0 【1 ) - l a y o g ( 妒，日) = o 因此，凝聚同伦方程( 3 3 ) 有唯一解w = w o 命题3 3 1 假设3 1 和3 2 成立，则 ( a ) 对任给的口( o ，l 】和芦( o ，1 】，有q 似) c q ( b ) 对任意的闭子集6 c q o ，存在一个p ( o ，i 】，使得壶c ( 1 ) o 证明：由引理和文献 1 中命题3 4 1 可直接导出。 命题3 3 2 若假设3 1 和3 2 成立，存在p ( 0 , 1 】使得，对任意的p ( o ，1 】，鹞( p ) 的边界是正则的，即v x a ( p ) ，有v ，g ( x ，印) 0 证明：由引理和文献 1 中命题3 4 2 可直接导出。 命题3 3 3 若假设3 1 和3 2 成立，则对任意的闭子集c 盎，存在一个口e ( o , l 】， 使得对任意的芦e ( o , 1 】，( 乒) 关于c 6 满足弱法锥条件。 证明：由引理和文献 1 中命题3 4 3 可直接导出。 定理3 3 4 如果假设3 1 和3 2 成立，墨，( 鹕p ) 定义如( 2 ，3 1 ) ，可选取适当小 的常数日( 0 , 1 】，则对几乎所有的w o 国吐，0 是映射上0 ( w ，p ) 的正则值。从而凝 聚同伦方程决定了一条起始于( w o ，1 ) 的光滑曲线r 矿c q o 吐( o ，1 】，且当u _ o + 时， f 矿的极限点集，记为r o ) c q 避 啦，一定是非空的，且设( x ，y ) 是r 中的任意 点，和善：= y 只，歹= l ，2 ，七，则( ， ? ，磊) 是广义k - k - t 方程的解，而x 为问 题( 2 1 i ) 的广义k 硌t 点。 一类约束序列极大极小问题的凝聚同伦方法 证明；由引理和文献 1 】中的定理3 4 4 可直接导出。 有定理3 3 4 知，对几乎所有的扩触足+ ，凝聚同伦方程( 3 3 ) 生成一条光滑 曲线r 矿，此曲线称为同伦路径，从( w o ，1 ) 出发数值跟踪r 一直到卢一o + ，即可得到约 束序列极大极小问题的一个广义k - k t 点。 下面利用预估校正算法进行数值跟踪同伦路径。 3 4 算法描述 凝聚同伦方程只，( w , l z ) 隐式地定义了这条光滑曲线。使用弧长参数s ，我们能参数 化该解曲线，即存在连续可微函数( w ( j ) ，p ( s ) ) ，使得 磊0 ( w ( s ) ，p ( s ) ) = o w ( o ) = _ h ，o ，p ( o ) = 1 关于参数s 微分式的第一个方程可得下面的定理。 定理3 4 1 ( 9 ) 凝聚同伦方程王0 ( w ，p ) = o 所确定的解曲线( w ( s ) ，p 0 ”满足 如下微分方程的初值问题： 日b 。山) 嘲 - 0 p ( s ) ，, i x ( 圳i = 1 w ( o ) = w op ( o ) = l ，z s ) o 并且，若有j 。- - - 0 ，使p ( s ) = o ，则工+ = x ( j ) ，y = y ( s ) 是广义k - k - t 方程的解。 根据定理，我们可以结合用预估校正法数值( 参考 2 0 ) 跟踪光滑路径r 一。 s t e p o ：初始化过程 给出初始点( ，盹) ，初始步长= o 1 ，充分小的正数占= 1 0 。，口= 0 5 ，k = o ， 记( ，段) = ( w 0 ，心) ，y o - - 1 ，心= 1 s t e p l ：计算预估方向 ( 1 1 ) 计算满足( d 亡o ，d 瓯) ( “，) 7 = o 的( ，以) 处单位切向量巩= ( ，( s ) ，p ( s ) ) ， ( 1 2 ) 若1 日。( 矿，矿) l 的符号为正，取仇；仇，不然，仇：吨 大连理工大学硕士学位论文 s t e p 2 ： ( 2 1 ) ( 2 2 ) s t e p 3 ： ( 3 1 ) ( 3 2 ) 坝估 匹程 ( w ，p 。) = ( 矿，以) + 吃仇 若( 矿，p ) 芒q 。致1 ( o ，1 】，= ，转2 。1 ，否则转s t 印3 n e w t o n 法校正 ( 矿，p ) - - ( w 。，p + ) 一d 日( w ，p + ) + 日( 矿，p ) 如果8 日( w ，p ) 8 8 ，转s t e p 3 1 ( 3 3 ) 若( 矿，芦) 仨+ x ( o ，l j ，盈= ，转2 1 ， ( 3 4 ) ( 矿”，段。) = ( 矿，旷) s t e p 4 ：中止准则 如果m g 终止计算，输出矿“，即为最优解，输出此时的m i i l 扩= m 。a x m 。i n - ，：, ，删 否贝0 ，令后= _ j + 1 ，g o t o s t e p l 注：在s t e p 3 中d 抒( w p ) + = d h ( w , ) 7 ( d 日( p ) 册( w ，_ 1 ) 7 ) - i 为d h ( x , ；t ) 的 m o o r e - p e n r o s e 逆矩阵。 下面给出算法中用到的计算公式及处理细节： 如果日，( 墨【1 ) - - - ( 1 一) v ，f ( 五舡) + p ( x x o ) = 0 则脚。叫p 碡驾一趾砖飞+ 南强卜p ， d h = x - x * - 训 赤驴互+ 寿乇一寿+ 叫 一1 9 二耋丝塞壁型堡盔堡尘塑壁塑堡塞旦丝茎丝 s = 口( i ) b ( i ，罗，乃( x ) 最= 口( f ) b ( i ，罗。( 习 最= 口( i ) z b ( i ) v ，乃( v ，乃( 刁1 蜀= 喜4 c r 骞6 g 歹妒，t 工) 害矗g 歹猡；五t x ， ，t l l i lj lj z l j 五= 4 ( f ) 6 g ，场( 功 瓦= a ( f ) 6 ( f ，j ) l o ) v ，( 玎 五= 喜口( ，) 妻6 ( ，v ；( x ) 圭j = l6 ( ) 守：石( 工) 2 ，一1l ，- ll ij 其中口( f ) ，b ( i ，_ ，) 的表达式可如下表示出来， 设 置= m i i l ( 厶( 矿) ，z ：( ) 丘( 矿) ) s ，= 喇足- z ，x ) ) 婶+ 心) ) s ：= e x p ( ( 墨尼( 矿) ) 佃+ 段) ) 甄= e x p “置一矗( ) ) ，( 日+ 以) ) 6 ( f ，1 ) = 品( 墨，+ s 2 + + & ) 则地2 ) = s ：( s t + 墨：”+ 黾) b ( i ，l 一= s 4 7 | 媾i i + s 口+ + s h ) k ( 1 ) = - 蜀+ p + 以) 。l n ( s l + s 2 + + s ) 。k ( 2 ) = 一是+ 徊以) l n ( s 2 l + + + 最 ) z 净 k ( 所) = 瓦+ ( 日+ 段) + i n ( 晶l + & 2 + + ) 设s = r a i n ( k ( 1 ) ，k ( 2 1 ，k ( m ) ) 墼坚丕塑! 兰塑丝 a l = e x p ( ( s - k ( 1 ) ) ( 日+ 以” a 2 = e x p ( ( s k ( 2 ) ) ，徊+ 肌) ) a m = e x p ( ( s k ( 研) ) ( p + 以) ) 口( 1 ) = a l ( a l + 以+ + 硎) 则口( 2 ) = a 2 ( 口1 + 口2 + + 册) 如果嘶咖r k e 竺：麓嚣掣p - o 详默：篡罱 v ；，( x ，卢) ：兰口( ，) 圭6 ( ) q 圳讪 ；| ；吲一半 叭圳劬睢酬一学 r g ( x ，p ) 。壹c ( f ) 窆d ( f ，) ( v ，2 f ( 础) = 赤”辨是+ 赤最+ 赤+ 墨 v ，2 g 似小赤牡忍+ 赤昏南+ 只 一2 1 类约束序列极大极小问题的凝聚同伦方法 v 摊小寿椭“+ 寿五一寿+ 正 v 徘盼毒躺寿q 2 一寿q 3 其中：s ，是，墨，只，互，五，e ，口( f ) ，b ( i ，j ) 表达式同上， 暑，昱，b ，只，q 1 ，q ，q ，c ( f ) d ( i ，) 表达式可同理得到。 同样，为避免在求解船，三曙。时分母秘过小导致无法进行要对g ( t p ) ，妒f ( 葺_ t ) 作 如下处理。 州w 冲h 瞧1p 唧( 掣 叫h h 防( - 学 叫h h 阡学) 姜唧( 书 叫h m h 学肛防( ( 学掣 ) = 一p b p ，一g 。c x ，+ “h 薯中 ( 墨型q 生产) 一2 2 大连理工大学硕士学位论文 一柚 芝霎c x p ( 掣) 卜f 芸 一h 1 只地j 卜半+ 只艺 l ，o p l ，q 姜唧( 一半 一舢阿盟# 1 ) 塞s - i 唧f t , 半掣 心 一只+ ( 一半h 姜唧( 半掣 卜芸 霎唧( 幽掣j t lk p = p 啦唧( - 掣 锄h 掣胁( 掣