（应用数学专业论文）非线性约束规划问题的算法研究.pdf

非线性约束规划问题的算法研究 摘要 非线性约束规划问题是最一般形式的非线性最优化问题，也是最优化研究中的 难点因此，本文就非线性约束规划问题的一些算法进行了研究对非线性约束规 划问题的研究方法一般有：可行方向法、拉格朗日一牛顿法、罚函数法、序n - 次规 划法、序列线性方程组法、信赖域法等，拉格朗日一牛顿法和序列二次规划法是其中 两种比较重要的算法，但将它们用于一般约束优化问题的情形研究较少如果在不 等式约束处理上采用有效集策略并结合可行方向法，将使得整个算法结构较为复 杂如果在线搜索上采用渐近式精确搜索，将使得运算量增大因而本文研究了求 解一般约束优化问题的拉格朗日一牛顿法，并利用a r m i j o 型线性搜索对拉格朗日一拟 牛顿法进行改进，同时借助于拉格朗日一牛顿法的结论和广义投影技术得到了一种混 合算法 本文的研究内容共分五章，各章的内容安排如下 第一章，介绍了非线性约束规划发展状况，对课题所研究的非线性约束规划问 题的各种算法的内部联系进行了阐述，介绍了一般约束规划问题的最优性条件，并 对各种非线性约束规划问题的收敛性以及超线性收敛条件进行了总结，对非线性约 束规划问题的研究背景、现状和工作做了说明第二章，把解决等式约束条件的拉 格朗日一牛顿法推广到一般约束问题情形，将一般约束规划问题的最优性条件化为线 性方程组来求解，在适当的假设条件下，得到了该算法的收敛性和超线性收敛性， 数值试验表明算法是有效的第三章，提出了求解一般约束优化问题的改进的拉格 朗日一拟牛顿算法算法采用a n u i j o 型线性搜索并利用修正b f g s 公式进行拟牛顿修 正，保证了拉格朗日函数的h e s s i a n 阵的正定性在适当的条件下，证明了该算法的 收敛性和超线性收敛性，通过算法检验及与其它算法比较，该种算法具有较快的收 敛速度第四章，提出了一种解决不等式约束优化的新的混合算法，算法采用广义 投影技术和a r m i j o 非精确线性搜索，每次迭代只需求解一个线性方程组，大大减少 了算法的计算工作量，在较弱的条件下，证明了算法的收敛性，数值算例表明该算 法是有效的第五章，总结了本文结论，同时提出了用滤子算法替代罚函数的研究 i 方向 关键词：一般约束；不等式约束；拉格朗日牛顿法；拉格朗日拟牛顿法；广义 投影技术 i v t h e a l g o r i t h mr e s e a r c h o nn o n l i n e a rc o n s t r a i n e do p t i m i z a t i o n p r o b l e m s a b s t r a c t n o n l i n e a rc o n s t r a i n e do p t i m i z a t i o np r o b l e m sa r et h em o s tc o m m o n f o r mi nn o n l i n e a ro p t i m i z a t i o np r o b l e m sa sw e l la st h em o s tc h a l l e n g e d s u b j e c t si no p t i m i z a t i o nr e s e a r c h t h e r e f o r e ，t h i st h e s i sd o e sar e s e a r c ha b o u t s o m ea l g o r i t h m si nn o n l i n e a rc o n s t r a i n e do p t i m i z a t i o np r o b l e m s c o m m o n l y , t h em a i nr e s e a r c hm e t h o d sa r ef e a s i b l ed i r e c t i o nm e t h o d ，l a g r a n g e - n e w t o n m e t h o d ，p e n a l t yf u n c t i o n sm e t h o d ，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 g ， s e q u e n t i a ls y s t e m so fl i n e a re q u a t i o n s ，t r u s tr e g i o na l g o r i t h ma n ds oo n ； a m o n gt h o s ea l g o r i t h m s ，l a g r a n g e n e w t o nm e t h o da n ds e q u e n t i a lq u a d r a t i c p r o g r a m m i n ga r et h em o r ei m p o r t a n tr e s e a r c hm e t h o d st h o u g ht h e y a r e s e l d o mu s e di ng e n e r a lc o n s t r a i n e do p t i m i z a t i o np r o b l e m i fw ec o m b i n e s a c t i v e s e ts t r a t e g yw i t hf e a s i b l ed i r e c t i o nm e t h o di nt h ed e a l i n go f i n e q u a l i t y c o n s t r a i n e do p t i m i z a t i o n p r o b l e m ，i tw o u l dm a k et h ew h o l ea l g o r i t h m s s t r u c t u r em o r ec o m p l e x i fw eu s eg r a d u a le x a c ts e a r c hm e t h o di nt h el i n e a r s e a r c h ，i tw o u l dm a k et h eo p e r a t i o ns c a l em o r el a r g e r t h u s ，t h i st h e s i sm a k e s ar e s e a r c ha b o u t l a g r a n g e - n e w t o n m e t h o di n g e n e r a l c o n s t r a i n e d o p t i m i z a t i o np r o b l e ma n du s e sa r m i j ol i n e a rs e a r c ht og a i na ni m p r o v e m e n t o fl a g r a n g e q u a s i - n e w t o nm e t h o d m e a n w h i l e ，ah y b r i da l g o r i t h mi sg i v e n w i t ht h eh e l po fl a g r a n g e - n e w t o n sc o n c l u s i o na n dg e n e r a l i z e dp r o j e c t i o n v t e c h n i q u e t h i st h e s i sc o n s i s t so ff i v ec h a p t e r s ，w h i c ha r el i s t e da sf o l l o w s i n c h a p t e r1 ，w e i n t r o d u c et h ed e v e l o p m e n to fn o n l i n e a rc o n s t r a i n e d p r o g r a m m i n ga n dd e p i c tt h ei n n e rc o n n e c t i o no fa l lk i n d so fa l g o r i t h mf o r n o n l i n e a rc o n s t r a i n e d o p t i m i z a t i o np r o b l e m s ，a n dt h e n i n t r o d u c et h e c o n d i t i o n sf o ro p t i m a l i t yo fg e n e r a lc o n s t r a i n e do p t i m i z a t i o np r o b l e m n e x t , w es u m m a r yt h ec o n v e r g e n c ea n ds u p e r l i n e a rc o n v e r g e n c ec o n d i t i o n so fa l l k i n d so fn o n l i n e a rc o n s t r a i n e do p t i m i z a t i o np r o b l e m s m o r e o v e r , w ei n d i c a t e t h er e s e a r c hb a c k g r o u n d ，s t a t u sq u oa n do u r 肌i t s i nc h a p t e r2 ，w ee x p a n d t h el a g r a n g e - n e w t o nm e t h o dw h i c hi su s e di ne q u a l i t yc o n s t r a i n e dp r o b l e m t og e n e r a lc o n s t r a i n e dp r o b l e mc o n d i t i o na n dt h e nt r a n s l a t et h ec o n d i t i o n sf o r o p t i m a l i t y i n t ol i n e a r e q u a t i o n s t os o l v e t h e g e n e r a l c o n s 仃a i n e d o p t i m i z a t i o np r o b l e m u n d e r s o m es u i t a b l ea s s u m p t i o n s ，w ep r o v et h e a l g o r i t h m i sc o n v e r g e n ta n dh a ss u p e r l i n e a rc o n v e r g e n c er a t e t h en u m b e r i c a l r e s u l t ss h o wt h ea l g o r i t h mi se f f e c t i v e i nc h a p t e r3 ，a ni m p r o v e m e n t l a g r a n g e q u a s i - n e w t o nm e t h o d a r e p r e s e n t e d f o rg e n e r a lc o n s t r a i n e d o p t i m i z a t i o np r o b l e m t h i sm e t h o da d o p t st h ea r m i j ol i n e a rs e a r c ha n d u t i l i z e sm o d i f i e db f g so fq u a s i - n e w t o n ，w h i c he n s u r e st h ep o s i t i v ed e f i n i t e p r o p e r t y u n d e rs o m e s u i t a b l e a s s u m p t i o n s ，w ep r o v e t h ea l g o r i t h mi s c o n v e r g e n t a n dh a s s u p e r l i n e a rc o n v e r g e n c er a t e t h r o u g h n u m e r i c a l e x p e r i m e n tr e s u l t so ft h ea l g o r i t h ma n dt h ec o m p a r i s o nw i t ho t h e r s ，i t i n d i c a t e st h a tt h i sm e t h o dh a sf a s tc o n v e r g e n c er a t e i nc h a p t e r4 ，an e w v 1 h y b r i da l g o r i t h mi sp r e s e n t e dt os o l v em e q u a l i t yc o n s t r a i n e do p t i m i z a t i o n p r o b l e m t h i sa l g o r i t h ma d o p t st h eg e n e r a l i z e dp r o j e c t i o n t e c h n i q u ea n d a r m i j ol i n e a rs e a r c h ，p e rs i n g l ei t e r a t i o n ，i ti so n l yn e c e s s a r yt os l o v eo n e s y s t e mo fl i n e a re q u a t i o n s t h u s ，t h ec o m p u t a t i o n a l c o s ti sr e d u c e d l a r g e l y u n d e r s o m ew e a k e n a s s u m p t i o n s ，w ep r o v e t h ea l g o r i t h mi s c o n v e r g e n t t h en u m e r i c a le x p e r i m e n tr e s u l t si n d i c a t e t h a t t h i sm e t h o di s e f f e c t i v e i nc h a p t e r5 ，w es u m m i to u rc o n c l u s i o no ft h i st h e s i sa n dp r o p o s e t h er e s e a r c hd i r e c t i o no ff i l t r a t em e t h o di n s t e a do f p e n a l t yf u n c t i o n s k e y w o r d s ：g e n e r a l c o n s t r a i n t ；i n e q u a l i t yc o n s t r a i n t ；l a g r a n g e - n e w t o n m e t h o d ；l a g r a n g e - q u a s i - - n e w t o nm e t h o d ；g e n e r a l i z e dp r o je c t i o nt e c h n i q u e v n 承诺书水话吊 本人郑重声明：所呈交的学位论文，是在导师指导 下独立完成的，学位论文的知识产权属于太原科技大学。 如果今后以其他单位名义发表与在读期间学位论文相关 的内容，将承担法律责任。除文中已经注明引用的文献 资料外，本学位论文不包括任何其他个人或集体已经发 表或撰写过的成果。 学位谂文作者( 筝章) ：p 寐力1 7 尻 2 0 0g 年c ，月占e l 第一章非线性约束规划概述 第一章非线性约束规划概述 1 1 非线性规划的产生和发展 非线性规划( 也称非线性最优化或最优化) 是在有限种或无限种可行方案( 决策) 中 挑选最优的方案( 决策) 随着计算机及信息计算的高速发展，使得最优化理论和算法 的研究成为了一种迫切需要最优化问题的一般数学模型为： ( p ) m i nf ( x ) s 1 x x 。 其中x = x e r ”ig ，( x ) = o ，f e ；哆( x ) o ，j i ) ，e = 1 ，2 ，) ， ，= ，+ 1 ，+ 2 ，+ m ，f ( x ) ，g ( x ) ，吃( x ) 均为连续可微函数此处 g e ( x ) = ( 蜀( x ) ，g ：( x ) ，g ，( x ) ) 7 ，啊( x ) = ( 卅( x ) ，啊+ ：( x ) ，巧+ 。( x ) ) 7 非线性规划问题是指厂( x ) ，g e ( x ) ，啊( x ) 中至少有一个是非线性函数对于约 束条件而言，若e = = ，为空集，则称问题( 尸) 为无约束优化问题；否则，称 问题( 尸) 为有约束优化或约束优化问题当e ，i = 时该问题称为等式约束优 化问题( 即泸) ，当i ，e = 时该问题称为不等式约束优化问题( 优p ) ，当e ， i 时该问题称为一般约束优化问题( g p ) 在这三类约束优化问题中，一般约束 优化问题的研究具有广泛的应用意义，等式约束优化问题相对比较简单，在一些情 况下可以有解析解，而不等式约束优化问题的研究对于我们最后在研究一般约束优 化问题时有着很好的参考价值本文主要研究不等式约束优化问题( 脚) 和一般约束 优化问题( g 尸) 非线性规划是一门应用相当广泛的学科，它讨论决策问题的最佳选择的特性， 构造寻求最佳解的计算方法，研究这些计算方法的理论性质及实际计算表现随着 现代社会各种生产经济活动规模的不断扩大，工程设计及决策过程日趋复杂，产生 了许多大规模的非线性规划问题，如上所述，这些非线性规划问题可分为无约束条 件和有约束条件的优化问题，解决前者的有牛顿法、共轭梯度法、拟牛顿法，解决 后者的有罚函数法、可行方向法、逐步二次规划法、有效集法、信赖域法等，借助 l 非线性约束规划问题的算法研究 于l a g r a n g e 函数，可将解决无约束优化问题的算法应用到约束优化问题上，进而融 合无约束线性规划的算法与约束线性规划的算法上面三种类型的等式与不等式约 束优化问题在理论研究和实际应用上具有重要的价值，在经济计划、生产管理、工 程设计、结构优化设计、电力分配和政府决策等很多重要领域都有直接的应用，因 而受到政府部门、科研机构和产业部门的高度重视而寻找这些问题快速有效的解 法，一直是最优化算法研究的重点之一将解决无约束优化中的上述几类方法加以 改进，可以用来求解大规模的非线性优化问题，但有些算法的收敛速度很慢且计算 量大，难以满足实际问题的需要，因而需要融合无约束优化算法和约束优化算法各 自的优点，从而得到求解约束规划更好的优化算法，这样才能更好的满足社会发展 的需求 由于非线性规划重要而广泛的应用价值，使得国内外很多专家学者对该领域进 行了研究和探讨国际上涌现出来如f f a c c h i n e i 、g l i u z z i 、s l u c i d i 、p s p e l l u c c i 、 r f l e t c h e r 、s l e y f f e r 等杰出的非线性规划专家国内的如袁亚湘、徐成贤、张可村、 贺国平、简金宝、李董辉、桂胜华等优秀的优化专家，他们在国际上取得了很多重 要的学术成果 非线性规划经历了从单变量规划到多变量规划、从无约束规划到约束规划、从 中小规模优化到大规模优化的发展过程，而约束规划又是其中十分重要的部分，除 了解决约束规划问题的常规算法如罚函数法、可行方向法、逐步二次规划法、有效 集法、信赖域法等算法外，参考借鉴并融合无约束算法的思想也成为研究的一个重 要方面，此外研究并借鉴约束规划问题的常规算法思想则成为研究的另一个重要方 面，因而我们既要处理好约束规划算法和无约束规划算法的内在联系，也要研究那 些解决约束规划问题的常规算法中的重要技术和思想 1 2 非线性约束规划的相关算法介绍 许多大规模非线性优化问题经过抽象建模可化为含等式与不等式约束规划问题 形式寻找该类问题快速而有效的解法一直是最优化算法的研究重点之一解决约 束规划问题方法有很多种，本文研究的算法是n e w t o n 法、l a g r a n g e n e w t o n 算法( l - n 法) 和序列二次规划算法( s q p 法) 等三种算法 n e w t o n 法是解决无约束问题最原始也是最经典的算法，同时它也是一种具有较 2 第一章非线性约束规划概述 快收敛速度的方法n e w t o n 法的思想和理论研究已经比较完整和完善l h l ，因而我们 参考并借鉴n e w t o n 法的思想也成为研究过程中一项很重要的内容在本文研究中， 比较有参考价值的是阻尼n e w t o n 法，该算法通过求解线性方程组得到搜索方向，并 利用线性搜索得到步长，这也是求解约束规划问题迭代算法的一般思路，下面我们 简单介绍该算法的一般描述【4 】： 考虑无约束优化问题 m i n f ( x ) ， s t e p1 给初始点五，精度s 0 ，令k ：= 1 s t e p2 若0 夥( 以) 忙s ，则算法终止，得无约束优化问题的解t 否则， 解线性方程组v 2 f ( x k ) d + v f ( x , ) = 0 ，得解矾 s t e p3 由线性搜索呀n 厂( + 仅巩) = 厂( 而+ a t 以) ，确定步长a t s t e p4 令稚+ l = 矗+ a 女喀，k ：= k + l ，转s t e p2 考虑等式约束优化问题 ( 口忡) m i nf ( x ) 赋g ，( x ) = 0 ，i e = l ，2 ，) ， 利用l a g r a n g e 函数三( x ，a ) = 厂( x ) + 九7 g e ( x ) 可联系目标函数和约束函数的信息， 其中a = ( ，疋，- ) 7 为拉格朗日乘子，进而利用上述的n e w t o n 法解决，此方法称 为l - n 法最早的解决等式约束问题( e ? v ：p ) 的l - n 法的基本算法如下h ： s t e p1 给出五r ”， r 7 ，卢( o ，1 ) ，0 ，k ：- - 1 s t e p 2 计算尸( ，z , ) - - u v ，三( 毛，九) 哐+ 9 9 e ( 屯) 眨， 此处( 以，九) = 厂( 以) + 九，蜀( 孔) ，若尸( ，九) g ，则停 否则求解线性方程组 ( 翟裂0 k 十g “e 剥，i ( ) 7j l 阮i( ) 得到搜索步长吨，矾；a = 1 非线性约束规划问题的算法研究 s t e p3 若尸( 以+ a 以，九+ 口吼) ( 1 一卢a ) 尸( ，九) ，则转s t e p4 ；a = a 4 ，转s t e p 3 s t e p4 令坼+ l = 故+ a 反，九+ l = 丸+ a 砜，k ：= k + l ，转s t e p 2 其中v g ( x , ) - - ( v g 。( 屯) ，v g t ( ) ) ，并定义( 1 1 ) 式中 v ：工( ，九) = v 2 厂( ) + 九，v 2 9 ，( ) = 日( 以，九) = 也 取对称正定阵最近似峨，由约束规划问题的k - t 点条件可知方程组( 1 1 ) 的解 反是下面q p 子规划问题的解 ( q p ) m i n 三( 畋) r b ( 毪，丸) 喀+ 町( ) r 盔 “ v g e ( ) 以+ & ( 以) = o 该q p 子规划问题所得解喀为搜索方向，并产生新的迭代点列，此时称该种算法为 解决等式约束问题( e 聊) 的s q p 法对于s q p 算法介绍如下4 1 ： s t e p1 给出_ r “，对称正定阵且r ，仃 0 ，6 0 ，s 0 ，七：= 1 s t e p2 求解二次规划q p 子规划问题： m i l l g ( d ) = 圭d r 圾d + w ( ) 7 d s 7 v g e ( x k ) d + g e ( 吒) = 0 可得解破及其对应的l a g r a n g e 乘子九+ ，：若0 以忙s ，则停； 否则求a 。【o ，5 】，使得 p ( 而+ 吒反，仃) 恶怨尸( 砟+ a 喀，仃) + & s t e p3 令+ l = 以+ a i 矾；用适当的拟牛顿法修正鼠得b + l ；令后：= k + l ，转s t e p2 s q p 法中在解得搜索方向矾时每步迭代须求解一个或多个q p 子规划问题，计 算量大，若将该q p 子规划问题用线性方程组替代，可使每步迭代只需求解几个系数 矩阵相同的线性方程组，使得算法迭代时间减少，同时数值稳定目收敛速度快，在 4 第一章1 r 线性约束规划概述 此情况下发展成为序列线性方程组算法( s s l e 法1 整理相关算法的发展进程我们可得到以下算法关系图： 图1 1 1 3 约束规划问题的最优性条件 考虑一般约束优化问题 ( 洲p ) m i nf ( x ) 旺g ，( z ) = o ，i ee = 0 ，2 ，m 乃( x ) o ，j e i = p + 1 ，+ 2 ，l + m ) 和( g n p ) 相关的l a g r a n g e 函数记为 z ( x ，a ，j l l ) = 厂( x ) + a r g e ( x ) + p r 啊( z ) = 厂( x ) + g ，( x ) + p ，哆( x ) ， 同时踞( 以) = ( 。( x k ) ，( 坼) ) ，v h , ( x k ) - - ( v h , 卅( x k ) ，v h , + ，( 黾) ) ( g n p ) 问题的最优性条件如下： 定理1 1 【5 】( 一阶最优性条件) 设厂( x ) ，g e ( x ) ，啊( x ) 为连续可微函数，x ：奖j ( g n p ) 问题的局部最优解，由，+ 肌个向量构成的向量组 ，( x ) ，i e ；v 勺( x ) ，) 线性 无关，则存在l a g r a n g e 乘子a r 7 ，p + r ”使得 非线性约束规划问题的算法研究 v ，三( x ，九+ ，j u ) = o ， a g 兰 吕( x ) ：o ，f e ， p ：o ，哆( x ) o ，：吃( x + ) - o ，je 1 ( 1 2 ) 此时称( 1 2 ) 为( g n p ) 问题的k 一丁点条件，其解( x ，允，| “) 称为( g - 尸) 问题的k r 点对k t 点条件( 1 2 ) 可以写成如下紧凑形式： v ，三( x ，九，p ) g ( x ) 幽一吃( x + ) ) = 0 ， 此时向量值函数的极小化按分量进行 定理1 2 旧( 二阶最优性条件) 设厂( x ) ，g e ( x ) ，啊( x ) 为二阶连续可微函数，对 可行点x 而言，若存在l a g r a n g e 乘子允r 7 ，r ”满足( 1 2 ) ，同时对每个向量 d g ，记，( x ) = 歹，i 吃( x ) = o ) ，其中 g = d 0 d 7 v g , ( x ) - - o ，f e d ，v 哆( x + ) - - o ，j i ( x ) ，且一 o d 7 v 匀( x + ) o ，jei ( x ) ，且= o 都有d 7 v ：三( x ，a ，p ) d o ，则x 。为( o n p ) 问题的一个严格局部最优解 1 4 算法的收敛性及超线性收敛性 对于最优化模型( 尸) ，我们通常采用迭代法求它的最优解一个算法是否收敛通 常和初始点有关，如果当初始点充分接近聚点x 时，算法产生的序列 ) 才收敛于 x ，则称算法局部收敛；若对于任意初始点而言，算法产生的序列 砟) 都收敛于x ， 则称算法整体收敛在本文中，所研究的算法的收敛性包括局部收敛性和整体收敛 性，我们统称为约束规划问题的收敛性，它主要是利用算法的最优性条件来检验， 说明的是算法有效性问题，而约束规划问题的超线性收敛性则是说明算法的收敛速 度问题 6 第一章非线性约束规划慨述 线性收敛速度和二阶收敛速度的算法是比较快速的 黼蝴惦受筒 当o 0 ，v y o ，y r ”，v g ( x ) 1y = 0 ，其中 w ( x ) = ( 。( z + ) ，( x + ) ) 很多学者对算法的超线性收敛证明做了很多有意义的研究工作0 1 ，关于如何证 明算法的超线性收敛性有以下著名的b o g g s t o l l e w a n g 条件 定义广义投影矩阵 尸( ，色) = 何1 一所1 ( 以) ( _ ) 7 何1 v g ( t ) rv ( 以) r 何1 定理1 3 阳3 设( x ，a ) 是( e 尸) 问题的k 一丁点对，在假设条件彳1 1 彳1 4 下，若 尾 和 何1 一致有界，则算法产生的点列 超线性收敛的充要条件为 7 非线性约束规划问题的算法研究 ：受睑与尚学剑一o 定理，4 n 1 在假设条件彳t 彳3 及彳，5 下，则! 受监霰兰铲= 。等价于 ! 鳃睑气半剑- o ， 其中b 是v ：三( ，九) 的一阶近似，j 为单位方阵，畋= 吒+ 。- x , 该条件虽然仅是研究等式约束问题的超线性收敛条件，但是对于我们研究不等 式约束问题和一般约束问题有很好的启发作用 1 5 选题背景及课题内容 1 5 1 非线性约束规划问题研究背景 对于求解一般非线性约束规划问题( g n p ) 的算法，按照发展的时间顺序和不同 的设计思路，可以大致分为以下两类 第一类：早期的直接法 包括网格法、随机试验法和复形法其主要思路是：把求解无约束规划问题的 各种直接方法推广到求解一般的非线性约束规划问题这类方法在按照某种方式选 定了一组测试点或规定了产生新的测试点的方法之后，此时通过计算目标函数和约 束函数的值来得到问题的最优解其缺点是计算量大、算法无好的理论依据，往往 只能找到问题的一个较好的可行解，即使在特殊情况下能保证算法的收敛性，其收 敛速度也只能是线性的所以，只要不是没有其它的算法可利用，一般不用这类方 法 第二类：近代常规方法 在可行域内使目标函数下降的迭代点法，包括可行点法、广义消去法、广义 简约梯度法、投影梯度法等可行方向法它是解决线性约束规划问题的算法在非线 性约束规划问题上的推广其主要思路是：对原约束优化问题不预先作转换，直接 用线性约束问题的算法进行处理因此，这类方法所产生的迭代点均是问题的可行 点这类方法的主要优点是它保持迭代点列的可行性，并通常可找到问题的局部最 第一章非线性约束规划概述 优解，其缺点是有关算法的实现往往很复杂、计算量比较大，且收敛速度通常只能 达到线性收敛故一般而言，对于非线性约束规划问题，这类方法不是有效的算法 利用目标函数和约束条件构造增广目标函数，借此将约束规划问题转化为无 约束规划问题，然后利用求解无约束规划问题的方法间接求解新目标函数的局部最 优解或稳定点，如l n 法和罚函数法对于精确罚函数的研究，1 9 7 9 年，h a n 和 m a n g s r i a n 开始讨论了精确罚函数，1 9 8 1 年r o s e n b e r g 和l a s s e r r e 分别给出了一个精确 罚函数的全局收敛性算法，1 9 8 2 年c l a r k e 贝u 讨论了精确罚函数的稳定性条件，1 9 8 4 年r o s e n b e r g 也讨论了精确罚函数的稳定性条件，其中稳定性条件又是判断精确性的 充分必要条件，但对于复杂问题则无法验证1 9 9 8 年，d i p p l l o 和g r i p p o 1 1 】研究了精 确罚函数的算法1 9 9 5 年韦增欣【1 2 】研究了一族精确罚函数的存在性及控制参数的下 界1 9 9 6 年林波艇和张可村【1 3 】研究了用l 1 精确罚函数作线性搜索函数的一种修正约 束变尺度算法精确罚函数对于问题函数性态的要求比较低，同时只要实现方法恰 当，就可保证有较好的收敛速度和数值稳定性，因而这类方法是求解非线性约束问 题的主要方法 ( 9 s q p 法s q p 法比罚函数法更直接一些它是利用原先非线性约束优化问题的 有关信息来构造某一简单的近似优化问题，通过求解它来给出对当前迭代点的修正， 主要是用一系列的线性规划或二次规划来逐次逼近原非线性规划问题近年来，为 了避免在每个迭代步直接求解一个乃至多个二次规划子问题，人们发展和研究了基 于二次规划子问题k 一丁点条件导出的线性方程组的s s l e 法，这种方法在求解问题 时往往和某种可行方向法相联系人们通过对s q p 法不断的改进和发展，克服了它在 局部收敛、子问题可能不可行或无有界解等缺点，现在，s q p 类方法已成为求解非线 性约束优化问题的一类最有效的算法 信赖域法求解约束优化问题的信赖域法的一个重要因素是价值函数的选取 1 9 8 6 年，袁亚湘和p o w e l l 合作，构造了利用f l e t c h e r 光滑罚函数作为价值函数的信赖 域法【1 4 1 ，这是第一个利用光滑价值函数并得到超线性收敛速度的信赖域法，1 9 9 5 年， 袁亚湘【l5 】接着提出了利用精确罚函数处理约束优化问题的信赖域法，该方法给出了 一个简单的但很有技巧性的调节罚因子公式，从而保证了算法的收敛性目前为了 使得求解约束优化问题的信赖域法能找到全局最优解，人们已经将传统的内点法与 信赖域法结合起来构造求解约束优化问题的信赖域内点法对于带有线性等式或非 9 非线性约束规划问题的算法研究 负变量的约束问题，2 0 0 0 年b y r d rh ，j e a n cg i l6 j 给出了一种信赖域内点法，而 2 0 0 6 年n i e p y ，m a cf t l 7 1 给出的信赖域内点法则是处理带线性不等式约束优化问 题近年来，y i n gj i ，s h a o - j i a nq u 等人【1 8 】通过有效集策略，提出了一种解决约束优化 问题的信赖域算法一锥模型信赖域算法，i f i w a n gc h e n g j i n g t l 9 1 则在文 1 8 】基础上提出 了一种解决非线性约束优化问题的新锥模型信赖域算法，并在一定的条件下证明了 新算法的全局收敛性 总之，从对求解非线性约束规划问题的算法的回顾中我们可以看出：l - n 法、罚 函数法和s q p 法在求解非线性约束优化问题体现了其特点，目前常用的非线性约束规 划算法大都属于这些方法中的某一类本文主要是用上述l - n 法和s q p 法并结合罚函 数和可行方向法的思想和技术来研究非线性约束规划问题的求解 1 5 2k - 8 法的研究现状及本文所做工作 对于算法中线性方程组的研究，p a r t i e r ，t i t s 和h e r s k o v i t s 在1 9 8 8 年给出了可行q p f r e e 算法【2 0 1 ，从而引发了人们对算法中线性方程组的研究【2 1 之9 1 q p f r e e 法主要特征为 用线性方程组代替二次规划，算法需求解两个线性方程组和一个最小二乘子问题针 对严格互补松弛条件提出的h q i 和l q i 算法【3 0 1 ，主要是利用f i s c h e r - b u r m e i s t e r j 线性 互补函数c p 函数) 将约束规划问题的k f 条件转化为一个非光滑方程组，其优点 是不发生求解方程组的系数矩阵的病态性，同时也弱化了证明超线性收敛的假设条 件在此基础上，2 0 0 5 年，桂胜华、王济生提出了解不等式约束问题的l n 法及 l a g r a n g e q u a s i - n e w t o n 法( l q n , 法) 3 1 - 3 2 ，他们主要是通过构造满足k z 点条件的 线性方程组作为基础，并引入罚函数作为终止条件，克服了单位步长不被接受的 m a r o t o s 效应，而在2 0 0 6 年及2 0 0 7 年，桂胜华等又继续研究了约束规划问题的l q - n 法，其算法采用了渐进精确搜索方法并用拟牛顿公式替代t h e s s i a n 阵【3 3 弓4 】这两种 算法在解决( n e l 问题上所采用到的线性方程组求解、搜索方向的计算及效益函数的 选择、利用f i s c h e r - b u r m e i s t e r 线性互补函数克服求解线性方程组系数矩阵病态性等 思想为讨论其它算法提供了一种启发，但是l n 法仅对于解决不等式约束问题而言， 而l q - n 法所采用的渐进精确搜索容易造成计算量增大，因而在本文第二章中我们首 先探讨了由不等式约束条件推广到一般约束条件的l n 法，在本文第三章中我们则采 用a n 蝎。非精确线性搜索并借助精确罚函数，替代了计算量大的渐进精确搜索，提 出了一种改进的l q - n 法 1 0 第一章非线性约束规划概述 1 5 3s o p 法的研究现状及本文所做工作 s q p 法是解决约束优化问题中最常用的、也是非常流行的方法之一【3 5 1 ，齐j - s q p 法最早研究工作为w i l s o n l 9 6 3 年提出的s o l v e r 算法，但该算法要求 最= v ：三( 坼，地) 正定，而且算法仅具有局部收敛性和局部二次收敛性二十1 廿幺e 7 0 年代中后期，h a n 提出了类似于无约束优化的朋p 公式修正b 来产生鼠+ 。，并证明 此时算法仍具有局部超线性收敛性1 9 7 7 年h a n 进一步提出用f 1 精确罚函数为效益函 数( 即线搜索目标函数) 确定步长，这使得算法具有全局收敛性同期，p o w e l l 对h a n 工作进一步修改，主要是具体给出精确罚函数中参数的选取和矩阵最的修正方法， 从而建立了一个有效的s q p 法( w h p 方法) 目前s q p 法研究可分为以下两类：第一类： 是直接以目标函数作为搜索函数，要求产生的迭代点满足一定的可行性，此类称为 可行方向法最早的可行方向法是1 9 8 7 年p a r t i e r ，t i t 等研究和建立了初始点和迭代点 均可行的可行s q p 法，在此基础上主要发展和研究的有次可行方向法和强次可行方向 法两类算法，它们兼顾了不可行s q p 法和可行s q p 法的长处，近年来对可行方向法的 研究参见文 3 6 4 2 ；第二类：是利用某个罚函数作为搜索函数，不直接考虑迭代点 的可行性在s q p 法中，为了克服m a r o t o s 效应，我们通常把罚函数选为厶光滑精确 罚函数或者增广l a g r a n g e i 函数，而1 9 9 8 年p s p e l l u c c i 将罚函数取为经典精确罚函数形 式 该罚函数的性能及克服m 踟t o s 效应的效果比较显著，因而以后很多文章均采用 这种罚函数的形式近年来对罚函数的研究参见文 4 3 - 4 9 】 s q p 法的主要特征和基本形式是用一阶t a y l o r 级数来近似非线性约束条件，用 二阶t a y l o r 级数来近似非线性目标函数现在s q p 法的研究已经比较完善，发展至 今它已经不再是一个具体的算法，而是一个概念性的算法了，借助s q p 法中可行方 向法和罚函数法的思想，我们在本文第四章中提出了一种混合算法，该算法借助文 3 1 】 拉格朗日牛顿法的一些结论，同时采用文 3 7 】的广义投影技术得到新的迭代方向和 e s p e l l u c c i 所采用的罚函数形式，并利用a r m i j o 非精确线性搜索，从而得到了一种 、il，j 、- ， x ，j i 、l o ，fi nm甜 。卢 一 、l ， x ，i g l ，一 + 、l ， x j 广 = 、l ， 矿甜x f p 非线性约束规划问题的算法研究 收敛速度较快的混合算法 1 。5 4 本文所做工作概括 针对目前l - n 法和s q p 法的研究现状，我们做了以下工作，如图1 2 所示 图1 2 1 2 第二章求解一般约束优化问题的拉格朗同牛顿法 第二章求