（运筹学与控制论专业论文）线性qvi约束的数学规划的光滑牛顿法.pdf

大连理工大学硕士学位论文 摘要 均衡约束数学规划问题可以被看作具有变分不等式或者互补约束的两层规划问题， 正是这种约束使得该类问题变得难以处理。因此，研究这类问题的最优性条件和求解算 法等问题就变得非常重要。 本文研究的是一类参数化的线性拟变分不等式为均衡约束的数学规划问题。我们将 该类问题的最优性条件巧妙地转化为非光滑方程组的形式，进而采用光滑牛顿法来求解 此方程。通过引入二阶充分性条件的概念，在适当的假设下验证了该半光滑系统的b d 一 正则性，从而保证了算法的二阶收敛速度。同时，我们给出了此算法在线性规划反问题 中的应用。最后用数值实验验证了该算法求解此类问题的有效性。 关键词：拟变分不等式；最优性条件；二阶充分性条件；b d 一正则；光滑牛顿法 线性q w 约束的数学规划的光滑牛顿法 a s m o o t h i n g n e w t o nm e t h o df o rm a t h e m a t i c a lp r o g r a m sw i t hl i n e a r q v i c o n s t r a i n t s a b s t r a c t m a t h e m a t i c a l p r o g r a m sw i t he q u i l i b r i u m c o n s t r a i n t sc a l lb ev i e w e da sb i l e v e l p r o g r a m m i n gp r o b l e m sw i t hv a r i a t i o n a li n e q u a l i t i e s o rc o m p l e m e n t a r i t yc o n s t r a i n t sw h i c h m a k es u c hp r o b l e m sd i f f i c u l tt od e a lw i 也s ot h e s t u d yo fo p t i m a l i t yc o n d i t i o n sa n d a l g o r i t h m sb e c o m e sv e r yi m p o r t a n t 。 t h i st h e s i si sd e v o t e dt ot h es t u d yo fm a t h e m a t i c a lp r o g r a m sg o v e r n e db yp a r a m e t e r d e p e n d e n tl i n e a rq u a s i - v a r i a t i o n a li n e q u a l i t i e s 强en e c e s s a r yo p t i m a l i 移c o n d i t i o n sf o rt h e o 蛳m i z a t i o np r o b l e ma r er e f o r m u l a t e da sas y s t e mo fn o n s m o o t he q u a t i o n s w ei n t r o d u c ea s m o o t h i n gn e w t o nm e t h o dt o s o l v et h ee q u a t i o n s b yg i v i n gt h es e c o n do r d e rs u f f i c i e n t c o n d i t i o n sw ep r o v et h eb d - r e g u l a r i t yo ft h es e m i s m o o t hs y s t e ma n ds ot h eq u a d r a t i c c o n v e r g e n c eo ft h es m o o t h i n gn e w t o nm e t h o du n d e rm i l da s s u m p t i o n s w eg i v e a l l a p p l i c a t i o ni nac l a s so fi n v e r s el i n e a rp r o g r a m m i n gp r o b l e m s n u m e r i c a le x p e r i m e n t sa r e r e p o r t e dt os h o wt h a tt h es m o o t h i n gn e w t o nm e t h o di se f f e c t i v ef o rs o l v i n gs u c hp r o b l e m s 。 k e yw o r d s ： q u q s ；vc i “q | o n a l i n e q u a l i t y ；o p t i m a l i t yc o n d i t i o n ；s e c o n d o r d e rs u f f i c i e n tc o n d i t i o n ；b d - r e g u t a r i t y ；s m o o t h i n gn e w t o nm e t h o d 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题霉： 垡丝型l 丝塞煎鏊堂趣型煎羞遗生塑洼一 作者签名：上j 垒一日期：j 里乒年厶月二兰日 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目： 绫性q y ! 约塞鲍数堂拯划鲍出通生塑洼一 作者签名：益：l 生 日期：丝艺年_ _ 厶月三兰- 日 导师签名：乓蓐l 魄斗年丘月坐日 大连理工大学硕士学位论文 1绪论 1 。1 研究的意义 数学规划理论作为数学的个分支，旱已应用于社会生产、生活的各个领域，其理 论研究已形成一套完整的体系，并已形成了许多独立的分支。多层规划( 尤其是二层规 划) 问题就是其中之一，它主要来源于资源控制和价格控制等问题，目前已渗透到企业 管理、交通运输和政府决策等诸多领域。对二层规划的理论研究已经历了近3 0 年的历 程，获得了许多成果，尤其是线性二层规划的理论和算法已经比较完善。 然而人们在研究时发现具有多层结构的系统在保证系统( 上层) 最优的前提下，往往 子系统( 下层) 不能保证实现最优；另一方面，由于系统的复杂性，系统成员往往并不都 是以实现最优为条件，而是达到一种双方都满意的均衡态势。诸如早期的网络设计闻遂， 用二层规划方法建模时下层问题表述成交通分配问题最优的形式，可是后来人们发现著 名的w a r d r o p 用户均衡理论用一个变分不等式的形式来表述交通分配问题更符合客观 现实。同样对于由不同的利益团体组成的多层供应链体系，n a g u m e y 运用变分不等式建 立了竞争的供应链网络均衡模型，能够研究供应链中各层成员的独立行为以及与网络成 员之间的交互影响。像这类下屡带有变分不等式或巨补约束的数学援划就称为带有均衡 约束的数学规划阉题，篱称m p e c ( m a t h e m a t i c a lp r o g r a m sw i t he q u i l i b r i u mc o n s t r a i n t s ) 问题。这类闻题可用于进行复杂的宏观和微观经济分析，例如畿够解决人工智畿、模式 识别、交通运输规划、机械结构设计、网络设计等自然科学和工程技术中的许多关键性 的问题。 但是，由于m p e c 问题约束条件是带参数的变分不等式，其可行域的结构非常复杂， 一般不具有连通性、闭性或凸性。同时，变分不等式的解通常是集值函数，即使是单值 殛数一般也不具有良好的连续性和可微性，因此这类数学规划问题与普通的数学规划问 题或二层嫂划阀题相比都要复杂得多，导致其可行域很难清楚地刻蘧，下层的变分不等 式和互补约束很难处理，得到最优性条件比较困难。圆前瓣弱闯题的理论研究主要是 将它归结为等价的互补约束优化问题，再研究互补约束优化阔题，在一些凸性与可徽性 的假设下，给磁互补约束优化问题的可行性条件、最优解的存在性条件和最优性条件等。 对予m p e c 问题还有很多值得研究的问题，比如，研究m p e c 新的等价形式以及其最优解 的存在性；研究用不同的方式处理均衡约束，提出相应的均衡约束规划问题的约束规范 性条件，及给也其最优性条件；根据对均衡约束条件的不同处理方式，提出求解相应的 线性q v i 约束的数学规划的光滑牛顿法 m p e c 问题的算法等问题。总之，研究该类问题不但具有重要的理论意义也有较大的实际 应用价值。 1 2 本文的研究背景 强前，入们在m p e c 的理论及算法研究方蘑瑟经取得了较为丰硕豹成果。饲如：l u o 等人于1 9 9 6 年在专著m a t h e m a t i c a lp r o g r a m sw i t he q u i l i b r i u mc o n s t r a i n t s ) ) 中全面介绍 了m p e c 问题的起源、研究的复杂性、主要困难，m p e c 问题的各种等价形式( 主要是等价 k k t 形式和互补形式) ，以及m p e c 闯题的最优性条件，并给出了m p e c 闯题的内点罚算 法、牛顿算法、分片逐步二次规划算法( p s q p ) 等【l l 。该著作中的很多工作都是原创性的， 被国态外很多学者视必此方面研究的奠基之律。1 9 9 8 年，f u k u s h i m a 对p s q p 算法进行了 改进，利用f b 函数将互补条件转化为半光滑方程，然后用s q p 算法求解【2 1 。同年， o u t r a t a 等人的专著( n o n s m o o t ha p p r o a c ht oo p t i m i z a t i o np r o b l e m sw i t he q u i l i b r i u m c o n s t r a i n t s ) ) 主要研究了可以利用隐规划方法处理的m p e c 问题，借助c l a r k e 广义微分的 思想、稳定性和灵敏度理论德到艘e c 闻题的最优性条件，并提崽了基于“捆绑技术 ( b u n d l et e c h n i q u e ) ”的非光滑优化方法 3 1 。另外，o u t r a t a 还研究了广义m p e c 问题，其约 束中具有广义方程，这个模型包括了带独立参数变分不等式和互补问题的数学规划，利 焉m o r d u k h o v i c h 广义积分褥到其一阶最优往条 牛网。h 。s c h e e l 和s s c h o l t e s 基于m p e c 的 分段光滑形式，研究了该问题的几种稳定点，并进行了比较，得到了互补约束数学规划 的二阶最优性条件f 5 l 。此外，f a c c h i n e i 等人研究了一类光清算法，此类算法利用光滑函 数来逼近m p e c 问题，从而得至i j m p e c i h 题的稳定点1 6 。2 0 0 4 年，p a n g 等人提出了磨光连 续方法与积极集( a c t i v es e t ) 方法，该方法的主要思想是将m p e c 问题磨光为普通的约束 优化闻题，在一定的条件下证明后者的二阶稳定点收敛子m p e c 问题的b 稳定点【7 】。 随着人们研究问题的日益深入，近年来，关于拟变分不等式( q v i ) 为均衡约束的数 学规划闻遂成为了一大磷究热点，获得了越来越多入的关注 1 ，3 嚣s - 1 0 。但对于均衡约束为 参数化q v i 的模型，得到的结果并不是很多，对其求解的有效算法更是少见。因此，即 使是对这类问题的极麓单的框架下豹研究，也是很有意义的。2 0 0 7 年，m o r d u k h o v i c h 等人在一定的假设下给出了一类参数化q v i 为约束的数学规划问题的最优雠条件，但没 有给出算法 8 1 。本文即是在此工作的基础上，具体研究了一类线性q v 为约束的数学规 划闻题的求解算法。 大连理工大学硕士学位论文 1 3 本文研究的问题 本文研究的是一类以参数化的线性q v i 为约束的数学规划问题，具体的约束表示 梵： 给定参数x r ”，求决策向量y 毫r ( x ，y ) c r ”，使得： 信( x ，y ) ，v - y ) o ，v v f ( x ，y ) ， 其中，g ：r ”妒。震拼定义为g ( x ，y ) 拳执+ 毋+ 悫，其中d 震柑”，f 疋m ， 乃r m ；f ：r ”x r 埘- - + 2 胪是一个集值映射，定义为r ( x ，y ) = z r 掰陶( x ，y ，z ) 匙 ，其 中q ：r 。x r 肿震”峥定，q ( x ，y ，z ) = 出缈+ + 彭，a 毫r 蹦“，b r “掰，c r 肌”， k r 8 。我们可以将q v i ( 1 1 ) 式表示为广义方程( g e ) 的形式： o e g ( x ，y ) + ) ( 少) ， ( 1 2 ) 其中，v ) ( 罗) 表示集合r ( x ，y ) t f f y 点的法锥。 在以上框架下，本文考虑的线性q v i 约束的数学规划问题为： = 嬲g ( x ，y m 叫( 夕) ， 了zo ，y ) + r h y ) ( 夕) ， 。7 其中，伊：r ”露柳_ r 是一个二次连续可微函数。本文正是从上述闯题的最优性条 件出发，通过化简变形将该最优性条件表达为一个非光滑方程，并采用光滑牛顿法对之 进行求解。 1 4 本文的主要内容 本文的共分七章，第一章介绍了m p e c 问题的研究意义和相关进展。第二章是本文 需要的相关预备知识。第三、四章分别给出了本文讨论的线性q v i 约束的m p e c 问题 的最优性条件和二阶充分条件。第五章采用光滑牛顿法来求解此最优性条件。第六章用 本文提出的算法求解一类具体闯题，即线性规划的反问题。最后一章汇报了相关的数值 实验结果。 大连珲工大学硕士学位论文 2 预备知识 2 1变分分析的相关知识 本节介绍变分分析的一些预备知识。 对于集值映射甲：r ”一2 胪，其图表示为g v h v = ( x ，y ) er ”r 肿jy 芒w ( x ) 。 定义2 1 设集合qcr 一在；q 是局部闭的，q 在；处的( 极限) 法锥定义为： ( ；) = v q l 孤。一；，j 毫n n ( 妒) ，j 吼- 0 ， 满足哝( 矿一功。) _ v ，当奄专。时。 定义2 2 对于集值映射￥：群- - ) 2 舻，其在点( 瓦罗) g p h t p 处的伴同导数d 甲( i ，罗) ： r 群_ 2 舻定义为： d ￥鬈，歹) 掰) = 擎r ”陬一豁) 甲t 罗) 。 ( 2 。王) 定义2 。3 称集值映射f ：震。2 矽在点f ；，歹) 彬处以模z o 是平稳的，若存在；的 邻域移，存在歹的邻域y ，满足： ，( x ) n yc f ( ；) 删x 一习，魄u 。 对于如下带有q v i 约束的数学规划闯题： 躐r a i n 。篡g ( x ) 魄此k y ) q ( 2 2 ) 葶歹o ，y ) + 强w ) ( y ) ，x ，) q 其中：式8xr 艚一r 是连续可微函数；q r 8xr 2 是非空闭集：g ：震”xr 搬_ r ”连续可 微；r ( x ，夕) = z 式”k ( x ，罗，z ) o 是闭凸值的，其中q ：r 8 x r 舶xr 搠- - + r 二次连续可 微，o c r 是闭凸集。令三：r ”r 拼r 一r “为一辅助函数，定义为： l ( x ，y ，d ) = g ( x ，y ) + p ( z ，y ) 。d ， 记p ( z ，y ) = j 3 q ( x ，y ，y ) ，r ( x ，y ) = q ( x ，y ，y ) ，则有如下的最优性条件8 】： 定理2 1 设( ；，歹) 是问题( 2 2 ) 的局部最优解，i 殴p ( x ，歹) 行满秩，令磊尺5 为下述方 程的唯一解： 三f ；，歹，矗) * o ， 设集值映射膨在点( o ，；，歹，孑) 处是平稳的，集值映射尸在点f o ，0 , i ，歹，孑) 处是平稳的，其 中，m ：r 畏5 _ 2 舻。胪。舻，定义为 坤咔幽小肌肌r 心力卜e 姚 户：r 棚r 。xr 5 2 。舻。定义为 p ( 2 ，渗) = ( x ，y ，蘑) q r i l r , y ，d ) + z = o 门材汐) 。 则存在乘子1 ，r ”和“舔r 满足： o v 爹( 硐( 三( ；，y ，硝v + ( 毋( 硐) r 鬈+ ( 硐， o - u + d e ( ，( 硐，孑) ( p ( 硐v ) 。 若映射g 和，是仿射的，集合e 和q 是多面体集，则上述两个平稳性的条件自然成立。 2 。2 非光滑分析的相关知识 在这部分中，我们回忆一些半光滑映射中非光滑分析的一些结果。 设和y 是两个有限维实向量空间，考虑映射f ：z _ y 。 定义2 4 若极限 f f x ；办) ：= l i m f ( x + t h ) - f ( x ) 存在，则称f 在x x 处沿方向h 彳是方向可微的。若，在x 处沿每个方向h x 都 是方向可微的，则称f 在x 处是方向可微的。 定义2 5 若f 在x 处是方向可微的且 f + 矗) = f ) + f ( x ；h ) + o ( 1 l h l l ) ，h e x 则称f 在x 处是f r e c h e t 可微的。 定义2 。6 设0 是j 中的一个开集，：0 j ，是开集0 上的局部l i p s e l l i 饶连续函数。 由r a d e m a c h e r 的结论我们可以知道辔在0 中是几乎处处f r e c h e t 可微的。记珑是o 中国 的f r e c h e t 可微点的集合，则在点x 0 处是b o u l i g a n d 次可微的( 记作3 嚣o ( x 1 ) ， 是指： o 嚣o ( x ) 譬 ! i m j o ( x * ) g 纯，_ x ，t l 大连理工大学硕士学位论文 在x 处的c l a r k e 广义j a c o b i a n 是吼( x ) 的凸包，即： 抛( 工) = c o n v a 嚣辔( z ) 定义2 7 设f 是局部l i p s c h i t z 连续函数，称f 在x 处为b d i e 贝x j 的，若v v a 厚f ( x ) ， y 是非奇异的。 定理2 2 如果f 在x 处为b d 一正则的，则存在x 的一个邻域k 和常数f 0 ，使得对任 意的夕k 和矿如，( y ) 都有矿是非奇异的，且妙i i 0 时，有 o + 麒) 一o ( x ) 一y ( x ) = o ( 1 l o x | | 2 l 剿称在点x o 处是强半光滑的。 大连理正大学硕士学位论文 3 最优性条件 本文以下均假设：矩阵c 行满秩。 设l ：灭”一一r 辫为一辅助函数，定义为： x ，y ，d 一d 譬f y + 玉+ e 。d 。 以下定理是定理2 1 的直接结果： 定理3 1 设( i ，歹) 是问题( 1 3 ) 的最优解，设孑r 5 是方程三( ，歹，) = 0 的唯一解。则 j 矿r 拼，磊gr 5 ，满足： 。= v p e i ，尹，+ ；霉 + 。b ：写，藉 0e - 酉+ d + 砹( 移，孑) ( 何) ， 其中，万= 瓜+ ( b + c ) 罗+ r 。 假设1 ：一万+ 孑 0 。 现在，记7 = ，l 谚= o ) ，歹表示7 的补集。 设8 为参数，f i s c h e r b u r m e i s t e r 函数丸：r 2 一r 表示为： 戎( 岛彩= a + b - - , a 2 + b 2 + c 2 易知，磊( 岛妨= o 令露o ，参o ，a b = 0 。 定理3 。2 在假设l 成立的条件下，最优性条件( 3 1 ) 可以等价地表示为 ，i ，箩，d ，耵，万) = 0 ， 其中，f ( x ，y ，d ，1 ，“) = v t t 罗，+ ；： + 。雪：；“ ，四x + 黟十是+ e 7 d c o ( d , ，- r 1 ) 证明：由伴同导数的定义， c o ( d , ，- t l ) 磊o ，一) ) ，+ 唬( o ，r ，) u ， 唬( o ，或) ( 西) 。+ 唬( o ，r l ) u ， ( 3 。1 ) o 一霸+ d k ( 万，孑) ( 研) 营( 荔，领) ( 万，露j 铮( 玩，一( c 可) ，) 仨二n 扎( j 7 ：，孑) ，v i = i ，s 磊磊掣嚣芸嚣i ： l 玩o ，t o ，粥= 0 ， 且芬= 0 ，巧= 0 ， l 且玩= o ，( 何) ，= 0 ， v i 絮1 ，s f 甄( 以，- r h ) 嚣0 ， i , o ( o ，一彬) ( ) ，+ 磊( o ，协) 吩= 0 ， l o _ o 大连璞工大学硕士学位论文 4 二阶充分性条件 记 郇烘小h 一袭掣咖叫 羹| j 易知，是半光滑的，置对任意方程g x ，y ，d ) - 0 的解( x ，y ，d ) 擐震”xr 埘xr ，对任意 的( 缸，a y ，a d ) r ”r 肌r ，有其方向导数为： d k 州；蚺删_ 弩搿一 其审，厂：r 橼+ 珑s r s 定义为： ，( 敏，缈，麒) = | i f 五( 缸，缈， j 矗( 觚，缈， i 哆若哆= o ，( 血+ ( b + c ) y + r ) ， o ，( 出+ ( b + c ) y + 茁b = o ， | m 流 哆( 一a a r 一( 雪+ c ) 缈) 0若d i = o ，( 叙+ ( 召+ c ) y + 茁) ，娑o 定义4 。1 设( i ，歹) 是阙题( 1 3 ) 的可行解，存在歹灭册，露r 5 ，满足( 3 。1 ) 式且 ( 何) ，o ，蟛o ，v f f i z = 祝= o ， ( 4 1 ) 我能称在( 舅，罗) 处二阶充分性条件戒立，若 w ，v 2 9 ( i ，罗) w o ，v wq ( 舅，歹) ，w o ， ( 4 2 ) 其中，令l q 表示投影，集合 q ( i ，夕) 一w = ( 缸，缈) 盖”尺”i v 妒( i ，歹) rw _ o 0 疆。矿 ( 触，匈，硝) 爱”震搬爻g - ，y ，, l a x ，每，酗) = o ； 定理4 1 若在( i ，y ) 点处二阶充分性条件成立，则该点处的二阶增长条件成立。 证明：用反证法。假设( i ，y ) 点处二阶增长条件不成立，则存在可行序列 ( 了8 j ”，) ， 满足 妒( 茗”，罗”) 伊( i ，歹) + d ( ) ， 线性q w 约束的数学规划的光滑牛顿法 其中厶= l l ( 一i ，y “一罗，d ”一孑) l ，名( 毽，鬈，蝣) = ( ，一舅，y ”一罗，d ”一孑) 。不妨设 ( 群，形，蝣) 岭( 稼，乃，) o 。 令a ( x , y ，d ，矿，石) = 妒( x ，y ) + ( f ，d x + f y + h + c 7 d ) + ( 玎，a 工+ ( b + c ) y + 彭) 一( c 可，矗) ， 则v 秽，( 舅，罗，孑，歹，器) = o 于是得到如下三个泰勒展式： 妒( x ny ”) = 伊( i ，歹) + 乙v 9 ( 芽，歹) r ( 蝣，彬) + d ( ) ， ( 4 3 ) g ( x “，y “，d ”) = g ( i ，歹，孑) + g ( 只罗，孑；毽，彬，弼) + d ( o ) ， ( 4 4 ) a ( 矿，j ，”，歹，嚣) 一a ( 譬，罗，磊，瓦石) = 露群，影) ，v 2 伊( 譬，罗) ( 群，形) + p ( ) ( 4 5 ) 令以一a 。，由( 4 3 ) ，( 4 4 ) 两式知， v 够( 耍，萝) 7 ( 壤，) s o ， g + ( i ，歹，孑；壤，岛，) 一o 故( 致，) q ( i ，歹) ，且存在 o 满足 ( 砖，砖) 7v 2 伊( 瓦罗) ( 壤，) 2 岁 扶丽( 4 5 ) 式右端当嚣充分大以焉， 委( 弼，够) 7 v 2 尹( 更，箩) ( 磁，彬) + 。( 碍) 碍 ( 4 6 ) 同时，由( 3 王) ，( 4 。王) 和 ( 翼“，罗抖，) 的可行性知，当羟充分大以恁， ( 彳群+ ( 嚣+ c ) 彤) ，= o ，( ) ，= o ，v f f | z 0 ，玩= o ， ( 弼) ，= o ，霹= o ，v f f l 弓= 0 ，谚 - 0 ，虿o ，v f f | 乏= o ，玩= o 所以得到 ( 万，么群+ ( b 十c ) 彬) o ，( 何，砑) o ， 且 a ( x ”，罗”，d ”，f ，蟊) 一a ( i ，罗，孑，矿，荔) = 驴( 羔”，y ”) 一驴孑，罗) 一1 2 _ 大连理工大学硕士学位论文 这与( 4 6 ) 式矛盾。 + 乙( 订，a h 7 + ( b + c ) 彬) 一乙( 何，蝣) d ( 碍) 一1 3 一 口 大连理工大学硕士学位论文 5 光滑牛顿法 本章节，我们引入光滑牛顿法来求解定理3 2 中的非光滑方程f ( x ，y ，d ，v ，“) = 0 5 1b d - 正则性 对于矩阵m ，用m ，表示所有指标在集合，中的行所构成的子矩阵。若是一个向 量，则对应地可简记为a j 。 矩阵既南卜秩。 定理5 1 设，( i ，歹，孑，矿，f i - ) = 0 ，若假设1 ，2 成立，且二阶充分性条件成立，则f 在 ( i ，歹，孑，矿，订) 是b i ) 一正则的。 证明：不妨设7 = 1 ，- ，j - r + l ，s ) 。 对任意的日钆，( i ，罗，孑，歹，历) 均可以表示为 其中， h = v 2 伊( i ，歹) 【df 】 蛩 毋 。阴d t c r 0 铲0 酽带 肚一姗( - + 南卜卅， 胀斗南 ， 日3 = 纰( 巧) 么刀+ c 】， 日4 = 一击昭( ( c 矿) ，) ， h 5 - - a i q g 嫜f + 厨、c ， 1j c ，而 “o o 矿 b p。l 线性q 约束的数学规划的光滑牛顿法 嚣s = 搬f 豸一再) ， 占f = 2 i 了， 镑1 o ，2 ，7 ， pf = 2 ，7 ， 钙1 o ，2 i e j 一 若胃( 缸，a y ，m ，a v ，a u ) = 0 ，则可以得到： v 坝撕料瞄心：缸卜 d h x + f a y + c 7 h d = 0 ， 4 敏+ ( 嚣+ c ) 7 缈= 0 ， ( 5 ，1 ) ( 从) 了= 俄 _ 缸+ ( 嚣+ c ) 缈 ，一( ) ，彭( 础) ，一( 弓+ 厨) ( c 加) ，+ ( 玩一厩) ( 触) ，= o ， v i = l ，善 在( 5 1 ) 的第一式等式两边同时左乘( 缸r ，缈7 ) ，得 ( 缸f ，缈r ) v 2 伊( t 歹) ( 箸) + 加f ( 。缸+ f 缈) + 材f ( 么缸+ ( 嚣+ c ) 缈) = 。 囊假设1 和等式f f 夏，萝，孑，矿，露 = o ，知 乃= 0 ，( 汀) 歹= 0 。 又由( 5 1 ) 知， a 缸+ ( 8 + c ) a y j 7 = o ，( c 1 ，) ；= o ，( “) 了= o ( 5 2 所以有 如r ( d a x + f a y ) = ( c a v ) r a d = o ，a u r 么缸+ ( 暑+ c ) 缈) = o 。 褥虽 矿( 移缸+ f 缈) = 西) ra d = o ，f i - r ( 叠敏+ ( 雪+ c ) 缈) = o 。 因为v 妒( i ，罗) 7 ( 缸，缈) = 一矿7 ( d a x + f a y ) - 万r ( 彳缸+ ( b + c ) 缈) 兰o ，且 一1 6 大连理工大学硕士学位论文 d b x + f a y + c 7 耐 ld a x + f a y + c 7 a dl g ( i ，歹，孑；缸，每，d ) = l 乃( 缸，a y ，硝) i - - i 一彳缸一( b + c ) 缈 7l = o ， l 易( 缸，缈，荫) j l ( 砸) 了j ；：(otm a t 艘 = o 户( 占，x ，y ，d ，1 ，“) = v 9 c 薯y ，+ ； + 。召：三丁“ 眈+ f y + h + c 7 d 龙( 碣，- r 1 1 ) 纯( 反，- r 1 , ) 欢( o ，一名) ( c v ) ，+ 疙( o ，r l 。) 均 ； 纯( o ，一以) ( 西) 。+ 九( o ，r z , ) u ， 令 zz(z；，c，y，d，、，z，)=，i；(。；，。，；，d，、，。，)， 显然e ( 占，z ，y ，d ，u “) = 0 f ( x ，y ，d ，v ，“) = 0 光滑牛顿法就是求解光滑方程e ( 8 ，x ，y ，d ，v ，材) = 0 的方法，这里我们采用函数 西( z ) = 忙( 占，z ，y ，d ，v ，材) 1 1 2 进行线搜索，其中z = ( g ，x ，y ，d ，1 ，“) 。令万 o ，( o ，l l 满足 一1 7 一 线性q v x 约束的数学规划的光滑牛顿法 i f ( 辔( ) 一辔( z 嘲j ) 2 万( 1 一彦) ( ) 且m ( ) 是严格单调递减的，故 垂( ：。) 趋于0 。所以 z 的任何聚点收敛到方程 e ( z ) = 0 的解。 n 定理5 3 若算法5 1 生成的窿列 三 收敛到芑( z ) = o 的解2 且f 在点z 处是b d 芷则 的。则 j f 2 k + l - - z * 8 = d 咿o n l = 纱) 2 ) o 大连理工大学硕士学位论文 证明：对于充分接近z 的矿，有u o e ( z ) 是非奇异的。因为f 在z 处是强半光滑的， 故由强半光滑的定义，对充分接近z 的z ，有： 畛+ 业。训= 忖+ u - 1 卜( z 。) + 酢刁- - z * 8 = d ( 0 e ( z 女- e ( z ) 一u ( 2 i z ) l l + 吼f ；j ) = o ( i j z - z | f 2 ) + o ( ( z 。) ) = d ( i l z 女一z 8 2 ) + d ( ( e ( z 。) 一e ( z ) ) 2 ) = d ( 畛o | 1 2 ) 注意到对充分接近z 的三。， ( z i + 位。) = o ( i j z t + 业一z 1 1 2 ) = d ( 畛1 1 4 ) = d ( ( z 僻 所以有当j j 充分大以后，z “l - 夕+ z 。所以有 z k + l - - z * 忙d 肛o i | 2 ) 第一式得证。 由吼的定义，而且当| i j0 0 时_ z ，所以当七充分大以后 幺= 细( ) 同时当k 充分大以后，由于z “1 = z + 业，所以有 占“1 = 占。+ a 6 = 晚；= z 洳( z 。) 因此，当尼充分大以后，有 ! 璁爵咆端硎! 璁衙2 舰赢寿印1 ) 因此 l = p 时) 2 ) 大连理工大学硕士学位论文 6 线性规划反问题中的应用 本章给出本文所提出的算法的一个应用举例，即求解一类线性规划的反问题。 6 1 问题描述 考虑如下形式的线性规划问题 l p ( c 6 ) = 名三 ( 6 1 ) 其中c r ”，彳g n x n ，b r ”，且么行满秩。 设妒q 户：= x 尺”l 出 - b ) 为l p ( c ，6 ) 的最优解，设( c 。，b 。) g n r 朋为未知参数 ( c , b ) r ”x r ”的一个估计，则此线性规划问题的反问题就是求( 岛功，使之为下述优化 问题的最优解： m i n 抓岛6 ) 一( ，叫8 2 趾x 。掣( 凹( 啪) ) 6 2 ( c , b ) r ”r ” 其中| i i i 定义为i | ( 岛功i i ：= ，f + 矿彦。 6 。2问题化简 由对偶理论知1 4 ，15 1 ，妒s o l ( l p ( c ，6 ) ) 当且仅当存在“r ”，满足： c a 丁u = 0 ，u 0 ，a x 。6 ，“7 ( 血。一b ) - - 0 a 则( 6 。2 ) 等价于如下形式： m i l l 札一圳2 + 扣一扩0 2 c - a r “= 0 s 1 材0 ，a x o - b 0 “7 ( a x o b ) = 0 令，= a x o 一6 1 ，o = a x o b o ，我们可以得到 线性q v l 约束的数学规划的光滑牛顿法 豳三l f c - c o l l 2 + 争叫2 c a7 甜= 0 s t u 0 v 0 r v = 0 进而得到具有互补约束的优化模型： 曲吾r u - c 卜如叫2 豁0 s j 。v 芝0 材r v = 0 令驴( 毛y ) = 丢1 1 a r x - ：1 1 2 + 圭血。一各。- y 1 1 2 ，则上述问题等价于： m i n 妒( x ，y ) ( 6 3 ) s j 0 x 上y 0 易知，若( ；，歹) 是问题( 6 。3 ) 的最优解，则( ；，5 ) = ( 么，；，a x 。一歹) 为阀题( 6 。2 ) 的 最优解。因此所求的反闻题转化为求解具有互补约束的优化闯题。 6 3 最优性条件 互补约束优化问题( 6 3 ) 可以视为是( 1 。3 ) 的一个特殊形式，郎g ( x ，岁) = 羔， q ( x ，y ，三) = 一z ，f ( 罗) = 群，s = m = r l 。易知，假设2 和二阶充分性条件囊然成立。 从而可以得到如下的最优性条件和算法的王阶收敛性： 定理6 1 设( ；，歹) 是问题( 6 3 ) 的最优解，且；+ 歹 o ，则存在；，云r 前，满足 f ( x ，一y ，；，丢) - - o 其中， 大连理工大学硕士学位论文 f ( x ，y ，v ，材) = a ( a r x - - c 。) 一v y a x o + 6 0 u 唬( 而，y 1 ) ； 磊矗，) 唬( o ，一) _ + 唬( o ，- y ，) u 。 ( o ，一) + 磊( o ，一) 定理6 2 设，( ；，y ，；，二) = o ，且；+ 多 o 。nf 在( x ，y 一，；，荔) 点是b d 一正则的，从而算 法5 1 具有= 阶的收敛速度。 一2 3 大连理工大学硕士学位论文 7 数值结果 本章节，我们举出算例并在m a t l a b7 。i 上运算出结果。我翻求解如下四个闻题： 问题7 1 设驴( 如y ) = ( x ，y ) 7g ( x ，j ，) + g r ( x , y ) ，其中分是随机生成的( 聊+ ，2 ) ( 聊+ ，z ) 正 定矩阵，g 是随机生成豹m + l l 维向量。设矩阵a ，b ，c ，d ，f 分别为随机生成豹s x n ， s x m ，s x m ，m x r l ，m x 肌维矩阵，而而，心分别为随机生成的m ，s 维向量。初始点亦随 机生成。 问题7 2 设妒( 而y ) = g r ( 薯少) + i l 杰o x p ( _ ) + 丢e x p ( 以) j ，其中以鼠c ，d ，g ， 鬼茁同问题7 1 。 问题? 3 设妒( 荔y ) = 三( 墨y ) rg ( 罗) + 夏害丽 喜唧( # ) + 姜哟巧) ) ，其中g 是随 机生成的( 聊+ ，z ) ( 川+ 胛) 半正定矩阵，a ，b ，c ，d ，f ，h ，暂同问题7 1 。 瘸题7 4 线性规划的反问题( 6 2 ) ，其中么是随机生成豹m x n 维矩阵，6 8 c oa x 8 分别是随 机生成的m 刀胛维向量。 在实验中，停止准烫| l 隽t 0 1 = o ( z ； 1 0 一，其它实验参数取手= o 1 ，l = 0 5 ，拶= 0 3 ， 万= 0 5 。实验结果分别参见表7 1 至表7 4 ，其中，n e 是指方程的个数。 表7 1 闯题7 1 的数值结果 t a b 7 1 n u m e r i c a lr e s u l t so fp r o b l e m7 1 线性q v l 约束的数学规划的光滑牛顿法 表了。2 漏题7 2 的数值结聚 t a b 7 2n u m e r i c a lr e s u l t so fp r o b l e m7 2 从上述实验结果中，我们可以看到：对问题7 1 至7 3 ，在相同的n e 之下，s 的值越 大，计算需要的时间越长。这是因失在求解的半光滑方程组孛，半光滑方程豹个数是扫 个，其余的方程均是可微的。方程的非光滑性是计算耗时的主要原因。在问题7 4 中，虽 然所求的方程的个数是4 m 个，与变量的维数聆无关，但是聍的增加相对予半光滑方程 的增加对闻题的计算速度影响曼大。从问题? 。4 的结采来看，本文提出的算法较 1 6 中的 算法要快很多。 大连理工大学硕士学位论文 表7 4 问题7 4 的数值结果 t a b 7 4n u m e r i c a lr e s u l t so fp r o b l e m7 4 n e nm时间( 秒) 牛顿法迭函数迭代初始残差最终残差 代次数 次数 4 02 01 00 4 5 3 1 69 1 3 8 e + 0 0 25 9 6 e 一0 0 8 4 05 01 0 0 3 7 5 081 4 6 0 0 e + 0 0 23 7 1 e 一0 0 8 8 05 02 0 2 6 8 7 53 25 3 7 2 9 1 e + 0 0 3 1 3 8 e 一0 0 7 8 01 0 02 0 6 7 6 5 65 1 1 5 4 81 5 4 e + 0 0 4 5 1 9 e 一0 1 0 1 6 01 0 0 4 03 5 4 3 7 54 0 1 0 9 52 0 2 e + 0 0 42 9 4 e 一0 0 7 1 6 0 1 5 04 03 5 4 2 1 63 6 6 0 85 5 4 e + 0 0 4 5 3 3 e 一0 0 6 2 4 0 1 5 06 07 8 6 4 2 1 92 5 2 8 2 0 17 5 2 e + 0 0 7 8 8 1 e 一0 0 6 2 4 0 2 0 06 01 1 6 e + 0 0 3 3 5 011 2 9 2 1 5 5 e + 0 0 86 4 1 e 一0 0 6 3 2 0 2 0 08 06 8 1 e + 0 0 3 6 0 62 6 6 6 1 3 3 2 e + 0 0 88 5 3 e 一0 0 6 2 7 大连理工大学硕士学位论文 结论 本文研究了一类参数化线性q v i 为约束的数学规划问题的最优性条件及其解法，通 过将该问题的最优性条件表示为非光滑方程组的形式，我们采用光滑牛顿法来对之进行 求解。通过给出二阶充分性条件的概念，在适当的假设条件下得到算法的局部二阶收敛 速度。并将该算法应用于一类线性规划的反问题中去。具体得到如下结论： ( 1 ) 若假设1 成立，则问题( 1 3 ) 的最优性条件可由定理3 2 给出。 ( 2 ) 二阶充分性条件( 4 2 ) 可以推出二阶增长条件成立。 ( 3 ) 若假设1 ，2 成立，且二阶充分性条件成立，则定理3 2 中定义的半光滑函数f 在 其解处是b d 一正则的，从而得到光滑牛顿法的二阶收敛性。 大连理工大学硕士学位论文 参考文献 1 z q l u o ，j s p a n g ，a n dd r a l p h m a t h