（运筹学与控制论专业论文）非凸二阶锥规划问题的非线性重新尺度化方法.pdf

大连理工大学博士学位论文 摘要 非线性l a g r a n g e 函数是经典的l 卿g e 函数的修正形式，它关于乘子向量或约束函 数是非线性的函数，非线性重新尺度化方法是基于一类非线性l a g r a n g e i 函数建立的求解 优化问题的方法非线性重新尺度化方法是求解约束优化问题的一类重要的算法 另外，二阶锥规划问题在工程、与鲁棒优化相关的控制和金融以及组合优化等领域 都有着广泛的应用而对非凸二阶锥规划问题的数值方法的研究还不很多本论文主要 研究非凸二阶锥规划的非线性重新尺度化方法的收敛速度，所阐述的主要研究结果可概 括如下： 1 第三章主要研究了一类求解非凸二阶锥规划问题的非线性重新尺度化方法首先 分析了l 6 w n e r 算子的微分性质，借助l 6 w n e r 算子构造了一类求解非凸二阶锥规划 问题的非线性l a g r a n g e 函数并建立了相关的非线性重新尺度化方法，接着给出了 与l 6 w n e r 算子相关的实值函数所满足的条件，以保证算法的收敛性然后研究了该 类非线性l a g r a n g e 函数的微分性质，最后在适当的假设条件下证明了当算法中的子 问题精确求解时该算法的收敛速度收敛定理表明：当惩罚参数t 4 , 于某一阈值时， 基于该类函数的算法生成的原始一对偶序列是局部收敛的，且原始一对偶解的误差界 与t 成正比与非线性规划的非线性重新尺度化方法相比，我们在收敛性分析中需要 增加对非凸二阶锥规划的二阶充分性条件中的s i g m a 项的处理 2 第四章主要研究了当算法中的予问题近似求解时算法的收敛速度首先给出了 与l 6 w n e r 算子相关的实值函数所满足的一些条件，以保证非精确算法的收敛性然 后提出了求解子问题时的终止准则，证明了在使用该准则作为子问题终止条件时非 线性重新尺度化算法的收敛速度收敛定理表明：当惩罚参数t d , 于某一阈值时，基 于该类函数的对偶算法生成的原始对偶序列是局部收敛的，且原始- 对偶解的误差 界与t 成正比 3 第五章验证了文献中给出的修正的f r i s c h 函数、修正的c a r r o l l 函数、l o g s i g m o i d 函数、m e c 函数、m f c 函数均满足第三章及第四章所提出的条件，并 用基于这五个函数的非线性重新尺度化方法计算了两个文献中给出的数值例子 数值结果表明该类算法是有效的 关键词：非凸二阶锥；非线性重新尺度化方法；非线性l a g r a n g e 区i 数：l i i w n e r 算 子；非精确算法 大连理工大学博士学位论文 n o n l i n e a rr e s c a l i n gm e t h o d sf o rs o l v i n gn o n c o n v e xs e c o n d - o r d e rc o n e p r o g r a m m i n gp r o b l e m s a b s t r a c t n o n l i n e a rl a g r a n g i a n sa r ev a r i a n t so ft h ec l a s s i c a ll a g r a n g i a n ，i nw h i c ht h em u l t i p t i e r so r c o n s t r a i n tf u n c t i o n sa r ei n v o l v e di nn o n l i n e a rw a y s n o n l i n e a rr e s c a l i n gm e t h o d s ，b a s e do na c l a s so fn o n l i n e a rl a g r a n g i a n s ，a r ei m p o r t a n ti nc o n s t r a i n e do p t i m i z a t i o n m e a n w h i l e ，s e c o n do r d e rc o n ep r o g r a m m i n gp r o b l e m sh a v ef o u n dw i d ea p p l i c a t i o n si ne n g i n e e r i n g ，c o n t r o la n d f i n a n c et or o b u s to p t i m i z a t i o na n dc o m b i n a t o r i a lo p t i m i z a t i o n h o w e v e r , t h es t u d yo fn u m e r i c a lm e t h o d sf o rn o n c o n v e xs e c o n do r d e rc o n ep r o g r a m m i n gi sn o te n o u g h b a s e do nt h i so b s e r v a t i o n ，t h i sd i s s e r t a t i o nf o c u s e so nt h es t u d yo ft h er a t eo fc o n v e r g e n c eo f n o n l i n e a rr e s c a l i n gm e t h o d sf o rn o n c o n v e xs e c o n do r d e rc o n ep r o g r a m m i n g t h em a i nr e s u l t s o b t a i n e di i lt h i sd i s s e r t a t i o nm a yb es u m m a r i z e da sf o l l o w s ： 1 c h a p t e r3s t u d i e sn o n l i n e a rr e s c a l i n gm e t h o d sf o rs o l v i n gn o n c o n v e xs e c o n do r d e r c o n e p r o g r a m m i n gp r o b l e m s f i r s t l y , w ed i s c u s st h ed i f f e r e n t i a lp r o p e r t i e so fl s w n e ro p e r a t o r a n dp r o p o s ec o n d i t i o n so nt h er e a l v a l u e df u n c t i o ni n v o l v e di nt h el o w n e ro p e r a t o rt o g u a r a n t e et h ec o n v e r g e n c eo ft h en o n l i n e a rr e s c a l i n gm e t h o d s s e c o n d l y , w es t u d yt h e p r o p e r t i e so ft h ep r o p o s e dc l a s so fn o n l i n e a rl a g r a n g i a n s f i n a l l y , u n d e r s u i t a b l ec o n d i - t i o n s ，w ep r o v et h er a t eo fc o n v e r g e n c eo ft h ep r o p o s e dm e t h o d sw h e nt h ei n n e rp r o b l e m s a r ee x a c t l ys o l v e d t h ec o n v e r g e n c et h e o r e ms h o w st h a tt h ea l g o r i t h mb a s e do na n yo f t h ep r o p o s e dn o n l i n e a rl a g r a n g i a n si nt h ec l a s si sl o c a l l yc o n v e r g e n tw h e nt h ep e n a l t y p a r a m e t e rti sl e s st h a nat h r e s h o l da n d t h ee r r o rb o u n do fp f i m a l d u a ls o l u t i o n si sp r o p o r t i o n a lt ot c o m p a r e dt ot h ec o n v e r g e n c ea n a l y s i si nn o n l i n e a rr e s c a l i n gm e t h o d sf o r n o n l i n e a rp r o g r a m m i n g ，w eh a v et oo v e r c o m et h ed i f f h c u l t yc a u s e db yt h es i g m at e r mi n t h es e c o n do r d e rs u f f i c i e n tc o n d i t i o nf o rn o n c o n v e xs e c o n do r d e rc o n ep r o g r a m m i n g 2 c h a p t e r4d i s c u s s e st h er a t eo fc o n v e r g e n c eo ft h ea l g o r i t h m sw h e nt h ei n n e rp r o b l e m s a r ea p p r o x i m a t e l ys o l v e d f i r s t l y , w eg i v ec o n d i t i o n so nt h er e a l v a l u e df u n c t i o ni n v o l v e d i nt h el 6 w n e ro p e r a t o rt og u a r a n t e et h ec o n v e r g e n c eo ft h ei n e x a c ta l g o r i t h m s e c o n d l y , w ep r o p o s eas t o pc r i t e r i o nf o ra l la p p r o x i m a t es o l u t i o no ft h ei n n e rp r o b l e m f i n a l l y , w e 非凸二阶锥规划问题的非线性重新尺度化方法 e s t a b l i s ht h ec o n v e r g e n c et h e o r e mo ft h en o n l i n e a rr e s c a l i n gm e t h o dw h e nt h i sc r i t e r i o n i su s e d t h ec o n v e r g e n c et h e o r e ms h o w st h a tt h ea l g o r i t h mb a s e do na n yo ft h ep r o p o s e d n o n l i n e a rl a g r a n g i a n si nt h ec l a s si sl o c a l l yc o n v e r g e n tw h e nt h ep e n a l t yp a r a m e t e rti s l e s st h a nat h r e s h o l da n dt h ee r r o rb o u n do fp r i m a l d u a ls o l u t i o n si sp r o p o r t i o n a lt o 亡 3 i nc h a p t e r5w ev e r i f yt h a tm o d i f i e df r i s c h sf u n c t i o n ，m o d i f i e dc a r r o l l sf u n c t i o n ，l o g s i g m o i df u n c t i o n ，m e cf u n c t i o na n dm f c f u n c t i o na l ls a t i s f yt h ec o n d i t i o n sp r o p o s e d i nc h a p t e r3a n dc h a p t e r4 b a s eo nt h e s ef u n c t i o n s ，w ed e v e l o pn o n l i n e a rr e s c a l i n g m e t h o d sa n de a r l yo u tt h en u m e f i c me x p e r i m e n t s t h ee x p e r i m e n tr e s u l t ss h o wt h a tt h e m e t h o d sa l ep r a c t i c a l k e y w o r d s ：n o n c o n v e x s e c o n d - o r d e rc o n e ；n o n l i n e a rl a g r a n g i a n s ；n o n l i n e a rr e s c a l 。 i n gm e t h o d ；l f w n e ro p e r a t o r ；i n e x a c ta l g o r i t h m 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方 外，本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已 申请学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的 贡献均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：韭鱼三塑亡丝鋈魁d 回趑丝韭筮呦逊查叠 作者签名：邀剑 日期：型乒年j 月j 赵日 大连理工大学博士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目：宴垦整当鸳推型盥塑丝叠e 毯壁垒拯虚盈之垄 作者签名：冱丛型日期：丝年兰月互日 导师签名：纽 蹶卑年j 月日 大连理工大学博士学位论文 1绪论 本章介绍7 - - 阶锥规划的发展现状和非线性l a g r a n g e 方法的研究背景，并对相关文 献做了综述，列出了本文的主要研究结果，并在最后给出本文所需要的一些预备知识 1 1 二阶锥规划的研究背景 “二阶锥规划”是“s e c o n do r d e rc o n ep r o g r a m m i n g ”的中文译名，是一类非常重要的优 化问题首先我们给出二阶锥的定义 定义1 1 若+ 1cr m + 1 满足 蚤，m + 1 ：= ( s o ；否) r l ：l , t m ：8 0 1 1 5 1 1 ( 1 1 ) 则称+ 1 为仇- t - 1 维的二阶锥，又叫做冰激凌锥或l o r e n t z 锥 二阶锥规划问题( s o c p ) 可以追溯到1 7 世纪经典的f e r m a t - w e b e r 问题f e r m a t 在他那 篇著名的关于最大数和最小数的文章最后，向那些质疑他方法的人提出了这样一个问题： 在一个平面上给定三个点，找到第四个点满足，它与给定的三个点之间的距离之和最小 容易看出，经过一些变换，这个问题可以转化成一个简单的s o c p 问题【1 1 二阶锥规划问 题在运输，物流，工程，以及组合优化等领域都有着非常广泛的应用，在本节中我们简要 地介绍一下s o c p 在这些领域中的应用 设施定位问题( f a c i l i t i e sl o c a t i o np r o b l e m ) 和s t e i n e r 最短树问题( s t e i n e rm i n i m a lt r e e p r o b l e m ) 广泛应用于运输和物流中的欧几里德设施定位问题以及组合中 的s t e i n e r 最短树问题( s t e i n e rm i n i m a lt r e ep r o b l e m ) 都是f e r m a t 问题的推广，x u e 和y e 【l j 指出，这两类问题都可以转化成二阶锥规划问题，并用内点法有效地求解出最 优解，且算法具有多项式复杂性更多关于这些模型的工作可参考文献吲等 天线阵权重模型( a n t e n n aa r r a yw e i g h td e s i g n ) 文献慨4 j 表明许多天线阵约束问题 都可以转化成s o c p 问题，并且可以用内点法有效地求解。 f i r 滤波器设计( f i rf i l t e rd e s i g n ) l o b o 等【) j 证明了极小极大化复转换函数设 计( m i n i m a xc o m p l e xt r a n s f e rf u n c t i o nd e s i g n ) ，极小极大化线性相位低通滤波器设 计( m i n i m a xl i n e a rp h a s el o w p a s s f i l t e rd e s i g n ) ，极小极大化d b 线性相位低通滤波器设 非凸二阶锥规划问题的非线性重新尺度化方法 计( m i n i m a xd bl i n e a rp h a s el o w p a s sf i l t e rd e s i g n ) 都可以转化成s o c p f 司题、u 等【6 j ：i l 西 过变量代换以及谱分解的工具，将量值f i r 过滤模型问题( m a g n i t u d ef i rf i l t e rd e s i g n p r o b l e m ) 转化成s o c p f 口 题，并用内点法求得问题的全局最优解 带分片线性s p r i n g s 的平衡体系( e q u i l i b r i u mo fs y s t e mw i t hp i e c e w i s e l i n e a rs p r i n g s ) 文献【) j 通过变量代换以及增加双曲线约束将带分片线性s p r i n g s 的平衡体系 转化成s o c p 问题，并指出若s p r i n g 收紧和扩张函数( s p r i n gt e n s i o nv e r s u se x t e n s i o n f u n c t i o n ) 是分片线性的且递增的，则平衡构形( e q u i l i b r i u mc o n f i g u r a t i o n ) 可以通过二 阶锥规划问题来找到 桁架设计( t m s sd e s i g n ) 可参考文献 7 _ 9 】等 带风险损失约束的投资组合优化问题( p o r t f o l i oo p t i m i z a t i o nw i t hl o s sr i s kc o n s t r a i n t s ) 文献例指出目标为预期收益函数，约束为风险损失的投资组合优化模型可 以转化成一个带有一个二阶锥约束的简单的s o c p 问题，并可以推广到其它形式更 为复杂的一些投资组合问题 鲁棒投资组合优化问题( r o b u s tp o r t f o l i oo p t i m i z a t i o np r o b l e m ) g o l d f a r b f f 千l l y e n g a r 1 0 i j 入市场参数的t 非确定结构”，证明了相应于这些非确定结构的 鲁棒投资组合选择问题可以转化成s o c p 问题，从而降低了问题的计算难度 当然，除了这些以外，s o c p 问题还在其它很多领域都有应用，例如握力优化( g r a s p i n g f o r c eo p t i m i z a t i o n ) 11 ，1 2 ，图像复原问题( i m a g er e s t o r a t i o np r o b l e m ) 以及鲁棒多类别分类 问题( r o b u s tm u t i c l a s sc l a s s i f i c a t i o np r o b l e m ) 1 1 3 1 等等，在这里我们就不一一叙述了 值得一提的是，尽管二阶锥规划问题可以转化成半定规划问题进行求解，但是这样 做会带来两方面的后果，其一，使得问题的规模变大，从而给实际计算带来困难；其二，变 化后的问题可能会丧失一些原问题好的结构，例如，若原问题是线性二阶锥问题，则转化 后的半定规划问题一般来说不再是线性的，因此有必要从二阶锥本身的视角来研究它的 理论和方法 2 大连理工大学博士学位论文 11 2 二阶锥规划的发展现状 目前对二阶锥规划( s o c p ) 的研究分为线性二阶锥规划和非线性二阶锥规划两类标 准的线性二阶锥规划形式如下： m i n i m i z e 一芏 s u b j e c tt oa x = 6 ， ( 1 2 ) z k 其中a r m 黼，b r m ，c 础，k = k m l + lxk m 2 + l k m j + l 为r 仇上的二阶 锥线性规划、凸二次规划以及具有二次约束的凸二次规划等均可转化成线性s o c p 问 题，参见文献【，h ，d j 对线性s o c p 问题的研究开展的比较早，在上个世纪9 0 年代，凸 二次约束规划引起了学者们的广泛兴趣，而它是s o c p 的一种特殊情况g o l d f a r b ，“u 和w 孤g 1 6 ，j 黜【1 7 】以及m e h r o t r a 和s u n 【1 8 】各自独立地将k a n n a r k a r l 拘内点法【1 9 】推广 到凸二次约束规划问题上随后，n e t e r o v 和n e m i r o v s k i 1 4 j 证明了将自协调障碍中的一般 结果应用到线性s o c p 问题上时，可以得到线性s o c p 的内点算法，并且对具有r 个二阶锥 不等式约束的问题，算法的迭代复杂性为n e m i r o v s k i j f f l s c h e i n b e r 9 1 2 0 j 指出，线性规划 的原始或对偶内点法可以直接推广到线性s o c p 问题上 接下来人们把目光投向了原始_ 对偶内点法同线性规划及半定规划一样，求解线 性s o c p 问题的原始一对偶内点方法在数值表现上更具鲁棒性进一步，由于对这些算法 的研究不仅具有挑战性，而且在实际应用上也占有非常重要的作用，因此对这一算法展 开了深入的研究线性s o c p 问题的原始_ 对偶内点法最先是由n e s t e r o v 和t o d d 2 1 ，2 2 提 出的，一种被称为n t 方法的原始一对偶内点算法，是n e s t e r o v 和t o d d 的巅峰之作 a d l e r 弄l l a l i z a d e h l 2 j j 讨论了半定规划和二阶锥规划之间的关系并把所谓的x z + z x 方 法【2 4 j 具体化到线性s o c p i 司题上接下来，a l i z a d e h 年 l ：i s c h m i e t a 2 5 出了线性s o c p 问 题的非退化条件，并提出了一个x z + z x 方法的稳定数值实现，这个实现在s d p p a c k 软 件包【2 6 1 中得到使用随后，m o n t e i r o 和t s u c h i y a l 2 ，j 证明了上述方法以及所有的m o n t e i r o z h a n g 类方法都具有多项式计算复杂性 基于欧氏若当代数，可以把线性规划，半定规划以及二阶锥规划统一到一种理 论上去f a r a u t 和k o r 细g 在文献 2 8 】中给出了这理论的基础f a y b u s o v i c h 2 9 - 3 1 y k 若当代数的角度，讨论了非退化条件并给出了n t , x z 和z x 方法s c h r n i e t a 3 2 j 以 3 非凸二阶锥规划问题的非线性重新尺度化方法 及s c h m i e t a 和a l i z a d e h 3 j ，3 4 j 运用若当代数的工具将s d p 上的m o n t e i r o z h a n g 类内点法 分析推广到所有的对称锥上另外，t s u c h i y a 3 5 ，j 借助若当代数对线性s o c p 上的内点 法进行了分析 目前有很多求解s o c p 问题或混合s o c p , l p 以及s d p 问题的软件包之前提到 的s d p p ! a c k 包就是其中的一种s t u r m 的s e d u m i 3 7 j 是另外一种应用广泛的软件包，它 是基于n e s t e r o v 。t o d d 方法的s t u r m 在文献【3 8 j 中给出他计算工作的理论基础更多关于 线性s o c p 问题的研究可参考文献 3 蛐2 1 近年来，由于对线性二阶锥规划问题的研究已较为完善，因此，学者们又把目光转到 非线性二阶锥问题的研究上来非线性二阶锥规划的标准形式如下： m i n i m i z e s u b j e c tt o 其中，f ：r n r 为实值函数，h ：r n _ r f ，g ：r n _ r m 汁1 ，i = l ，j 为向量值映 射，。+ 1 为r m t + 1 上的二阶锥b o r m a n s 和r 疵z 【4 3 】研究了非线性二阶锥规划问题的 一阶及二阶最优性条件，并从二阶最优性条件的角度描述了强正则性，从而为发展非线 性二阶锥规划问题的算法提供了理论基础随后，诸多学者也先后提出许多求解非线 性s o c p 问题的方法，近年来发展的方法主要包括以下几类： 1 原始一对偶内点算法( p r i m a l d u a li n t e r i o rm e t h o d s ) 内点法是求解线性规划问题 一类非常重要的算法，其思想来源于1 9 8 4 年k a r m a r k a r 提出的求解线性规划的算 法这类算法的优点在于它具有多项式计算复杂性，适合于大规模问题的计算 y a m a s h i t a 和y a b e l 4 4 j 将原始对偶内点法推广到非线性二阶锥规划问题上，提出了 一个新的结合了障碍惩罚函数以及势函数的原始对偶效益函数，并基于该效益函 数建立了一个带有加1 i l i j o 线搜索的原始对偶内点方法，收敛性定理表明该方法在 一定的假设条件下是全局收敛的 2 半光滑牛顿方法( s e m i s m o o t hn e w t o nm e t h o d s ) 。半光滑这个概念最初是 i 刍m i f f l i n 在1 9 7 7 年的文献【4 5 】中针对实值函数提出的，后来，q i s f l s u n 4 6 糙j ：这一 概念推广到向量值函数。并据此提出了求解半光滑向量值方程组的半光滑牛顿 法此后，半光滑牛顿法在线性和非线性优化及互补等问题上得到了深入的研究， 4 z i i +叭 = 神动荆荆 大连理工大学博士学位论文 可参见文献 4 7 巧1 】等c h e n ，c h e n 和t s e n g 5 2 】以及s u n 和s u n 5 3 】分别探讨了二阶锥 上的向量值函数的非光滑性质，从而将半光滑牛顿法引入到二阶锥领域k a n z o w , f e r e n c z i 和f u k u s l l i m a | 5 4 j 分析了使二阶锥上的半光滑牛顿法达到局部二次收敛的 条件，而且他们指出即使解的严格互补条件不成立，半光滑牛顿方法依然可以达到 局部二次收敛，从这个角度讲，该方法是优于内点法的更多的关于二阶锥上半光 滑牛顿法的文献可参见【，5 6 j 等 3 光滑化牛顿方法( s m o o t h i n gn e w t o nm e t h o d s ) 人们发现，将光滑化技巧应用 于半光滑牛顿法可以提高其计算速度，从而产生了光滑化牛顿法光滑 化牛顿法最初是由m a d s e n 和n i e l s e n 在文献l ) ，j 中用于求解线性f 1 问题的此 方法在优化问题领域和互补问题领域引起了诸多学者的研究兴趣，参见著 们g 5 8 ，5 9 】和文献【6 嘶2 】等f u k u s h i m a , l u o 和t s e n g 6 3 将c h e n - m a n g a s 撕锄类光滑 化函数1 0 4 ，j 以及光滑化的f i s c h e r - b u r m e i s t e r 函数推广到二阶锥问题上，他们研究 了这两类函数的l i p s c h i t z 和微分的性质，计算了这些函数的j a c o b i a n s ，将光滑化方 法推广：至u - - 阶锥问题上h u a n g ，s u n 和z h a o l o b j 提出了一个求解带凸二次不等式约 束的凸二次规划的光滑化牛顿法，并证明了算法在一定条件下是全局收敛的，收敛 率为超线性的h a y a s h i ，y a m a s h i t a 和f u k u s h i m a l o j 将光滑化方法与正则性方法结 合起来，提出了一个求解单调二阶锥互补问题的算法，并证明了在适当的条件下，该 算法是全局二次收敛的更多的关于光滑化牛顿法的文献可参见l 嘣j 等 4 序列二次规划( s q p ) 方法( s e q u e n t i a lq u a d r a t i cp r o g r a m m i n gm e t h o d s ) 序列二次规划 方法兴起于上世纪6 0 年代，最早是w i l s o n ( 1 9 6 3 ) 1 6 9 j 在他的博士论文中提出的 b o g g s 和t o u e 在文献i ，u j 中提到，如果选取合适的二次子问题，那么序列二次规划方 法可以看成是牛顿法和拟牛顿法在约束优化背景下的一种平凡推广，因此该方法是 一种非常有效地求解约束优化问题的方法k a t 0 和f u k u s h i m a t ，l j 将序列二次规划 方法应用到非线性s o c p 问题上，他们所提出的算法采用带f 1 惩罚函数线搜索的内 点法来求解每一次迭代中的子问题该算法在一定的假设条件下是全局收敛和局部 二次收敛的 5 增广l a g r a n g e 方法( a u g m e n t e dl a g r a n g em e t h o d s ) a r r o w ； ：i s o l o w ( 19 5 8 ) 2 j 在用微 分方程方法求解带有等式约束的非线性规划问题时，第一次提出了增广拉格朗日函 数这个概念h e s t e n e s ( 1 9 6 9 ) 7 3 l ：j p o w e l l ( 1 9 6 9 ) 7 4 】分别提出了求解具有等式约束 5 一 非凸二阶锥规划问题的非线性重新尺度化方法 的非线性规划问题的增广l a g r a n g e 方法随后，r o c k a f e l l d 7 5 - 7 9 j 将这个方法推广 到一般的非线性规划问题中在一定条件的保证下，增广l a g r a n g e 方法是局部线性 收敛的，并且收敛速度跟惩罚参数成比例，因此，算法在选取很大的惩罚参数加快收 敛速度的同时还可以保证稳定性，这个优点吸引了众多学者对这一方法的兴趣自 上世纪7 0 年代开始，非线性优化问题的增广l a g r a n g 方法得到了飞速的发展，关于经 典增广l a 斟a n g e 法的详细研究工作可参阅【8 旧4 】等l i l 】痢z h a n g 9 5 】研究了非线性 二阶锥上的增广l a g r a n g e 方法，并证明了在严格互补条件，约束非退化条件以及二 阶充分性条件的保证下，增广l a g r a n g e 方法有着与在非线性优化问题中同样出色的 表现更多关于二阶锥规划问题的增广l a g m g e 方法的工作可参见【y o 叫圳 注1 2 与非线性规划问题相比，非线性二阶锥规划的二阶充分性条件增加t s i g m a ：项，在 前面提到的五大类方法中，只有增广l a 铲a n g e 方法在收敛性分析中讨论了对s i g m a , 项的处 理 关于非线性二阶锥规划问题的研究，发展还是比较缓慢，我们期待有更多的工作的 出现到目前为止，关于非凸二阶锥规划的非线性重新尺度化方法方面的的文献比较少， 因此，本文要在此基础上对这一专题展开研究 6 大连理工大学博士学位论文 2二阶锥的最优性条件 本章主要介绍- f - - 阶锥的最优性条件及一些相关的概念和定理，并在最后给出了本 文所需的一些预备知识 2 1 一般约束集合的变分几何 2 1 1 集值映射的极限 设x 与u 是两个有限维的i - i i l b e r t 空间，用2 u 是空间u 的所有子集合的全体从x 到u 的 一集值映射是x 到2 u 的一映射，即对应z x 为一集合s ( z ) 2 u ，记为s ：xj u 或s ： x 一2 u 集值映射s 的定义域，值域定义为 d o r as = z ls ( x ) 0 ) ，r a n g es = uij z x ，t s ( z ) ) 集值映射s 的逆定义为s 一1 ：ujx ，定义为 s 一1 ( t 1 ) = ziu s ( z ) ) ， 定义2 1 设x 与u 是两个有限维的h i l b e r t 空间，s ：xj u 是一集值映射，s 在z 一邡寸 的外极限是下述集合 l i r a s u ps ( x ) = t 正l | z 七一孟，3 u 七s ( x 七) ，u 七一心) ， 2 _ 孟 s 在z _ 牙时的内极限是下述集合 l i m i _ n fs ( x ) ： t 正i 妇七一牙，3 n 人乙，u 七s ( x 七) ，王n ，t 七乌u ) z - - + 2 , 基于集值映射的极限可以给出以函数为值的映射的下上图极限，上上图极限与上图 极限的概念 + n 表示自然数集合，眠= n c n l n 是有限集合) 7 非凸二阶锥规划问题的非线性重新尺度化方法 定义2 2 对于定义于x u 上的函数f ( x ，让) ，可将它视为函数为值的映射u 一厂( ，仳) ， 它的当u 一硼寸的下上图极限e h m i n f u 。豇，( ，u ) 是以集值映射也_ 印i ，( - ，钍) 的让一硼寸 的外极限为上图的函数： e p i ( e l i mi n f ，( ，钍) ) = l i ms u p ( e p i ，( - ，仳) ) u 呻乱 t + 缸 它的当札_ 硼寸的上上图极限e l i ms u p u 面，( ，u ) 是上图为集值映射u e p i 厂( ，乱) 的u _ 面时的内极限的函数： e p i ( e l i ms u pf ( ，u ) ) = l i mi _ n f ( e p i ，( ，乱) ) 牡面 t 正+ u 当下上图极限与上上图极限重合时，称此函数为值的映射的上图极限e l i m u 豇，( ，u ) 存 在，e - l i i i l 一面，( ，u ) = e l i m i n f 一面，( ，u ) = e - l i m s u p , , 面，( ，u ) 此种情形，称，( ，钍) 上 图收敛到，记为，( ，u ) f 2 1 2 增广实值函数的方向上图导数 设y 是有限维h i l b e r t 空间考虑一增广实值函数，：x _ 瓦设点z x 满f f a f ( x ) 有 限定义差商函数 鲥( 酬班丛掣d o 定义2 3 ( i ) 称，在z x 处沿，： l h - j h x 是方向可微的，若极限 舳垆船丛掣 存在若，在z 处沿每一方向 x 均是方向可微的，则称，在z 处是方向可微的 若，在z 处是方向可微的且方向导数，( z ； ) 关于 是线性的，连续的，即存在线性算 子d f ( x ) 乡( x ，y ) ，满足，7 ( z ；h ) = d f ( x ) h ，则称，在z 处是g a t e a u x 可微的 ( 赶) ，在z 处的上，下方向导数分别定义为 只( z ；h ) ；l i ms u pa t ，( z ) ( 危) ， 上o 8 大连理工大学博士学位论文 正( 。；h ) = l i m i n f a t f ( x ) ( h ) t l u 若群( z ；h ) = 正( z ； ) ，称，在z 处沿方向九是方向可微的 ( i i i ) ，在z 的下方向上图导数( 或下次导数) 正( z ；) 定义为 正( z ；) = e - l i m t i o i n f a f 施) ； 上方向上图导数肆( z ；) 定义为 肆( z ；) = e 1 i ms u pa t ，( z ) ； 若正( z ；九) = 肆( z ； ) ，称，在z 处沿方向九是方向上图可微的，记，( z ；尼) 为它们公共 的值，称之为厂在z 处沿 的上图导数；如果正( z ；) = 肆( z ；) ，则称，在。处是上图可微 的，记厂( z ；) = 正( z ；) = 辟( z ；) 其中z ，三z 意味着z ，_ z 且厂( ) 一，( z ) 注2 4 如果，在z 附近时l i p s c l l i t z 连续的，则对所有的九x ，有正( z ；h ) = 正 ；h ) 且一( z ； ) = ，：( 。； ) 若，是方向可微的，下述极限存在，则二阶方向导数定义为 八咖川= 船盟塑笋型型 ( 2 - ) 上二阶方向导数定义为 肚沌小，i m j 严盟堕掣型，t 上0百l _ 下二阶方向导数可类似定义若，具有二阶t a y l o r 展式 则 ，( z + ) = - 厂( z ) + d 厂( z ) + 互1 d 2 ，( z ) ( ，危) + 。( 1 l h l l 2 ) ， ，( z ；h ，w ) = d f ( x ) w - 4 - d 2 ，( z ) ( 九， ) ， 9 非凸二阶锥规划问题的非线性重新尺度化方法 其中，d f ( ) 设，( z ) 与方向上图导数正( z ， ) ，肆( z ，h ) 是有限的，可以定义下二阶上图导数与上二 阶上图导数 斯池) = e - ，；咿盟型掣， ( 啪，) _ e - l i p 迎丝生专竺幽 t & o 2 “ 称，在z 处沿方向 是二阶方向上图可微的，若正( z ；h ) = 肆( z ；危) ，( z ；h ，) = 岸( z ；h ，) 再次注意到，若，( ) 是l i p s c h i t z 连续的，在z 处方向可微，则对h ，w x 有( z ；h ，w ) = 拦( z ；h ，w ) 且岸( z ；h ，w ) = 群( z ；h ，叫) 2 1 3 集合的切锥及二阶切集 设x 是有限维h i l b e r t 空间，s 是x 的闭子集，厍j d i s t ( z ，s ) 记z x 到s 距离， 即d i