约束优化二次规划与SQP

第２８卷㊀第８期２０２０年８月㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀光学精密工程㊀O p t i c s a n dP r e c i s i o nE n g i n e e r i n g㊀㊀㊀㊀㊀㊀㊀V o l ．２８㊀N o ．８㊀A u g．２０２０㊀㊀收稿日期:２０２０Ｇ０１Ｇ０９;修订日期:２０２０Ｇ０２Ｇ１８．㊀㊀基金项目:吉林农业科技学院大学生科技创新创业训练计划资助项目(N o ．２０１９１１４３９０２７);吉林农业科技学院青年基金资助项目(N o ．２０１９０５０５)文章编号㊀１００４Ｇ９２４X (２０２０)０８Ｇ１７３３Ｇ１０两栖球形机器人的路径规划策略马宇科１,郑㊀亮１,２∗,胡高凯１,吉晓雯１,司兆怡１,刘晏彤１(１．吉林农业科技学院,吉林吉林１３２１０１;２．长春理工大学,吉林长春１３００２２)摘要:两栖机器人的水下路径最优规划是目前机器人运动控制研究领域的热点和难点.本文针对两种基于视觉伺服的广义约束优化(G C O P )和序列二次规划(S Q P )的机器人运动控制算法进行对比分析,结合视觉伺服传感器,实现了两栖机器人最佳路径的规划㊁监测动态目标标定㊁移动目标监测㊁水下障碍物识别和目标跟踪.利用球形机器人的结构对称特性及阿基米德浮力原理,并结合模糊控制算法对水舱水位进行实时控制,使球形两栖机器人在水下能实现水下多自由度运动.最后,进行了算法的仿真和水下运动实验.实验结果表明,G C O P 算法和S Q P 算法在相对障碍物的有限距离内,S Q P 算法规划的路径更加合理;而在达到目标坐标位置上,两种算法的误差为１６７．５m m ,S Q P 算法在水下路径规划上更加有效.关㊀键㊀词:两栖机器人;球形机器人;路径规划;目标识别中图分类号:T H ７３㊀㊀文献标识码:A㊀㊀d o i :１０．３７８８/O P E ．２０２０２８０８．１７３３P a t h p l a n n i n g s t r a t e g y o f a m p h i b i o u s s ph e r i c a l r o b o t MA Y u Ｇk e １,Z H E N GL i a n g １,２∗,HU G a o Ｇk a i １,J IX i a o Ｇw e n １,S I Z h a o Ｇy i １,L I U Y a n Ｇt o n g１(１．J i l i nA g r i c u l t u r a lS c i e n c e a n dT e c h n o l o g y U n i v e r s i t y ,J i l i n １３２１０１,C h i n a ;２．C h a n g c h u nU n i v e r s i t y o f S c i e n c e a n dT e c h n o l o g y ,C h a n gc h u n １３００２２,C h i n a )∗C o r r e s p o nd i n g a u t h o r ,E Ｇm a i l :s １８d ５０５＠s t u ．k a g a w a Ｇu ．a c ．j pA b s t r a c t :T h eu n d e r w a t e r p a t h p l a n n i n g o f a m p h i b i o u s s p h e r i c a l r o b o t s i s c u r r e n t l y a re s e a r c hc h a l Ｇl e n g e i n t h ef i e l d o f a m p h i b i o u s r o b o tm o t i o n c o n t r o l ．I n t h i s s t u d y ,t w o t y p e s o f r o b o tm o t i o n c o n t r o l a lg o r i th m s ,n a m e l y G e n e r a li z e dC o n s t r a i n tO p t i m i z a t i o n (G C O P )a n dS e q u e n t i a lQ u a d r a t i cP r o gr a m Ｇm i n g (S Q P )a l g o r i t h m sb a s e do nv i s u a l s e r v o ,w e r ec o m p a r e da n da n a l y z e d ．T h eo pt i m a l p a t h p l a n Ｇn i n g o f t h ea m p h i b i o u ss p h e r i c a l r o b o tw a s r e a l i z e d ,c o m b i n a t e dw i t hv i s u a l s e r v os e n s o r s ．D yn a m i c t a r g e t c a l i b r a t i o n ,m o v i n g t a r g e tm o n i t o r i n g ,u n d e r w a t e ro b s t a c l er e c o g n i t i o n ,a n dt a r g e t t r a c k i n g Ｇf u n c t i o n sw e r ea l s o d e v e l o p e d ．F u r t h e r m o r e ,t h i ss t u d y c o n s i d e r e dt h es ym m e t r i c a ls t r u c t u r eo f s p h e r i c a l r o b o t s (u s i n g A r c h i m e d e s ᶄb u o y a n c y p r i n c i p l e )a n d c o m b i n e d f u z z y c o n t r o l a l g o r i t h m s t o c o n Ｇt r o l t h ew a t e r l e v e l o f t h ew a t e r t a n ks o t h a t s p h e r i c a l a m ph i b i o u s r o b o t s c a na c h i e v em u l t i ＧD O Fu n Ｇd e r w a t e rm o t i o n ．F i n a l l y ,a l g o r i t h ms i m u l a t i o n s a n du n d e r w a t e rm o t i o ne x p e r i m e n t sw e r e p e r f o r m e d t ov e r i f y t h e f e a s i b i l i t y o f t h e p r o p o s e dm e t h o d ．T h e r e s u l t s s h o wt h a t p a t h p l a n n i n g b y t h e S Q Pa l go Ｇ. All Rights Reserved.r i t h mi sm o r e r e a s o n a b l e c o n s i d e r i n g t h e d i s t a n c e b e t w e e n t h eG C O Pa n dS Q Pa l g o r i t h m s,r e l a t i v e t o t h eo b s t a c l e．I n r e a c h i n g t h e t a r g e t c o o r d i n a t e p o s i t i o n,t h e e r r o r b e t w e e n t h e t w o a l g o r i t h m s r e a c h e s t o１６７．５m m,s h o w i n g t h a t t h e S Q P a l g o r i t h m i s s u p e r i o r i n u n d e r w a t e r p a t h p l a n n i n g t h a n t h eG C O P a l g o r i t h m．K e y w o r d s:a m p h i b i o u s r o b o t;s p h e r i c a l r o b o t;p a t h p l a n n i n g;t a r g e t r e c o g n i t i o n１㊀引㊀言㊀㊀目前,在机器人研究领域,两栖仿生机器人的研究逐步成为研究热点,通过对一种动物运动方式的长时间观察与研究,提出了相应具有运动模式的仿生机器人的设计方案.这类机器人具有较为灵活的两栖运动能力,能够在水下实现最佳的路径控制和对目标具有一定的识别与追踪能力,但是,以往提出的仿生机器人大多只适应于水下的运动环境,对于目前所需要的两栖运动环境并不合适,球形两栖机器人能够很好地解决这一问题.在一些特殊的应用环境下,例如两栖侦察㊁海底探测㊁深海探测等相关领域,一般性能的机器人无法满足要求,所以两栖机器人应运而生.由于两栖机器人特殊的灵活性㊁超强的适应能力㊁便于投放和回收的优越特性,使它可以独立在水下完成侦查㊁搜救㊁探测㊁数据收集等工作.所以两栖球形机器人很自然地成为人类延伸自己感知能力的主要工具之一.本文提出的两栖球形机器人是一种先进的执行装置,包括运动推进器,传感器,控制板和安装在球形壳体中的电源装置.作为微型球形机器人,这种机器人得到广泛应用主要依靠四个技术优势.第一个特点是球形机器人是一种可移动行走的移动机器人,可以保持先进的平衡性㊁稳定性和运动连续性.第二个特点是球形机器人具有良好的密封性,可以完全保护内部控制单元和机构,这是其他机器人无法做到的.第三个特点是球形机器人具有很强的适应性,能在无人区㊁灰尘㊁湿气㊁腐蚀性和恶劣环境下完成任务.最后是矢量推进器具有更高的稳定性和灵活性,能使机器人保持更好的水下运动性能和抗噪声干扰能力.两栖机器人控制技术发展迅速,北京理工大学仿生机器人与系统教育部重点实验室郭书祥团队研究的两栖球形机器人,是以球形为主体的机器人,整体结构分为上半球和下半球.在陆地模式时,下半球可以折叠到上半球,用４个由８个舵机组成的机械臂行走,在水下模式的时候,折叠的上半球通过二个舵机封闭下半球,由喷水电机推进行走,球体内部也安装了通信和稳定控制模块,该球基本实现了球形机器人的基本功能,但没有实现水下的自动路径规划[１Ｇ３].北京邮电大学孙汉旭团队研究的球形机器人以摩擦力为驱动力,没有被动摩擦力的球形机器人,该机器人具有运动效率高,对路面要求低,适应能力强等优点[４].哈尔滨工程大学叶秀芬团队,也对球形机器人 基于喷水推进的微小球形水下潜器 进行了深入的研究[５].天津理工大学郭健团队也对球形机器人在陆地上的路径规划进行了深入的研究[６].但目前针对水下路径规划的相关研究相对较少.机器人执行有障碍的复杂水下任务时,路径规划对水下机器人实现任务目标具有非常重要的意义.文献[７]提出了一种基于先验知识强化学习策略的最佳路径选择的新算法.针对未知空间中移动机器人的路径规划问题,Y u a n等提出了一种基于门控递归单元Ｇ递归神经网络模型的动态路径规划方法[８].B a e等提出了一种结合深度学习和卷积神经网络的多机器人路径规划算法[９].文献[１０]提出了一种非完整的三轮移动机器人的路径规划和控制方法,该机器人用于在道路跟踪和复杂环境中进行在线导航.文献[１１]开发了一种 增强轮辋跳跃 的方法,该方法不依赖于逐点定位,而是通过找到障碍物之间的多次切线来获得最短路径.尽管在两栖球形机器人的路径规划方面已有许多研究,但是多数研究是基于单一的陆地环境下进行的.本文以实现球形两栖机器人最佳路径规划为研究目标,针对两种基于视觉伺服的广义约束优化(G e n e r a l i z e dC o n s t r a i n tO p t iＧm i z a t i o n,G C O P)和序列二次规划(S e q u e n t i a l Q u a d r a t i cP r o c o n t r o l,S Q P)的机器人运动控制算法进行对比分析,使用视觉伺服传感器实现两栖４３７１㊀㊀㊀㊀㊀光学㊀精密工程㊀㊀㊀㊀㊀第２８卷㊀. All Rights Reserved.机器人的最佳路径规划,并实时对监测动态目标进行标定㊁移动目标监测㊁水下障碍物识别和目标跟踪.最后,通过水下运动测试和仿真来对比验证算法的可行性.该运动的路径规划方案提高了球形两栖机器人的运动性能,使机器人可以执行更为复杂的水下任务.２㊀两栖球形机器人设计２．１㊀机械设计新型两栖球形机器人不仅具有良好的陆地运动能力,而且能够实现水下多自由度的运动.图１是机器人陆地运动模式和水下运动模式的结构.在陆地模式下,机器人下半球壳体通过两个舵机折叠至上半球,４个喷水推进器根据相应步态调整实现陆地行走[１２].在水下模式下,下半球闭合,机器人可以利用４个水下推进器实现水下多自由度运动.相比其他两栖球形机器人,加入了稳定控制块㊁４个激光测距模块和４个视觉采集模块,用来实现路径规划的相关参数采集.图１㊀两栖球形机器人的机械结构F i g ．１㊀M e c h a n i s mo f a m p h i b i o u s s ph e r i c a l r o b o t ２．２㊀硬件构成两栖球形机器人采用模块化设计,通过各模块的合理分布与协调工作,保证球体运动的可靠性和稳定性.如图２所示,球体主要搭载一块嵌入式处理器(A R M S ３C ６４１０,２G B D D R ３,l i n u x３．１２．０),用于数据处理;G P S 模块和声纳模块用于机器人通讯.陀螺仪传感器对机器人进行姿态感应与调整,伺服电机和电机控制器控制机器人的运动和姿态,图像采集模块用于机器人的视觉识别与动态目标捕捉,５０００m A 锂电供电模块用于机器人的供电.图２㊀两栖球形机器人的硬件结构F i g ．２㊀H a r d w a r es t r u c t u r eo fa m p h i b i o u ss ph e r i c a l r o b ot图３㊀机器人上浮和下潜原理F i g ．３㊀P r i n c i p l e f o r r o b o t f l o a t i n g a n dd i v i n g３㊀两栖球形机器人上浮下潜原理㊀㊀球体分为上半球和下半球两个仓室,如图３所示,下仓室装有排水口,通过上仓室的仓室气泵将上仓室的空气压入下仓室,通过下仓室的水压调节罐控制水箱的进水量,根据阿基米德浮力原理,球体的浮力由球体排开水的体积决定.当机５３７１第８期㊀㊀㊀㊀㊀㊀㊀马宇科,等:两栖球形机器人的路径规划策略. All Rights Reserved.器人下潜时,防水舵机顺时针旋转,将放气的阀门关闭,水从球体一端的孔进入,由于压力的作用,原本在球体内部的气体从球的另一端排出.水的重量再加上球体本身防水舵机的重量使球形机器人进行下潜.上浮时,防水舵机逆时针旋转,将二氧化碳气瓶中的压缩二氧化碳气体放出,此时排气孔和进水孔都变成了排水孔,机器人上浮.４㊀运动控制和路径规划算法４．１㊀非线性６自由度算法两栖球形机器人能够在陆地与水下多自由度运动,在陆地上要具有４个自由度,在水下要具有６个自由度的运动模式.图４㊀６自由度建模坐标标定F i g ．４㊀C a l i b r a t i o no f ６ＧD O Fm o d e l i n g co o r d i n a t e ６自由度包括R P Y (q ,p ,r )和Z Y Z (v ,u ,w )参考系.为了达到精确控制的目的,分别给出了两种受控源的旋转矩阵.如图４所示,参考坐标以x 轴围绕的角度 q 旋转,并用矩阵R x (q )表示.参考坐标以Y 轴围绕的角度 p旋转,并用矩阵R y (p )表示.参考坐标以Z 轴围绕的角度 r 旋转,并用矩阵R z (r )表示[１３].R (φ)＝Rx (q )R y (p )R z (r )＝C q C p C q S p S r －S q C r C q S p C r ＋S q S r S q S p S q S p S r ＋C q C r S q S p S r ＋C q S r －S pC p S r C q C r æèçççöø÷÷÷．(１)㊀㊀假设参考坐标绕Z 轴旋转一个φ的角度,并且旋转矩阵为R z (φ),参考坐标绕Y 轴旋转一个ϑ的角度,并且旋转矩阵为R yᶄ(ϑ),参考坐标绕Z 轴旋转一个ψ的角度,并且旋转矩阵为R z ᵡ(ψ).最终坐标系的方向是通过合成相对于当前坐标系的旋转矩阵并通过右乘计算得出的,获得基本矩阵为:R (Φ)＝R z (φ)R y ᶄ(ϑ)R z ᵡ(φ)．(２)㊀㊀旋转矩阵为:R ＝r １１r １２r １３r ２１r ２２r ２３r ３１r ３２r ３３æèçççöø÷÷÷．(３)㊀㊀参数ϑ在[π,０],可以表示为:φ＝A t a n２(r ２３,r １３)ϑ＝A t a n２(r ２１３＋r ２２３,r ３３)ψ＝At a n２(r ３２,－r ３１)ìîíïïïï．(４)㊀㊀参数φ在[－π,０],可以表示为:φ＝A t a n２(－r ２３,r １３)ϑ＝A t a n２(－r ２１３＋r ２２３,r ３３)ψ＝At a n２(－r ３２,－r ３１)ìîíïïïï．(５)４．２㊀G C O P 控制算法假设物体的表面由m 个方程表示为:h i (x ),i ＝１,２, ,m ,并且它的内部方程为[１４Ｇ１６]:h １＜０ɡh ２ɡ ɡh m ＜０．(６)㊀㊀对每个h i 构造新的函数:v i ＝(h ２i ＋t ２)１/２＋h i ,(７)其中:t 是一个小的正实数,v i 是x 和t 的函数,对整个物体,构造函数V :V ＝v １＋v ２＋ ＋v m ＝ðmi ＝１v i．(８)㊀㊀验证从h i 到v i 和v i 到V 的两个变换的性质.首先,函数v i 对任意x 和t 总是正的,其次,v i 是关于h i 的递增函数,即当h i ＞０时v i 的值和当h i ＜０时v i 的值.如果t ≪１,v i 可以近似表示为:v i ＝２h i ＋O (t ２)≫t ＞０,h i ＞０v i ʈt ,h i ＝０v i ʈO (t ２),h i ＜０ìîíïïï,(９)其中:O (t ２)为一个值非常小的正数.式(９)表明,除了点在物体表面附近时,h i ＝０;当h i ＞０时,v i ＞t ;当h i ＜０时,v i ＜t .对于在物体h i 内部和边界附近的点,其他函６３７１㊀㊀㊀㊀㊀光学㊀精密工程㊀㊀㊀㊀㊀第２８卷㊀. All Rights Reserved.数值h i (j ＝１,２,．．．,m ,j ʂi )是小于零的,因此得到v t ＝O (t ２).将式(７)替换到式(９)中,得到:V ≫t ,(h １＞０)＋(h ２＞０)＋ ＋(h m ＞０)V ʈt ＋O (t ２),(h １＝０ɡh j ＜０,j ＝２,３, ,m )＋(h ２＝０ɡh j ＜０,j ＝㊀㊀１,３,４, ,m )＋ ＋(h m ＝０ɡh j ＜０,j ＝１,２, ,m －１)V ʈO (t ２),(h １＜０)ɡ(h ２＜０)ɡ ɡ(h m ＜０)ìîíïïïïï．(１０)㊀㊀从式(１０)可以看出,当所有的h i 是负,即点在物体内部时,函数V 非常小;当点在物体外部时,V ≫t ＋O (t ２);当点在物体边界附近时,V ʈt.考虑当t ң０时,则有:v i ＞０,h i ＞０v i ＝０,h i ɤ０{．(１１)㊀㊀两个正数的和还是正数,一个正数与零的和是正数,两个零的和是零.因此,如果把正数作为逻辑 １ ,把零作为逻辑 ０ ,那么式(１１)中v i 的加 操作对应了布尔 或 运算.所以得到:V ＞０,(h １＞０)ᶱ(h ２＞０)ᶱ ᶱ(h m ＞０)V ＝０,(h １ɤ０)ɡ(h ２ɤ０)ɡ ɡ(h m ɤ０){．(１２)㊀㊀在水下机器人路径规划中,不期望路径太靠近障碍物.因此,引入一个小的正数Δv 作为路径到障碍物的距离控制参数,如果x 满足以下不等式:V ＝ðviȡΔv 或Δv －ðv i ＜０．(１３)㊀㊀那么这个点一定在由式(１３)所确定的障碍物的外部.如果Δv ң０,由Δv －ðv i ɤ０确定的边界将趋近于障碍物的表面.如果一个物体的表面和外部由(h １ȡ０)ᶱ(h ２ȡ０)ᶱ ᶱ(h m ȡ０)确定,那么它的外部和表面同样可以由Δv －ðv i ɤ０确定,其中Δv ң０.x 若满足Δv －ðv i ɤ０,那么x 就落在物体的外部.４．３㊀S QP 控制算法为了在三个维度上对两栖球形机器人进行建模,必须设定６个独立变量构建环境的空间位置㊁方向㊁大小和形状,O ＝O (x ０,y ０,z ０)代表机器人的几何中心,θ＝(θ１,θ２,θ３)代表机器人的定位方向[１７Ｇ１９].x ＝x (x ０,y０,z ０,θ１,θ２,θ３,v ),(１４)y ＝y (x ０,y ０,z ０,θ１,θ２,θ３,v ),(１５)z ＝z (x ０,y０,z ０,θ１,θ２,θ３,v ),(１６)其中:x ,y ,z 是机器人边界上的一个点,用于构造没有碰撞条件的机器人,x ０,y０,z ０是空间位置,θ１,θ２,θ３是空间方向,v 是具有两个参数的向量,(t １,t ２)用于表示特定机器人的边界点,球形机器人定义如下:((x －x ０)/r x )２/s ２＋((y －y ０)/r y )２/s ２[]s ２/s １＋((z －z ０)/r z )s /s １＝１,(１７)x ＝r x c o s s １(t １)c o s s ２(t ２),(１８)y ＝r y co s s １(t １)c o s s ２(t ２),－π/２ɤt １ɤπ/２,(１９)z ＝r z c o s s １(t １),０ɤt １ɤ２π．(２０)㊀㊀基于S Q P 算法,路径规划问题转化为半无限约束优化问题.假设空间中有n 个障碍物,则j个障碍物的表面可以表示为[２０]:h １(x ,y ,z )＝１,j ＝１,２, ,n ．(２１)㊀㊀整个可用空间可表示为:１－h １(x ,y ,z )ɤ０,j ＝１,２, ,n ．(２２)㊀㊀没有碰撞的必要和充分条件是曲面上所有点都必须无碰撞,获得无碰撞的充分条件是:１－h j (x l o c ,y l o c ,z l o c )ɤ１,(２３)其中:x l o c ＝x (x ０,y０,z ０,θ１,θ２,θ３,v )y l o c ＝y (x ０,y０,z ０,θ１,θ２,θ３,v )z l o c ＝z (x ０,y０,z ０,θ１,θ２,θ３,v )．(２４)㊀㊀在路径规划中,配置变量需要一个约束,如公式(２５)所示[２１Ｇ２２]:x ０l ɤx ０ɤx ０u ,y０l ɤy ０ɤy ０u ,z ０l ɤz ０ɤz ０u ,θ１l ɤθ１ɤθ１u ,θ２l ɤθ２ɤθ２u ,θ３l ɤθ３ɤθ３u ．(２５)其中(x ０l ,y ０l ,z ０l )和(x ０u ,y ０u ,z ０u )分别是上限和下限,推导得到:１－h j (r x c o s s １(t １)c o s s ２(t ２)(c o s (θ１)c o s (θ２)c o s (θ３)－s i n (θ１)s i n (θ３))－r yc o s s １(t １)s i n s ２(t ２)(c o s (θ１)s i n (θ３)－c o s (θ２)s i n (θ２)s i n (θ３))＋r z s i n s １(t １)(c o s (θ１)s i n (θ２))＋x ０,７３７１第８期㊀㊀㊀㊀㊀㊀㊀马宇科,等:两栖球形机器人的路径规划策略. All Rights Reserved.r x c o s s １(t １)c o s s ２(t ２)(－c o s (θ１)c o s (θ２)s i n (θ３)－s i n (θ１)c o s (θ３))＋r yc o s s １(t １)s i n s ２(t ２)(s i n (θ１)c o s (θ２)s i n (θ３)－c o s (θ１)s i n (θ３))＋r z s i n s １(t １)s i n (θ２)s i n (θ３)＋y ０,r x c o s s １(t １)c o s s ２(t ２)c o s (θ１)s i n (θ２)＋r yc o s s １(t １)s i n s ２(t ２)s i n (θ１)s i n (θ２)＋r z s i n s １(t １)c o s (θ２)＋z ０ɤ０．(２６)㊀㊀在方程中,－π/２ɤt １ɤπ/２,０ɤt ２ɤ２π.在非线性规划问题中,目标函数必须具有下限的最小值.目标设置必须使全局最小值可变,二次函数的目标函数表示为:f (x ０,y ０,z ０,θ１,θ２,θ３)＝w ((x ０－x ０g )２＋(y ０－y ０g )２＋(z ０－z ０g )２)＋(１－w )((θ１－θ１g )２＋(θ２－θ２g )２＋(θ３－θ３g )２)．(２７)㊀㊀其最优化点的坐标为(x ０g ,y ０g ,z ０g ),最优化角度为(θ１g ,θ２g ,θ３g ),并且满足方程式:m i n f (x ０,y０,z ０,θ１,θ２,θ３)＝(x ０g ,y ０g ,z ０g ,θ１g ,θ２g ,θ３g )＝０．(２８)㊀㊀在前面的公式中,w 表示用于调整空间位置(x ０－x ０g )２＋(y ０－y ０g )２＋(z ０－z ０g )２和机器人空间方向(θ１－θ１g )２＋(θ２－θ２g )２＋(θ３－θ３g )２之间的相对关系的权重,当w ＝１时计算空间位置.当w ＝０．５时,空间位置和空间的权重方向必然相等.５㊀实验及结果分析５．１㊀仿真实验为验证两种基于路径规划的G C O P 和S Q P在水下两栖机器人的路径规划过程中的有效性,使用MA T L A B 设置了两种算法,从初始起始坐标O l ＝(－２００,－２００,－２００)到达目标O u ＝(６００,６００,６００)的仿真实验的场景范围.场景空间的长㊁宽和高为６００c m 的立方体形状.基于S Q P 算法的不等式O l ɤO ɤO u 通过四个参数确保生成的路径在场景内,坐标分布分别在三维平面上的O s ＝(x ０s ,y ０s ,z ０s ),θs ＝(θ１s ,θ１s ,θ１s ),O g ＝(x ０g ,y ０g ,z ０g )和θg ＝(θ１g ,θ２g ,θ３g ).GC O P 算法的初始时刻设定t ＝０,Δv ＝０．０００１,起点坐标为:(x ０s ,y０s ,z ０s ,θ１s ,θ２s ,θ３s )＝(－２００,－２００,－２００,０,０,０),(２９)(x ０g ,y ０g ,z ０g ,θ１g ,θ２g ,θ３g )＝(５００,５００,５００,０,０,０)．(３０)㊀㊀目标函数定义为:f ＝ω[(x ０－５００)２＋(y ０－５００)２＋(z ０－５００)２]＋(１－ω)(θ２１＋θ２２＋θ２３)．(３１)㊀㊀如果满足等式,则该坐标点不会与球形障碍物碰撞.在模拟实验中设置了４个球形障碍物,为确保基于两种算法的准确性.４个障碍物的坐标和方程定义为:(x －２００)２＋(y －２００)２＋(z －２００)２＝５０２,x ２＋(y －２００)２＋(z －２００)２＝３０２,(x －４００)２＋(y －２００)２＋(z －２００)２＝３０２,(x －２００)２＋y ２＋(z －２００)２＝３０２．(３２)㊀㊀球形机器人的参数为(r x ,r y ,r z )是对象的几何间隔(s １＝１,s ２＝１．５表示机器人的形状是球形):r x ＝５,r y ＝４,r z ＝３,s １＝１,s ２＝１．５．(３３)㊀㊀图５为仿真结果(彩图见期刊电子版),在起点和目标点之间有４个障碍.粉色球和灰色球表示不同算法的两栖机器人的运动轨迹.３个蓝色球体和１个红色球体分别代表障碍物.机器人从起始位置到目标位置经过４个障碍物,两种算法比较,S Q P 算法在路径规划上更加合理,并在３个采样点处(黄色圆点)离障碍８３７１㊀㊀㊀㊀㊀光学㊀精密工程㊀㊀㊀㊀㊀第２８卷㊀. All Rights Reserved.图５㊀两种路径规划算法仿真分析F i g．５㊀S i m u l a t i o na n a l y s i so f t w o p a t h p l a n n i n g a lＧg o r i t h m s物始终保持了安全距离.但G C O P算法选择的路径在坐标点(－１００,１９０,３３２．５)处离障碍物较近,如机器人发生小角度偏移,有发生碰撞的危险.所以S Q P算法比G C O P算法在安全路径规划的路径控制方面更加有效.而在达到目标坐标位置上,两种算法的误差Δd＝１６７．５m m,因此S Q P算法在水下路径规划上更具有优势.５．２㊀水下实验为了进一步验证文章所提出算法的有效性,本文设计了基于S Q P算法的水下测试实验,实验是在长１５００m m,宽为１０００m m,高度为８００m m的封闭水池环境下进行,如图６所示.图中设置了跟仿真环境相匹配的４个球形障碍物,分别设计障碍物的固定坐标位置.机器人从起点出发,激光测距模块和图像采集传感器实时采集障碍物在水中的坐标,并实时调整机器人的运动轨迹,按算法程序中设定的最佳路径移动到目标位置.图７(a)是t＝０s时刻机器人的初始位置,箭头标明了规划的机器人最优路径轨迹.图７(b)~７(i)是机器人从t＝０s移动至t＝１５s的实际运动轨迹.在实验过程中,采集６个图６㊀球形机器人避障实验环境F i g．６㊀E x p e r i m e n t a l s e t u p f o ra v o i d i n g o b s t a c l e so fr o b ot图７㊀S Q P路径规划算法的实验图片F i g．７㊀P h o t o e s o f p a t h p l a n n i n g b y S Q Pa l g o r i t h m 不同的时间点,对机器人y轴和z轴方向的位移变化曲线进行采样,从而判断机器人在最佳路径选择上的稳定性和可靠性.从图８可以看出,机器人分别在第二个和第三个采样点偏移误差较大,误差值达到２０m m,在其余４个采样点误差小于１０m m,这是因为机器人在第二个到第三个采样点主要是对路径的选择阶段,从而影响了机器人的运动形态.机器人的运动轨迹如图９所示.９３７１第８期㊀㊀㊀㊀㊀㊀㊀马宇科,等:两栖球形机器人的路径规划策略. All Rights Reserved.图８㊀球形机器人y轴和z轴运动方向误差F i g．８㊀K i n e m a t i c e r r o r s o f r o b o t i n yＧa x i s a n d zＧa x i s图９㊀球形机器人的最佳路径轨迹F i g．９㊀O p t i m a l p a t h t r a j e c t o r y o f s p h e r i c a l r o b o t ６㊀结㊀论㊀㊀本文提出了两种基于路径规划的算法(G C O P和S Q P),通过设置４个不同尺寸的球形障碍物使两栖球形机器人可以通过视觉伺服传感器实现避障功能并选择最佳路径.在实验中,设置３个采样点对两种路径规划算法进行评估,基于G C O P算法在(－１００,１９０,５００)和(－５,２００,３４５．８)处距离障碍物较近;而基于S Q P算法在相对应的采集点处坐标分别为(－１００,１９０,５００)和(－１６０,１９０,５００),相对处于离障碍物较为安全和合理的位置.在终点坐标位置,基于G C O P算法到达预计终点坐标为(５００,５００,３３２．５),偏离了预先设定的终点坐标,而基于S Q P算法到达终点的坐标为(５００,５００,５００),基本达到预先路径规划的要求.通过３个坐标点的数据显示分析,两个采样点的坐标偏差最优化是要保证距离障碍物的距离在合理范围之内,S Q P算法在两个采集点处的障碍物距离更加合理.在第三个终点采样点,两种算法的机器人运动轨迹偏差为１６７．５m m.实验表明,对于两栖水下机器人的水下运动控制,基于S Q P的路径规划算法比G C O P的路径规划算法更具有优越性.未来的研究工作会在机械设计和控制方法上持续改进,以实现多机器人的水下多机协作控制与路径规划的最优控制.参考文献:[１]㊀Z H E N G L,G U OSX,G U SX．T h ec o m m u n i c aＧt i o na n d s t a b i l i t y e v a l u a t i o no f a m p h i b i o u s s p h e r i c a l r o b o t s[J]．M i c r o s y s t e m T e c h n o l o g i e s,２０１９,２５(７):２６２５Ｇ２６３６．[２]㊀郭书祥,孙珊,郭健．新型仿生水下子母机器人系统设计[J]．控制与决策,２０１９,３４(５):１００４Ｇ１０１０．G U OS H X,S U N S H,G U OJ．D e s i g no f an o v e lb i o m i m e t ic u nde r w a t e r m o t h e rＧs o n r o b o t s y s t e m[J]．C o n t r o la n d D e c i s i o n,２０１９,３４(５):１００４Ｇ１０１０．(i nC h i n e s e)[３]㊀Z H E N GL,G U OSX,P I A O Y,e t a l．．C o l l a b o r aＧt i o na n dt a s k p l a n n i n g o ft u r t l eＧi n s p i r e d m u l t i p l ea m p h ib i o u ss p h e r ic a lr o b o t s[J]．M i c r o m a c h i n e s,２０２０,１１(１):７１．[４]㊀于涛,孙汉旭,赵伟,等．一种球形滚动机器人的路径跟踪控制器设计[J]．计算机测量与控制,２０１９,２７(３):９１Ｇ９６．Y U T,S U N H X,Z HA O W,e t a l．．D e s i g no f ap a t h f o l l o w i n g c o n t r o l l e r f o ras p h e r i c a l r o l l i n g r oＧb o t[J]．C o m p u t e r&C o n t r o l o f C o m p u t e r,２０１９,２７(３):９１Ｇ９６．(i nC h i n e s e)[５]㊀杨红彪．水下球形机器人的关键技术研究[D]．哈尔滨:哈尔滨工程大学,２０１８:１５Ｇ１９．Y A N G H B．R e s e a r c h o n t h eK e y T e c h n o l o g i e s o f０４７１㊀㊀㊀㊀㊀光学㊀精密工程㊀㊀㊀㊀㊀第２８卷㊀. All Rights Reserved.t h e U n d e r w a t e r S p h e r i c a l R o b o t[D]．H a r b i n:H a r b i n E n g i n e e r i n g U n i v e r s i t y,２０１８:１５Ｇ１９．(i nC h i n e s e)[６]㊀G U OJ,L IC Y,G U OSX．An o v e l s t e p o p t i m a l p a t h p l a n n i n g a l g o r i t h mf o r t h e s p h e r i c a lm o b i l e r oＧb o t b a s e do n f u z z yc o n t r o l[J]．I E E EA c c e s s,２０２０,８:１３９４Ｇ１４０５．[７]㊀L I U X H,Z HA N G D G,Y A N H R,e t a l．．A n e wa l g o r i t h m o f t h eb e s t p a t hs e l e c t i o nb a s e do nm a c h i n el e a r n i n g[J]．I E E E A c c e s s,２０１９,７:１２６９１３Ｇ１２６９２８．[８]㊀Y U A NJY,WA N G HJ,L I NCJ,e t a l．．An o v e lG R UＧR N N n e t w o r k m o d e l f o rd y n a m i c p a t h p l a nＧn i n g o fm o b i l er o b o t[J]．I E E E A c c e s s,２０１９,７:１５１４０Ｇ１５１５１．[９]㊀B A E H,K I M G,K I MJ,e t a l．．M u l t iＧr o b o t p a t h p l a n n i n g m e t h o du s i n g r e i n f o r c e m e n t l e a r n i n g[J]．A p p l i e dS c i e n c e s,２０１９,９(１５):３０５７．[１０]㊀A L I M A H,MA I L A H M．P a t h p l a n n i n g a n dc o n t r o l o fm o b i l e r o b o t i n r o ade n v i r o n m e n t s u s i n gs e n s o r f u s i o na n da c t i v ef o r c ec o n t r o l[J]．I E E ET r a n s a c t i o n s o nV e h i c u l a rT e c h n o l o g y,２０１９,６８(３):２１７６Ｇ２１９５．[１１]㊀Y A OZ,Z HA N G W M,S H IY L,e t a l．．R e i nＧf o r c e d R i m J u m p:t a ng e n tＧb a s e dsh o r t e s tＧp a t h p l a nＧn i n g f o r t w oＧd i m e n s i o n a lm a p s[J]．I E E E T r a n sＧa c t i o n s o nI n d u s t r i a lI n f o r m a t i c s,２０２０,１６(２):９４９Ｇ９５８．[１２]㊀Z H E N GL,P I A O Y,MA Y K,e t a l．．D e v e l o pＧm e n t a n d c o n t r o l o f a r t i c u l a t e da m p h i b i o u s s p h e r iＧc a l r o b o t[J]．M i c r o s y s t e mT e c h n o l o g i e s,２０２０,２６(５):１５５３Ｇ１５６１．[１３]㊀郑亮,朴燕,马宇科．非线性反馈和二次型调节器在两栖机器人中的应用[J]．光学精密工程,２０１９,２７(１０):２１９９Ｇ２２０６．Z H E N G L,P I A O Y,MA Y K,A p p l i c a t i o no fn o n l i n e a r f e e d b a c ka n d q u a d r a t i c r e g u l a t o r s i na mＧp h i b i o u s r o b o t s[J]．O p t．P r e c i s i o nE n g．,２０１９,２７(１０):２１９９Ｇ２２０６．(i nC h i n e s e)[１４]㊀张旭,曾祥鑫,郎博．基于控制变量参数化方法的自由漂浮空间机器人路径规划[J]．光学精密工程,２０１９,２７(２):３７２Ｇ３７８．Z HA N G X,Z E N G XX,L A N GB．P a t h p l a n n i n go f f r e eＧf l o a t i n g s p a c e r o b o t b a s e do nc o n t r o l v a r i aＧb l e p a r a m e t e r i z a t i o n m e t h o d[J]．O p t．P r ec i s i o nE n g．,２０１９,２７(２):３７２Ｇ３７８．(i nC h i n e s e) [１５]㊀Y UJZ,L I UJC,WUZX,e t a l．．D e p t h c o n t r o l o fab i o i n s p i r e dr o b o t i cd o l p h i nb a s e do ns l i d i n gＧm o d ef u z z y c o n t r o l m e t h o d[J]．I E E E T r a n s a cＧt i o n so n I n d u s t r i a l E l e c t r o n i c s,２０１８,６５(３):２４２９Ｇ２４３８．[１６]㊀Z HA N GS W,Q I A N Y,L I A OP,e t a l．．D e s i g na n d c o n t r o l o f a na g i l e r ob o t ic f i s hw i t h i n t e g r a t i v eb i o m i m e t i cm ec h a n i s m s[J]．I E E E/A S M ET r a n sＧa c t i o n s o nM e c h a t r o n i c s,２０１６,２１(４):１８４６Ｇ１８５７．[１７]㊀曾祥鑫,关英姿,晏卓,等．自由漂浮空间机器人最小基座扰动路径规划[J]．光学精密工程,２０１７,２５(１２z):６７Ｇ７３．Z E N G XX,G U A N YZ,Y A NZ H,e t a l．．P a t hp l a n n i n g f o r m i n i m i z i n g b a s ed i s t u r b a n c eo ff r e eＧf l o a t i ng s p a c er o b o t[J]．O p t．P r e c i s i o n E n g．,２０１７,２５(１２z):６７Ｇ７３．(i nC h i n e s e)[１８]㊀陈原,何淑垒,姜媛,等．轮Ｇ腿复合式移动机器人球面并联腿机构的动力学模型[J]．光学精密工程,２０１９,２７(８):１８００Ｇ１８１０．C H E N Y,H ES H L,J I A N G Y,e t a l．．D y n a m i cm o d e l o f s p h e r i c a l p a r a l l e lm e c h a n i s mf o rw h e e lＧl e gh y b r i d m o b i l er o b o t[J]．O p t．P r e c i s i o n E n g．,２０１９,２７(８):１８００Ｇ１８１０．(i nC h i n e s e)[１９]㊀WA N G W,D A IX,L IL,e t a l．．T h r e eＧd i m e nＧs i o n a lm o d e l i n g o f a f i nＧa c t u a t e dr o b o t i c f i s h w i t hm u l t i m o d a l s w i m m i n g[J]．A S M ET r a n s a c t i o n s o nM e c h a t r o n i c s,２０１８,２３(４):１６４１Ｇ１６５２．[２０]㊀WUZX,L I UJC,Y UJZ,e t a l．．D e v e l o p m e n t o f a n o v e l r o b o t i c d o l p h i n a n d i t s a p p l i c a t i o n t ow aＧt e r q u a l i t y m o n i t o r i n g[J]．A S M ET r a n s a c t i o n s o nM e c h a t r o n i c s,２０１７,２２(５):２１３０Ｇ２１４０．[２１]㊀徐彦伟,刘明明,刘洋,等．基于信息融合的机器人薄壁轴承故障智能诊断[J]．光学精密工程,２０１９,２７(７):１５７７Ｇ１５９２．X U Y W,L I U M M,L I U Y,e t a l．．I n t e l l i g e n tf a u l t d i ag n o s i s o f thi nw a l l b e a r i n g b a s e do n i n f o rＧm a t i o n f u s i o n[J]．O p t．P r e c i s i o nE n g．,２０１９,２７(７):１５７７Ｇ１５９２．(i nC h i n e s e)[２２]㊀刘涛,尹仕斌,任永杰,等．机器人工具坐标系自动校准方法[J]．光学精密工程,２０１９,２７(３):６６１Ｇ６７０．１４７１第８期㊀㊀㊀㊀㊀㊀㊀马宇科,等:两栖球形机器人的路径规划策略. All Rights Reserved.L I U T ,Y I NS H B ,R E N YJ ,e t a l ．．A u t o m a t i c c a l i b r a t i o no fr o b o tt o o lc e n t e rf r a m er o b o tt o o l c e n t e r f r a m e [J ]．O p t ．P r e c i s i o nE n g ．,２０１９,２７(３):６６１Ｇ６７０．(i nC h i n e s e)作者简介:㊀马宇科(１９９６－),男,吉林通化人,主要从事机器人机械结构设计和机器人建模相关方向的研究.E Ｇm a i l :f r a n k Ｇm a １２０８１６＠１６３．c o m通讯作者:㊀郑㊀亮(１９８２－),男,吉林吉林人,博士研究生,讲师,２００６㊁２０１０年于长春理工大学分别获得学士㊁硕士学位,２０１５年至今香川大学(日本)在读博士,主要从事机器人控制学㊁水下机器人建模与仿真系统的研究.E Ｇm a i l :s １８d ５０５＠s t u ．k a g a w a Ｇu ．a c ．j p２４７１㊀㊀㊀㊀㊀光学㊀精密工程㊀㊀㊀㊀㊀第２８卷㊀. All Rights Reserved.。

(1)带约束的非线性优化问题解法小结考虑形式如下的非线性最优化问题(NLP):min f(x)「g j (x )“ jI st 彳 g j (x)=O j L其 中， ^(x 1,x 2...x n )^ R n， f : R n > R ， g j :R n > R(j I L) ， I 二｛1,2,…m ｝， L ={m 1,m 2...m p}。

上述问题(1)是非线性约束优化问题的最一般模型，它在军事、经济、工程、管理以 及生产工程自动化等方面都有重要的作用。

非线性规划作为一个独立的学科是在上世纪 50年 代才开始形成的。

到70年代，这门学科开始处于兴旺发展时期。

在国际上，这方面的专门性 研究机构、刊物以及书籍犹如雨后春笋般地出现，国际会议召开的次数大大增加。

在我国， 随着电子计算机日益广泛地应用，非线性规划的理论和方法也逐渐地引起很多部门的重视。

关于非线性规划理论和应用方面的学术交流活动也日益频繁，我国的科学工作者在这一领域 也取得了可喜的成绩。

到目前为止，还没有特别有效的方法直接得到最优解，人们普遍采用迭代的方法求解： 首先选择一个初始点，利用当前迭代点的或已产生的迭代点的信息，产生下一个迭代点，一 步一步逼近最优解，进而得到一个迭代点列，这样便构成求解( 1)的迭代算法。

利用间接法求解最优化问题的途径一般有：一是利用目标函数和约束条件构造增广目标 函数，借此将约束最优化问题转化为无约束最优化问题，然后利用求解无约束最优化问题的 方法间接求解新目标函数的局部最优解或稳定点，如人们所熟悉的惩罚函数法和乘子法；另 一种途径是在可行域内使目标函数下降的迭代点法，如可行点法。

此外，近些年来形成的序 列二次规划算法和信赖域法也引起了人们极大的关注。

在文献［1］中，提出了很多解决非线性 规划的算法。

下面将这些算法以及近年来在此基础上改进的算法简单介绍一下。

1. 序列二次规划法序列二次规划法，简称SQ 方法.亦称约束变尺度法。

序列二次规划法求解一般线性优化问题:12min (x)h (x)0,i E {1,...,m }s.t.(x)0,i {1,...,m }i i f g I =∈=⎧⎨≥∈=⎩ (1.1) 基本思想：在每次迭代中通过求解一个二次规划子问题来确定一个下降方向，通过减少价值函数来获取当前迭代点的移动步长，重复这些步骤直到得到原问题的解。

1.1等式约束优化问题的Lagrange-Newton 法考虑等式约束优化问题min (x)s.t.h (x)0,E {1,...,m}j f j =∈=(1.2)其中:,n f R R →:()n i h R R i E →∈都为二阶连续可微的实函数. 记1()((),...,())T m h x h x h x =. 则(1.3)的Lagrange 函数为： 1(,)()*()()*()mT i i i L x u f x u h x f x u h x ==-=-∑（1.3）其中12(,,...,)T m u u u u =为拉格朗日乘子向量。

约束函数()h x 的Jacobi 矩阵为：1()()((),...,())T T m A x h x h x h x =∇=∇∇.对（1.3）求导数，可以得到下列方程组：(,)()A()*(,)0(,)()T x u L x u f x x u L x u L x u h x ∇⎡⎤⎡⎤∇-∇===⎢⎥⎢⎥∇-⎣⎦⎣⎦（1.4）现在考虑用牛顿法求解非线性方程（1.4）.(,)L x u ∇的Jacobi 矩阵为：(,)()(,)()0T W x u A x N x u A x ⎛⎫-= ⎪-⎝⎭（1.5）其中221(,)L(,)()*()mxx iii W x u x u f x u h x ==∇=∇-∇∑是拉格朗日函数L(,)x u 关于x 的Hessen 矩阵.(,)N x u 也称为K-T 矩阵。

对于给定的点(,)k k k z x u =，牛顿法的迭代格式为：1k k k z z z +=+∆. 其中k k (d ,v )k z ∆=是线性方程组k k k k (,)()(x )A(x )u *()0(x )k k k k T T k k d W x u A x f A x v h ⎛⎫-⎛⎫-∇+⎛⎫= ⎪ ⎪ ⎪ ⎪-⎝⎭⎝⎭⎝⎭（1.6）的解。

不等式约束优化新型SQCQP 算法研究 刘 美 杏二○一四 年 六 月分类号O221.2密级公开UDC硕士学位论文不等式约束优化新型SQCQP算法研究刘美杏学科专业应用数学指导教师简金宝教授、唐春明教授论文答辩日期2014年5月24日学位授予日期答辩委员会主席刘焕文教授广西大学学位论文原创性和使用授权声明本人声明所呈交的论文，是本人在导师的指导下独立进行研究所取得的研究成果。

除已特别加以标注和致谢的地方外，论文不包含任何其他个人或集体已经发表或撰写的研究成果，也不包含本人或他人为获得广西大学或其它单位的学位而使用过的材料。

与我一同工作的同事对本论文的研究工作所做的贡献均已在论文中作了明确说明。

本人在导师指导下所完成的学位论文及相关的职务作品，知识产权归属广西大学。

本人授权广西大学拥有学位论文的部分使用权，即：学校有权保存并向国家有关部门或机构送交学位论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影印、缩印或其它复制手段保存、汇编学位论文。

本学位论文属于：□保密，在年解密后适用授权。

□不保密。

(请在以上相应方框内打”√”)论文作者签名：日期：指导教师签名：日期：作者联系电话：电子邮箱：不等式约束优化新型SQCQP算法研究摘要不等式约束优化是数学规划领域的一个重要分支,在经济计划、电网规划、实时控制、工程设计和交通运输等实际问题中有着相当广泛的应用.不等式约束优化研究的焦点在于探索设计各类快速有效、实用的数值优化方法.本学位论文针对不等式约束优化问题,借助序列二次约束二次规划(SQCQP)方法、罚函数法和积极识别集精确识别技术等思想对此类问题的新型求解算法展开研究.首先,提出了一个新的求解不等式约束优化问题的罚函数型全局收敛SQCQP算法.该算法初始点任意选取,每次迭代只需求解一个恒有最优解的凸二次约束二次规划(QCQP)子问题,并且采用积极识别集精确识别技术降低子问题的规模和计算成本.算法在没有函数凸性及Slater CQ等条件下实现了全局收敛性.此外,算法在数值测试过程中具有稳定性和有效性.其次,建立了一个新的快速收敛SQCQP算法.通过构造新型QCQP子问题,并设计适当的罚参数修正策略和新型线搜索,算法不仅能从任意初始点开始,而且能保证迭代点在有限步迭代后落入可行域.并在不需要线性无关约束规格(LICQ)、严格互补等较温和的条件下,证明了算法的弱全局收敛性、全局收敛性以及超线性收敛性.最后,通过一定规模的数值试验测试了算法的有效性.关键词：不等式约束优化序列二次约束二次规划新型线搜索算法积极识别集全局收敛性超线性收敛性RESEARCH ON NEW SQCQ P ALGORITHMS FORINEQUALITY CONSTRAINED OPTIMIZATIONABSTRACTInequality constrained optimization is one of the most important branch-es in thefield of mathematical programming,which is widely applied in prac-tical problems,such as economic plan,power network planning,real-time control,engineering design,transportation and so on.The focus of the in-equality constrained optimization research is to explore and design all kinds of quick,effective and practical numerical optimization methods.The the-sis studies new numerical algorithms for solving inequality constrained op-timization problems by means of the ideas of sequential quadratically con-strained quadratic programming(SQCQP)method,penalty function method and an accurate identification technology of active set.Firstly,a new penalty-function type globally convergent SQCQP algo-rithm for inequality constrained optimization problems is proposed.The al-gorithm can choose an initial iteration point arbitrarily,at each iteration only a convex quadratically constrained quadratic programming(QCQP)subprob-lem which always has an optimal solution needs to be solved and the scale of the subproblems and computational cost are reduced by employing the active set accurately identification technology.Without conditions such as the con-vexity of functions and Slater constraint qualification,global convergence of the algorithm is proved.In addition,the algorithm is stable and effective in the process of numerical tests.Secondly,a new fast convergent SQCQP algorithm is established.By constructing a new QCQP subproblem and designing a appropriate penal-ty parameter correction strategy as well as a new line search,the presented algorithm is not only able to begin with an arbitrary initial point,but also guarantees that all of the iterates are turned into feasible ones after afinite number of iterations.And without the linearly independent constraint quali-fication(LICQ)or the strict complementarity,the weakly global,global and superlinear convergence properties are obtained under relatively milder stly,the validity of the algorithm is tested through a certain scale of numerical experiments.KEY WORDS:inequality constrained optimization;sequential quadratically constrained quadratic programming;new line search;algorithm active iden-tification set;global convergence;superlinear convergence目录第1章绪论 (1)1.1研究背景及意义 (1)1.2国内外研究现状 (2)1.3本文研究内容与结构 (5)第2章理论基础 (6)2.1基础知识 (6)2.2积极识别集 (7)2.3本章小结 (8)第3章一个改进的全局收敛SQCQP算法 (10)3.1算法设计 (10)3.2全局收敛性分析 (14)3.3算法的数值试验及复杂度分析 (19)3.3.1数值试验 (19)3.3.2复杂度定性分析 (23)3.4本章小结 (23)第4章基于新型子问题和线搜索的超线性收敛SQCQP算法 (24)4.1算法设计 (24)4.2全局收敛性分析 (30)4.3强收敛性分析 (38)4.4收敛速度分析 (40)4.5算法的数值试验 (46)4.6本章小结 (48)结论与展望 (49)参考文献 (51)致谢 (56)攻读硕士学位期间概况 (57)第1章绪论1.1研究背景及意义最优化这一门学科凸显了广泛性与实用性两大特点,包含了非常丰富的研究内容,其中对基本理论及其快速有效算法的研究是必要的基础,而将之付诸于对实际问题的计算和应用则是学者们期望的最终目的.简单来说,最优化研究的问题可以归结为如何在适用的情形中找出最优的策略,其理论和方法在解决这些问题中发挥了巨大的作用,目前已被广泛应用于生产分配、油价配比、建筑规划、农业发展、金融服务、军事指挥等重要领域.因此,最优化理论和方法得到了迅速发展.最优化有较小的研究分类,无约束优化和约束优化是从是否带约束来进行划分;而非线性约束优化这一分支则是约束优化根据函数的类型所作的进一步细分.在实际应用中,绝大多数的实际问题属于非线性约束优化问题．本学位论文研究如下非线性不等式约束优化问题f0(x)minx∈R n(1.1)s.t.f i(x)≤0,i∈I△={1,···,m},其中函数f i:R n→R,i∈{0}∪I均一阶连续可微.随着科学技术飞速发展和工程技术现代化,各类具有一定实际背景的问题变得更加复杂,规模不断扩大,数据也要求更加精密,使得经济效果与一个决策的好坏密切相关.因此,要在经济迅猛发展的今天取得更好的效益就必须从优解决问题,这就为最优化理论和算法的发展提供了必要性,同时也为不等式约束优化的研究奠定了基础.目前,在日常生活中不等式约束优化方法同样有着广泛的应用,如工程设计、阻塞管理、政府决策、实时电价计算、最优控制等,且其研究成果也越来越受到人们的重视.因而,对不等式约束优化方法的研究一直是最优化领域中一个十分常见且倍具发展空间的课题,特别是针对此类优化问题设计的快速有效算法,这对实际问题的指导有着相当重要的理论意义和实用价值.鉴于此,本学位论文对不等式约束优化问题进行深入研究,进而建立求解此类问题的有效算法,并具体阐述算法的收敛性质及收敛速度.1.2国内外研究现状目前有很多方法可应用于求解非线性不等式约束优化问题(1.1),如强次可行方向法、内点法、梯度投影法、可行方向法、罚函数法、信赖域法、QP-free方法等,其中序列二次规划(SQP)方法是目前优化领域被公认为求解问题(1.1)的最有效方法之一.其具有收敛性质良好、收敛速度快等优点,特别适用于求解中小规模非线性优化问题.在过去的三四十年,前人对SQP方法的研究进行了极大的完善,现在该类方法已获得丰富的发展成果,见文献[1].然而,在遇到非线性程度较高或者规模较大的优化问题时,如经典的人造卫星轨道问题[2],SQP方法可能会收敛性质较差,收敛速度缓慢,甚至整个进程会失败.而且,在每一次迭代,除了求解获得主搜索方向的二次规划(QP)子问题外,为克服Maratos效应[3],还需额外求解一个甚至多个QP子问题以获得高阶修正方向,计算量较大.这些都限制了SQP方法在优化问题中的应用.为此,一些学者提出了一类序列二次约束二次规划(SQCQP)方法.SQCQP方法属于一种极具潜力的非线性规划算法,从优化问题的函数来看,其目标和约束均为二次实函数.在每次迭代时,SQCQP方法相应地只有一个二次约束二次规划(QCQP)子问题需要求解,并且Maratos效应可以避免而无需任何修正方向,这对于SQP方法而言无疑是一大难题.另一方面,可注意到整个QCQP子问题是原问题的高阶近似,因此,其近似程度更精确更优于SQP方法的QP子问题,从而SQCQP方法更适合于求解一些非线性程度较高的问题.从数值计算的角度来看,虽然QCQP子问题比QP子问题复杂,但是由于凸的QCQP子问题可以转化为一个二阶锥规划问题[4–6],进而用内点法高效求解,见文献[7–9].因此,SQCQP方法突破了数值计算这一困难.而且,从数值试验结果来看,对某些实际问题,SQCQP方法在迭代过程中不管是迭代次数还是运行时间均要显著少于SQP方法.实际上,SQCQP方法早在上世纪八九十年代已开始研究并用于求解非线性优化问题,见文献[10–12].但当时由于无法克服求解QCQP子问题的困难而没有得到较好的发展.现如今,许多有效的技术和工具已被成功应用于求解QCQP子问题,如内点法、半定规划松弛法[13,14]、直接法[15–19]等,使得SQCQP方法受到广泛重视和深入研究,可见文献[20–36].其研究类型主要有:罚函数型SQCQP算法[20,21],可行及强次可行SQCQP算法[23–26],摄动型SQCQP算法[27],局部收敛的SQCQP算法[28–30]等.针对问题(1.1)的目标和约束函数均为凸函数的情形,文献[20]在优化过程中利用控制参数来调节凸QCQP子问题的相容性,采用l1罚函数作为效益函数.加之Slater 约束规格,并考虑强二阶充分条件,论证了算法的收敛性质和收敛速度.但是涉及到一个Slater点(即严格内点),其不可避免地会使得计算量很大,耗时较多.随后l∞罚函数被使用到SQCQP方法上.文献[21]进一步对文献[20]进行改进,其考虑如下QCQP 子问题min (d,t)∈R n+1∇f0(x k)T d+12d T G k0d+βk ts.t.f i(x k)+∇f i(x k)T d+12d T G k i d≤t,i∈I k,t≥0,(1.2)其中t是一个额外变量,βk>0是罚参数,矩阵G k0正定,G k i(i∈I k)半正定,且分别为问题(1.1)的目标和约束函数Hesse阵的近似,指标集I k满足I(x k)⊆I k⊆I,I(x k)={i∈I:f i(x k)=ϕ(x k)},ϕ(x k)=max{0;f i(x k),i∈I}.(1.3)该方法降低了目标函数凸性及约束函数二阶信息的要求从而得到良好的全局收敛性质,并且无需计算一个Slater点,同样具有二次收敛性.然而,对于满足关系(1.3)的指标集I k,文献[21]并没有给出具体的办法,而且在收敛性分析中,需要假设当k充分大时I k≡I,这导致子问题(1.2)与问题(1.1)的规模相当.现在这种方法还有待进一步研究以实现整个优化过程更加合理.需要指出的是,上述两个罚函数型方法对原问题皆有凸性要求,为减弱这一条件,文献[22]提出了一个以新型增广Lagrangian函数为效益(线搜索)函数的SQCQP算法,其在QCQP子问题的目标和约束中分别引入二次项和线性项人工变量,以解决QCQP 子问题相容性这一难题.由于罚函数型SQCQP算法可能产生不可行的迭代点和近似解,从而不擅于处理那些需要严格保持可行性的实际问题.鉴于此,文献[23]借助可行SQP方法思想提出了一个可行SQCQP算法,这种方法无需目标和约束函数的凸性,而且产生可行的迭代点.但缺点是算法需要一个初始可行迭代点,计算复杂.文献[24]将该模松弛型可行方向法进一步发展推广,但不同的是,这里考虑求解带简单二次约束的QCQP子问题.鉴于强次可行方向法有着良好的发展成果,结合此思想,文献[25]提出了一个新的SQCQP方法来完成整个优化过程,其研究如下QCQP子问题min (z,d)∈R n+1γ0z+12d T G k0ds.t.∇f0(x k)T d≤γ0z+γϕθk,f i(x k)+∇f i(x k)T d+12d T G k i d≤γiσk z,i∈I−k,f i(x k)+∇f i(x k)T d+12d T G k i d≤γiσk z−εz2+ϕk,i∈I+k,1 2‖d‖2≤cσ2τk,(1.4)其中G k0是对称正定阵,G ki(i∈I)是对称半正定阵,γ,γi(i∈{0}∪I),θ,ε,c,σk>0,τ>1.该方法对初始点无特殊要求,且经有限步迭代能够产生可行迭代点,曾受到广泛重视,成为一种十分有效的算法.文献[26]进一步将强次可行方向法用于优化含简单二次约束的QCQP子问题并显示了较好的结果.SQCQP方法的一个难点在于:大多数算法在全局收敛性分析时均需要假设矩阵G k0(一致)正定,这样的条件太强,限制了该方法在优化问题中的应用.文献[27]通过适当的策略调整对QCQP子问题中的目标函数进行修正,从而减弱了对矩阵G k的要求,并且算法全局收敛性的性质仅仅需要矩阵的半正定性来分析得以实现.目前,还有一些SQCQP方法仅考虑到局部的收敛性质,其所需假设条件相对比较弱,如不需要假设矩阵的(半)正定性等.文献[28]研究了一类信赖域QCQP子问题,并应用MFCQ和一个二次增长条件保证算法具有局部超线性收敛性.此外,文献[29]研究了原始序列超线性收敛的充分必要条件为Dennis-Mor´e型条件,并结合线性无关、严格互补和二阶充分条件,论证了SQCQP算法具有原始对偶二次收敛性.而在文献[30]中,研究了一个二次近似模型的算法构造,在MFCQ和恒秩约束规格的基础上,进一步结合强二阶充分条件,该算法的收敛速度得以实现.至今,这一工作在优化问题中仍然十分适用.近年来,SQCQP方法的研究得到了进一步发展和推广应用.文献[31]提出了一个带简单非单调罚参数更新技术[37]的SQCQP算法,该算法采用工作集技术,计算速度快;无需函数凸性及Slater约束规格,收敛性较好.文献[32]研究的是凸规划问题的非精确SQCQP方法.文献[33]提出了求解光滑凸极小化问题的简单SQCQP方法,其具有良好的收敛性质.文献[34]将SQCQP方法进行发展推广并应用于不同的优化领域,如非线性规划、二阶锥规划、半无限规划等.文献[35]较早地应用SQCQP方法的思想研究无约束Minimax问题.后来,文献[36]提出了一种结合可行方向法和积极识别集的简单SQCQP方法求解约束Minimax问题,该方法通过求解线性方程组获得高阶修正方向,采用弱Mangasarian-Fromovitz约束规格保证方法有全局收敛性,并且超线性收敛性在上水平严格互补条件下进行了具体阐述.1.3本文研究内容与结构本学位论文通过结合SQCQP方法、罚函数法和积极识别集精确识别技术等思想,针对不等式约束优化问题研究其相应的新型数值求解算法.本文具体的结构组织如下:第一章是本论文的绪论部分,该部分以不等式约束优化问题为研究对象,首先对此类问题的研究背景及意义进行阐释,然后详细介绍SQCQP方法的国内外发展现状．第二章是给出本论文工作涉及到的基础知识以及积极识别集精确识别技术，为后续章节的具体研究作准备．第三章是对文献[21]提出的算法作进一步改进.针对非线性不等式约束优化问题,借助积极识别集修正QCQP子问题,使得问题规模大大降低,计算量也显著减小.采用l∞罚函数作为效益(线搜索)函数,进而具体设计本章的算法框架.最后,适当加以条件,算法实现了全局收敛性,并在数值测试中将算法与其他算法进行比较,本章算法具有一定的优越性.第四章是研究不等式约束优化的新型SQCQP方法.在优化过程中,建议引入线性项和二次项人工变量构造新的QCQP子问题,使用适当的罚参数修正策略,并采用一种罚函数法和两阶段法组合的新型线搜索技术.该方法初始点可任意选取,在每一次迭代只需求解一个恒有最优解的QCQP子问题,并且有限步后迭代点均落入可行域.此外,可适当选取相应于子问题的约束指标集,如积极识别集或全部的约束指标,来研究方法的适用范围,有助于求解大规模的优化问题.算法具有弱全局、全局以及超线性收敛性,数值结果说明了算法的有效性.最后一部分是回顾、总结本学位论文的工作以及提出后续需要研究的问题．第2章理论基础为便于后续章节的分析研究,本章给出论文中涉及到的基础知识以及积极识别集精确识别技术,也可查阅、参考相关文献[38,39,45]．2.1基础知识对∀x∈R n,定义问题(1.1)的可行集和拉格朗日(Lagrange)函数为ℱ={x∈R n:f(x)≤0},f(x)=(f i(x),i∈I),L(x,µ)=f0(x)+∑︀i∈Iµi f i(x).下面介绍一些数学符号、基本定义和重要结论,这些将在后面的分析中用到.定义2.1[38]设向量x=(x1,x2,x3,···,x n)T∈R n,p≥1,向量x的l p范数定义为‖x‖p=(︃n∑︁i=1|x i|p)︃1p.特别地‖x‖1=n∑︀i=1|x i|,(l1范数),‖x‖△=‖x‖2=(︂n∑︀i=1|x i|2)︂12,(l2范数).定义2.2[38]设x*∈ℱ,若存在向量µ*=(µ*i,i∈I)∈R m,使得∇f0(x*)+∑︀i∈Iµ*i∇f i(x*)=0,f i(x*)≤0,µ*i f i(x*)=0,µ*i≥0,i∈I,(2.1)成立,则称x*为问题(1.1)的一个Karush-Kuhn-Tucker(KKT)点,并称µ*为相应的KKT乘子或Lagrange乘子.定义2.3[39]若向量x,y∈R n为两个无穷小量,(1)如‖y‖‖x‖→0,则称y为比x高阶的无穷小量,记为‖y‖=o(‖x‖)或y=o(‖x‖);(2)如‖y‖‖x‖→1,则称y与x是等价无穷小量,记为‖y‖∼‖x‖或y∼x;(3)如存在常数M>0,使得‖y‖≤M‖x‖,则记‖y‖=O(‖x‖)或y=O(x).定义2.4[39]设Ω为问题(1.1)的满足一定条件的解集(如KKT点,局部解等),由求解问题(1.1)的迭代算法产生点列{x k},(1)如对于任意的或满足一定可行性的初始迭代点x0∈R n,序列{x k}至少存在一个聚点x*∈Ω,则称该算法在解集Ω内是弱全局收敛的;(2)如对于任意的或满足一定可行性的初始迭代点x0∈R n,均能保证序列{x k}的任意聚点x*∈Ω,则称该算法在解集Ω内是全局收敛的;(3)如对于任意的或满足一定可行性的初始迭代点x0∈R n,存在x*∈Ω,使得limk→∞x k=x*,则该算法在解集Ω内是强收敛的.定义2.5[39]设算法产生点列{x k}收敛于x*,(1)若点列满足lim k→∞‖x k+1−x*‖‖x k−x*‖=0,则称算法是超线性收敛的;(2)若点列满足‖x k+1−x*‖=O(‖x k−x*‖·‖x k−1−x*‖),则称算法是强两步二次收敛的.2.2积极识别集此处介绍本学位论文用到的一种重要技术—–积极识别集精确识别技术.积极识别集精确识别技术的特点在于:考虑定义起作用约束的一个工作集(有效的估量),使得优化问题因仅包含与工作集相应的约束而得到改进,从而简化算法的设计.此外,当迭代点充分接近KKT点时,这一技术能够在无严格互补条件下实现对起作用约束的精确估计.因此,该技术在优化过程中起着十分重要的作用,而且国内外学者对此研究给予了广泛关注和高度重视,见文献[39,第1.5节]及[40–45].其中,文献[45]在文献[42]的基础上,提出了一种更优更为精确的积极识别集.为便于分析,对问题(1.1)作如下基本假设,并设其在本学位论文中成立.假设2.6函数f i:R n→R,i∈{0}∪I均一阶连续可微.假设2.7Mangasarian-Fromovitz约束规格(MFCQ)成立,即对任意点x∈R n,存在相应的ˆd(x)∈R n,使得∇f i(x)Tˆd(x)<0,∀i∈I(x),其中I(x)={i∈I:f i(x)=ϕ(x)},ϕ(x)=max{0;f i(x),i∈I}.基于文献[45]和KKT条件(2.1),定义函数Φ:R n+m→R n+m和ρ:R n+m→[0,+∞)如下:Φ(x,µ)=⎛⎝∇x L(x,µ)min{−f(x),µ}⎞⎠,ρ(x,µ)=‖Φ(x,µ)‖12,(2.2)其中∇x L(x,µ)=∇f0(x)+∑︁i∈Iµi∇f i(x),min{−f(x),µ}=(min{−f i(x),µi},i∈I).显然,(x,µ)是问题(1.1)的KKT点对当且仅当ρ(x,µ)=0,即ρ(x,µ)为问题(1.1)的最优识别函数.基于该识别函数ρ(x,µ),引入文献[45]的积极识别集:I(x,µ)={i∈I:f i(x)−ϕ(x)+ρ(x,µ)≥0}.(2.3) 2.3本章小结本章首先给出了与本学位论文密切相关的基础知识:l1(l2)范数、KKT条件、高阶(等价、同阶)无穷小量、弱全局收敛、全局收敛、强收敛、超线性收敛及强两步二次收敛的概念;其次,简单介绍本学位论文用到的一种有效技术—–积极识别集精确识别技术用以处理子问题.这些定义、结论及关键技术对于后续章节的分析非常重要．第3章一个改进的全局收敛SQCQP算法本章基于文献[21]的工作进行适当的改进从而建立了一个新的SQCQP算法．在每一次迭代,算法通过求解一个总有最优解的凸QCQP子问题获得搜索方向,并且应用积极识别集[45],子问题无需考虑全部的约束指标,只需考虑约束与工作集相应的指标,进而对子问题的规模起到很好的压缩作用,计算成本也得到有效控制.最后,对新算法的全局收敛性进行分析及其数值有效性进行试验.3.1算法设计对当前迭代点x k∈R n及相应的近似乘子µk(由算法上一次迭代产生),受启发于文献[21],考虑QCQP子问题(1.2),记由(2.3)产生的积极识别集为I k△=I(x k,µk),(3.1)并用其取代QCQP子问题(1.2)中的指标集I k,故本章算法和分析中的I k均指由(3.1)式所产生,不再赘述.设(d k,t k)是子问题(1.2)的最优解,由于(1.2)满足Slater约束规格,故(d k,t k)是子问题(1.2)的KKT点,即存在u kI k∈R|I k|及v k∈R,使得⎧⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎩∇f0(x k)+G k0d k+∑︀i∈I ku k i(︀∇f i(x k)+G k i d k)︀=0,βk−∑︀i∈I ku k i−v k=0,f i(x k)+∇f i(x k)T d k+12(d k)T G k i d k≤t k,u k i≥0,i∈I k,u k i(︀f i(x k)+∇f i(x k)T d k+12(d k)T G k i d k−t k)︀=0,i∈I k,t k≥0,v k≥0,t k v k=0.(3.2)为分析子问题(1.2)的重要性质,将之等价转化为R n中的非光滑无约束二次子问题min d∈R n ∇f0(x k)T d+12d T G k0d+βk t k(d),(3.3)其中,t k(d)=max{0;f i(x k)+∇f i(x k)T d+12d T G k i d,i∈I k}.(3.4)接着,对子问题(1.2)的良好性质作如下刻画.引理3.1设矩阵G k0对称正定,矩阵G ki(i∈I k)对称半正定,则(1)子问题(1.2)有唯一最优解,且最优解与KKT点等同;(2)如果(d k,t k)是子问题(1.2)的最优解,则t k=t k(d k);(3)(d k,t k=t k(d k))是子问题(1.2)的最优解当且仅当d k是问题(3.3)的最优解;(4)如果子问题(1.2)的最优解(d k,t k)=(0,0),则(x k,u k)是问题(1.1)的KKT点对,其中u k=(u k Ik ,0I∖Ik).证明：利用文献[39]的定理3.4.3和推论3.4.4,可知结论(1)、(2)、(3)成立. (4)设(d k,t k)=(0,0),由KKT条件(3.2)知,f i(x k)≤0,i∈I(x k)⊆I k.于是ϕ(x k)=0,即x k∈ℱ.令u k=(u k Ik ,0I∖Ik),结合(d k,t k)=(0,0)和KKT条件(3.2),立知(x k,u k)是问题(1.1)的KKT点对.对于问题(1.1)和与之相应的产生方向的QCQP子问题(1.2),本章采用如下的l∞罚函数作为效益(线搜索)函数:ψβ(x)=f0(x)+βϕ(x).(3.5)其中β>0是罚参数.基于上述分析,算法的框架构造如下.算法3.2步骤0.(初始化)选取初始点x0∈R n,初始乘子µ0∈R m,参数β0,δ1,δ2>0,α,θ∈(0,1),置k:=0.步骤1.(产生积极识别集)由(2.2)计算ρk△=ρ(x k,µk),通过(3.1)产生积极识别集I k.若ρk=0,则(x k,µk)是问题(1.1)的KKT点对,终止.步骤2.(计算搜索方向)选取对称正定阵G k0及对称半正定阵G ki(i∈I k),求解子问题(1.2)得到最优解(d k,t k)和相应的KKT乘子(u k Ik ,v k),令u k=(u k Ik,0I∖Ik).如果(d k,t k)=(0,0),则(x k,u k)是问题(1.1)的KKT点对,终止;否则,进入步骤3.步骤3.如果d k=0且t k>0,则令步长s k=1,进入步骤5;否则,进入步骤4.步骤4.(线搜索)令s k为序列{1,θ,θ2,···}中满足不等式ψβk (x k+sd k)≤ψβk(x k)+αs△k,(3.6)的最大(步长)值s,其中△k=∇f0(x k)T d k+12(d k)T G k0d k+βk(t k−ϕk),ϕk=ϕ(x k).步骤5.(更新)计算γk=min{‖u k‖1+δ1,‖d k‖−1}(d k=0时,记‖d k‖−1=+∞),按如下公式更新罚参数βk+1=⎧⎨⎩βk,若βk≥γk;βk+δ2,若βk<γk.(3.7)令x k+1=x k+s k d k,µk+1=u k,k:=k+1,返回步骤1.在算法3.2的框架下,罚函数的下降性见以下引理.引理3.3如果矩阵G k0对称正定,矩阵G ki(i∈I k)对称半正定,子问题(1.2)的解d k=0,则ψ′βk (x k;d k)≤△k≤−12(d k)T G k0d k<0,(3.8)其中ψ′βk (x k;d k)表示函数ψβk(x)在x k处沿d k的方向导数.证明：由文献[21]的命题3,矩阵G k0对称正定及G ki(i∈I k)对称半正定,可知ψ′βk (x k;d k)≤△k−12(d k)T G k0d k≤−(d k)T G k0d k−12∑︀i∈I ku k i(d k)T G k i d k−v kϕk≤−(d k)T G k0d k<0.(3.9)进而得到ψ′βk (x k;d k)≤△k,△k≤−12(d k)T G k0d k<0.接下来可得到算法3.2的适定性.引理3.4设假设2.6,2.7成立,则(1)如果d k=0,t k>0,则存在有限正整数p,使得d k+p=0,或(d k+p,t k+p)=(0,0);(2)如果d k=0,则当s>0充分小时,不等式(3.6)成立,从而算法3.2是适定的.证明：(1)(反证法)假设∀p>0,d k+p=0,t k+p>0.显然由步骤3知x k+p=x k.根据(3.4)得ϕk+p=t k+p(0)=t k+p=ϕk=t k>0.进而由KKT条件(3.2)知,v k+p=0,0<βk+p=∑︀i∈I k+p u k+pi.又因为‖d k+p‖−1=+∞,故γk+p=‖u k+p‖1+δ1=∑︁i∈I k+p u k+pi+δ1=βk+p+δ1>βk+p.于是,由(3.7)有,βk+p+1=βk+p+δ2,进而可得limp→∞‖u k+p‖1=limp→∞βk+p=+∞.另外,注意到t k+p=ϕk+p>0,由KKT条件(3.2)知,u k+pi=0,i∈I k+p∖I(x k+p).又I(x k)=I(x k+p)⊆I k+p,故由(3.2)有∇f0(x k)+∑︁i∈I(x k)u k+pi∇f i(x k)=0.(3.10)注意到{︁u k+pI(x k)/‖u k+pI(x k)‖1}︁∞p=1有界,不妨设其收敛到˜u kI(x k),(3.10)式两边同时除以‖u k+pI(x k)‖1,然后令p→∞,有∑︁i∈I(x k)˜u k i∇f i(x k)=0,˜u k i≥0,i∈I(x k),‖˜u kI(x k)‖1=1.这与假设2.7矛盾,故结论(1)成立.(2)由于d k=0,对充分小的正数s,结合(3.8),有ψβk (x k+sd k)=ψβk(x k)+sψ′βk(x k;d k)+o(s)≤ψβk(x k)+s△k+o(s)=ψβk(x k)+αs△k+(1−α)s△k+o(s)≤ψβk(x k)+αs△k.因此,算法3.2是适定的.3.2全局收敛性分析本小节在罚函数型线搜索下分析算法3.2的全局收敛性,首先给出以下假设条件.假设3.5矩阵序列{G k}和{G k i},i∈I k满足ρ1E⪯G k0⪯ρ2E,O⪯G k i⪯ρ2E,i∈I k,∀k,其中0<ρ1≤ρ2,A⪯B表示B−A是半正定阵,E为n阶单位阵,O为n阶零阵.假设3.6由算法3.2产生的点列{x k}及方向序列{d k}有界.为获得算法3.2的全局收敛性,作如下准备.引理3.7设假设2.6,2.7,3.5,3.6均成立,若d k j→0,x k j→x*,I kj≡ˆI,则t kj j→∞−→ϕ(x*).证明：由(3.4)及I(x k j)⊆I kj,可知t kj =t kj(d k j)→max{0;f i(x*),i∈ˆI}≤ϕ(x*).只需再证limj→∞t kj≥ϕ(x*).若ϕ(x*)=0,结论显然成立.若ϕ(x*)>0,则j充分大时,ϕkj >0,进而I(x k j)=/0.取i kj∈I(x k j)⊆I kj,由子问题(1.2)的约束条件,有t kj≥f ik j(x k j)+∇f ik j(x k j)T d k j+12(d k j)T G k ik jd k j=ϕkj+∇f ik j(x k j)T d k j+12(d k j)T G k ik jd k j→ϕ(x*).引理获证.引理3.8设假设2.6,2.7,3.5,3.6均成立,x*是序列{x k}给定的一个聚点,即存在指标集K,使得limk∈Kx k=x*.若x*是问题(1.1)的可行点,即ϕ(x*)=0,则(1)对充分大的k∈K,问题min d∈R n ∇f0(x k)T d+12d T G k0ds.t.f i(x k)+∇f i(x k)T d+12d T G k i d≤0,i∈I k,(3.11)有严格可行解,从而满足Slater约束规格,并且有唯一最优解,其与KKT点等同;设(p k,ωk Ik )是问题(3.11)的KKT点对,则当βk≥‖ωk Ik‖1时,(p k,0)是子问题(1.2)的唯一解.反之,如果(d k,0,u k Ik ,v k)是子问题(1.2)的KKT点对,则(d k,u k Ik)是问题(3.11)的KKT点对;(2)问题(3.11)的KKT点对序列{(p k,ωk Ik)}k∈K有界.证明：类似于文献[31]的引理3.2,可证引理成立.基于罚参数修正策略(3.7),下面引理表明罚参数最终可固定下来,且此时子问题(1.2)相应的乘子序列有界.引理3.9设假设2.6,2.7,3.5,3.6均成立,则存在正整数k0,使得βk≡βkβ,∀k≥k0,并且乘子序列{u k}有界.证明：(反证法)若{βk}不能固定,则根据(3.7),知βk→+∞,k→∞.进而,由其更新方法可知,关系式βk<γk=min{‖u k‖1+δ1,‖d k‖−1}发生无限次,故存在子列{k j},使得lim j→∞d k j=0,limj→∞‖u k j‖1=+∞.由序列{x k j}的有界性及I kj 选取的有限性,不妨设x k j→x*,I kj≡ˆI.首先证明x*是问题(1.1)的可行点,即ϕ(x*)=0.假设ϕ(x*)>0,故有I+*△= I+(x*)=/0.由KKT条件(3.2),得f i(x k j)+∇f i(x k j)T d k j+12(d k j)T G k j i d k j≤t kj,∀i∈ˆI.(3.12)对于i∈ˆI∖I+*,当j→∞时,不等式(3.12)左边的极限为f i(x*)(≤0),由引理3.7知不等式(3.12)右边的极限为ϕ(x*)(>0),从而当j充分大时,不等式(3.12)是严格的.于是,由(3.2),有u k ji =0,i∈ˆI∖I+*,故‖u k jˆI∩I+*‖1→∞,ˆI∩I+*=/0.另一方面,由(3.2)及u k jI+*∖ˆI=0,有∇f0(x k j)+G k j0d k j+∑︁i∈ˆI∩I+*u k j i(︁∇f i(x k j)+G k j i d k j)︁=0.。