（基础数学专业论文）非线性优化qpfree算法的研究.pdf

摘要 自从二十世纪7 0 年代以来，q p f r e e 算法一直是非线性约束优化研究中的 一个十分活跃的领域本文针对带非线性不等式约束的优化问题，对q p f r e e 算法自身的理论进行了深入系统的研究，具体研究成果包括如下四部分 1 绝大部分q p f r e e 算法，须求解三个线性方程组和一个线性最小二乘 问题( 有时须求解五个线性方程组) 以产生搜索方向本文进一步研究该类算 法，提出了一个新的q p f r e e 内点算法该算法通过求解具有相同系数矩阵 的三个线性方程组获得搜索方向，减少了计算量 2 通过积极约束集策略，利用部分约束条件，构造了一个规模较小的线 性系统，提出了相应的可行q p f r e e 算法该算法的搜索方向由三部分组成： 下降方向稚；可行方向s ；以及克服m a r a t o s 效应的二阶校正方向露证明了辅 助方向d k ：稚+ 8 为一个可行下降方向线搜索技巧采用两种直线搜索的 有机结合辅助的可行下降方向与a r m i j o 线搜索的结合确保了算法的全局收 敛，同时方向d k ：稚+ d f 与步长恒为1 的试探步线搜索的结合确保了算法的 超线性收敛率理论上证明了当迭代次数充分大时，辅助的可行下降方向与 相应的a r m i j o 线搜索不再执行，而步长为1 的试探性搜索恒成立 3 对序列二次规划算法进行了本质上的改进绝大部分序列二次规划 算法，其共同之处在于：牛顿步方向均为通过求解不等式约束二次规划子问 题而得这里，提出了一个可行序列等式约束二次规划算法首先，直接通 过求解仅含线性等式约束二次规划子问题得到下降方向稚其次，不同于 文【2 引，为避免定义精确罚函数，避免定义复杂的罚权重和深刻的理论分析， 该算法通过求解线性方程组来修正方向罐，得到目标函数，的可行下降方 向泸且算法在迭代中自动保证了乘子的非负性 4 以往可行q p f r e e 算法其可行下降方向须求解两个或多个线性方程 组( 有时包含非线性的子问题) 这里，提出了一个改进的可行q p f r e e 算法 该算法只须求解一个线性方程组就可得到可行下降方向，减少了计算量，且 用一较弱的假设条件取代近似h e s s i a n 阵正定假设，算法仍具有全局收敛性 和超线性收敛性 最后，对上述算法均进行了数值实验，实验结果充分表明所提出的算法 具有有效性、可行性和稳定性 关键词：非线性规划，q p f r e e 算法，可行方向法，全局收敛，超线性 收敛率 a b s t r a c t s i n c e1 9 7 0 s ，q p f r e ea l g o r i t h mh a sb e e nah o tf i e l di nr e s e a r c hi n t on o n l i n e a r p r o g r a m m i n g i nt h i st h e s i s ，w em a k eas y s t e m a t i ca n dd e e pi n v e s t i g a t i o no nq p f r e e a l g o r i t h mf o rn o n l i n e a ri n 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 t h ec r e a t i v ea c h i e v e m e n t s c a nb es u m m a r i z e di n t ot h ef o l l o w i n gf o u ra s p e c t s 1 t h et r a d i t i o n a lq p f r e ea l g o r i t h mi si m p r o v e di ns u b s t a n c e a t p r e s e n t ，m o s t q p f r e ea l g o r i t h m sa r en e c e s s a r yt os o l v et h r e es y s t e m so fl i n e a re q u a t i o n sa n dal i n e a r l e a s ts q u a r e sp r o b l e m ( s o m e t i m e s ，i n c l u d i n gf i v es y s t e m so fl i n e a re q u a t i o n s lt oo b t a i n t h es e a r c hd i r e c t i o n h e r e ，an e wi n t e r i o rp o i n tt y p eq p f r e ea l g o r i t h mi sp r o p o s e d t h em o s tp r o p e r t yo ft h en e wa l g o r i t h mi st h a to n l yt h r e es y s t e m so fl i n e a re q u a t i o n s w i t ht h es a n ec o e f f i c i e n tm a t r i xa r er e q u i r e dt oo b t a i ns e a r c hd i r e c t i o n w h i c hs h o w s t h a tt h ec o m p u t a t i o n a le f f o r to ft h ep r o p o s e da l g o r i t h mi sr e d u c e df u r t h e r 2 al i n e a rs y s t e mw i t hs m a l ls c a l ei sc o n s t r u c t e dw i t ha c t i v es e ta n dp a r to f c o n s t r a i n t s i na l g o r i t h m ，s e a r c hd i r e c t i o ni sm a d e u po ft h r e ep a r t s ：ad e s c e n td i r e c t i o n c 6 8 ，af e a s i b l ed i r e c t i o ns f ，a n das e c o n d o r d e rr e v i s e dd i r e c t i o n 砰t oo v e r c o m em a r a t o s e f f e c t i ti sp r o v e dt h a tt h ed i r e c t i o nd k = d 各+ s i saf e a s i b l ed e s c e n td i r e c t i o n t w o t y p e so fl i n e a rs e a r c ha x ep r o p o s e d t h ea u x i l i a r yf e a s i b l ed e s c e n td i r e c t i o nd ka n d t h ea r m i j ol i n e a rs e a r c h ，w h i c ha r en ol o n g e rp e r f o r m e df o rt h el a r g ee n o u g hn u m b e r o fi t e r a t i o n ，e n s u r et h eg l o b a lc o n v e r g e n c e ，w h i l et h ed i r e c t i o nd k = 稚+ 砟a n d a n a t t e m p t e dl i n e a rs e a r c hw i t hu n i ts t e p s i z ee n s u r et h es u p e r l i n e a rc o n v e r g e n c er a t e 3 t h et r a d i t i o n a ls 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 ga l g o r i t h mi si m p r o v e di n s u b s t a n c e a tp r e s e n t ，m o s ts 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 ga l g o r i t h m sh a v ea c o r n - m o n ：t h en e w t o n 8d i r e c t i o ni so b t a i n e db y s o l v i n gq u a d r a t i cp r o g r a m m i n gs u b p r o b l e m w i t hi n e q u a l i t yc o n s t r a i n s h e r e ，af e a s i b l es e q u e n t i a le q u a l i t yc o n s t r a i n e dq u a d r a t i c p r o g r a m m i n ga l g o r i t h mi sp r o p o s e d f i r s t ，t h ed e s c e n td i r e c t i o n 稚i so b t a i n e db ys o l v - i n gq u a d r a t i cp r o g r a m m i n gw i t ho n l ye q u a l i t yc o n s t r a i n s s e c o n d ，u n l i k e 【2 引，i no r d e r t oa v o i dt od e f i n et h ee x a c tp e n a l t yf u n c t i o n ，w h i c hc a u s e st h ec o m p l i c a t e dd e f i n i t i o n o ft h ep e n a l t yw e i g h t sa n dt h ep r o f o u n dt h e o r e t i c a la n a l y s i s w er e v i s et h ed i r e c t i o nd o t oo b t a i naf e a s i b l ed e s c e n td i r e c t i o ndo ft h eo b j e c t i v ef u n c t i o n b ys o l v i n gs y s t e m s o fl i n e a re q u a t i o n s m o r e o v e r ，t h ea l g o r i t h me n s u r e st h en o n n e g a t i v e p r o p e r t yo ft h e m u l t i p l i e rv e c t o r 4 f o re x i s t i n gf e a s i b l eq p f r e ea l g o r i t h m s ，i ti sn e c e s s a r yt os o l v et w oo rm o r e s y s t e m so fl i n e a re q u a t i o n s ( s o m e t i m e s ，i n c l u d i n go t h e rs u b p r o b l e m sw h i c ha r en o t l v v e q u i v a l e n tt ol i n e a rs y s t e m s ) t oo b t a i nt h ef e a s i b l ed e s c e n td i r e c t i o n h e r e ，a ni m p r o v e d f e a s i b l eq p f r e ea l g o r i t h mi sp r o p o s e d t h em o s ta t t r a c t i v ef e a t u r eo ft h en e wa l g o r i t h m i st h a to n l yo n es y s t e mo fl i n e a re q u a t i o n si sr e q u i r e dt oo b t a i nt h ef e a s i b l ed e s c e n t d i r e e t i o n w h i c hs h o w st h a tt h ec o m p u t a t i o n a le f f o r to ft h ep r o p o s e da l g o r i t h mi s r e d u c e df u r t h e r m o r e o v e r ，t h ea l g o r i t h mi ss t i l lg l o b a lc o n v e r g e n ta n ds u p e r l i n e a r l y c o n v e r g e n t ，i ft h ep o s i t i v ed e f i n i t e n e s sa s s u m p t i o no nt h eh e s s i a ne s t i m a t ei sr e l a x e d a n dr e p l a c e dw i t has i g n i f i c a n t l ym i l d e ra s s u m p t i o n i nt h ee n d ，w em a k es o m en u m e r i c a le x p e r i m e n t st oa l la l g o r i t h m ，a n dr e s u l t s s h o w st h a ta l la l g o r i t h ma r ee f f e c t i v e k e yw o r d s ：n o n l i n e a rp r o g r a m m i n g ，q p f r e ea l g o r i t h m ，m e t h o do ff e a s i b l e d i r e c t i o n ，g l o b a lc o n v e r g e n c e ，s u p e r l i n e a rc o n v e r g e n c er a t e 符号 r n r a n k ( a ) i 引 i n 弋t f ( x ) v 2 - 厂( 。) k c 铲 谚 札0 札 0 ”l i a 七 a t z 上y d i a g ( a j ，j = 1 一m ) a t 含义 主要符号表 佗维欧氏空间 矩阵a 的秩 集合i 中的元素个数 n 阶单位矩阵 ，( z ) 的一阶导数或梯度 ，( z ) 的二阶导数或海色矩阵 迭代指标 分量全为1 的向量 向量函数u ( z ) 在迭代点x 七处的值 向量函数牡( z ) 在迭代点扩处的第j 个分量 向量仳的每一个分量u j 0 向量u 的每一个分量u ； 0 表示舻中的范数 矩阵函数a ( x ) 在迭代点x 知处的值 矩阵a 中列下标属于指标集，中的列向量组成的子矩阵 向量z 与y 正交 表示以o ；为对角元素的m 阶对角矩阵 矩阵4 的转置 注：全文其余类似符号含义同上如无特殊说明，所有向量均为列向量 厦门大学博士后研究工作报告著作权使用声明 本人完全了解厦门大学有关保留、使用博士后研究工作报告的规定厦 门大学有权保留并向国家主管部门或其指定机构送交该报告的纸质版和电 子版，有权将该报告用于非赢利目的的少量复制并允许该报告进入学校图 书馆被查阅，有权将该报告的内容编入有关数据库进行检索，有权将博士后 研究工作报告的标题和摘要汇编出版保密的博士后研究工作报告在解密 后适用本规定 本研究报告属于：1 、保密() ，2 、不保密( 纸本在年解密后适用本授权书； 电子版在年解密后适用本授权书 ( 请在以上相应括号内打“”) 6 月3 日 6 月哆日 年 年 听呷 期 期 日 日 第一章绪论弟一早珀丫匕 数学与工程技术的联系现在越来越密切，以有限的资源，获得最大的经济效益或社 会效益一直足人们追求的目标，这就产生了最优化这门学科最早可以追溯到十分古老 的极值问题，然而它成为一门独立学科足在上世纪4 0 年代末，具体来讲，它主要研究某 些数学上定义的问题的最优解，即对于给出的一些实际问题，寻求最优的解决方案经 过多年的发展，针对线性规划，非线性规划，随机规划，非光滑规划，多目标规划，几何 规划以及整数规划等各种最优化问题的研究取得了丰硕的成果，新方法层出不穷，实 际应用日益广泛 本文主要研究非线性规划问题中的q p f r e e 算法而在本章中，首先介绍了与本 文相关的优化基本概念和重要引理，其次介绍了q p f r e e 算法的历史与研究现状，最 后将作者在q p f r e e 算法方面的研究工作作以介绍 1 1 基本概念 本文考虑如下非线性不等式约束优化问题： m i nf ( x ) s t 乌( z ) 0 ，j ，= 1 ，2 ，m ) ， 其中，g j ( j ，) ：胛一r 连续可微 下面我们介绍一些关于问题( 1 1 1 ) 的基本概念，参见文献【1 ，2 一记问题( 1 1 1 ) 的 可行集与积极约束集分别为 x = z r ni 易( z ) o ，歹，) ，l ( x ) = 【j ，ig j ( x ) = o ) ( 1 - 1 2 ) 而( 1 1 1 ) 的l a g r a n g i a n 函数为 l ( x ，入) = ，( z ) + 易( z ) j = i 定义1 1 1 ( 最优点) 设z + x 纠如果 f ( x + ) ，( z ) ，vz x ( 1 1 3 ) ( 1 一l 一4 ) 成立，则称z + 是问题以一f 一纠的全局最优点进一步，如果对任意z x 且z z + ，以一i 一 纠中严格不等式成立，则称z + 是全局严格最优点 圳如果对某一6 0 ，存在领域g ( x + ，6 ) ，使得 f ( x ) 厂( z ) ，vz xnn ( x + ，6 )( 1 - 1 5 ) 成立，则称z 是问题f ，f j i ，) 的局部最优点进一步，如果对任意z xnn ( x ，6 ) 且z z + ，以一f 一中严格不等式成立，则称z + 是局部严格最优点 1 2 第一章绪论 定义1 1 2 ( k k t 条件) 设z + x ，- i 口存在入4 = ( 芍，j ，) ，使得 v f ( z + ) + 芍v 函( z + ) = 0 ， j = l ( 1 - 1 6 ) 岛( z 4 ) 0 ，譬夕j ) = 0 ，芍0 ，j ， ( 1 - l 一7 ) 成立，则称z + 为问题以一j 一1 ) 的k u h n t u c k e r - k a r u s h 点f ，简称解z 点j ，a 为相应的三叼m 叼i 口佗乘 子或脒睐子，而( z ，入+ ) 为以一j 纠的一个删z 最对 定义1 1 3 ( l i c q 条j # ) 设z 。x ，如果向量组 v 易( z 4 ) ，j i ( x + ) ) 线性无关， 贴称( i 一1 1 ) 枉z 处满足l i c q 条件 定义1 1 4 ( m f c q 条件) 设z + x ，如果集合 s + = y r 竹lv g , ( z + ) t y 0 ，j ， 则称以一f 夕在z + 处满足严格互补条件 其中 定义1 1 6 ( 二阶充分条件)设( z + ，a ) 为以j u 的一个删z 最对，若 d r v 乙l ( z + ，a + ) d o ，v0 d y ( x + ，a + ) ， y ( z + ，a 4 ) = dlv g j ( z 。) t d = 0 ，歹i ( x ) ) 则称门j j j 在z + 处满足二阶充分条件 定理1 1 2 设( z + ，a 4 ) 为门一j 一f ) 的一个肼z 羔对，若以_ f j 在z 处满足二阶充分条 件，则z 。为问题一_ f 一砂的一个局部严格极小点 定理1 1 3 设序列 矿) 存在一个聚点z + ，且z + 为f ，j j f j 的一个删z 轰，如在z + 处 二阶充分条件与严格互补条件成立，且七l _ + i r a l i z 七“一x k i | = 0 ，则一一z ，k _ o 。 i 1 基本概念 定义1 1 7 ( 可行下降方向) 设z + x ，0 d r n 纠如存在萋瓴 0 ，使 f ( x + a d ) 0 ，使 z + t d x ，vt ( 0 ，6 ) ， 则称d 为门- f - u 在z + 处的可行方向 定理1 1 4 设z x ，0 d r n ，若 v f ( x ) 丁d 0 ，使得 恕糕群邓 则称点列 扩】- 具有q q 阶收敛速度特别地， 圳若q = 1 ，q o ，称 z 七) 具有q 一线性收敛速度i 矽若1 0 ，对某个z r n ， a 丁y = c ，y 0 ，对某个y r m 4 1 2q p f r e e 算法回顾与研究现状 第一章绪论 1 2 1 q p f r e e 算法的研究意义 针对最优化问题( 1 1 1 ) ，当前大多数算法都足通过迭代算法产生一个迭代点列逐 步收敛到问题的k k t 点由于具有超线性收敛速度，自从2 0 世纪7 0 年代以后，序 n - 次规划( s q p ) 算法被认为是求解约束优化问题的最有效的算法之一，引起众多学 者的广泛关注【4 ，5 ，6 ，7 ，8 ，9 ，1 0 , 1 1 , 1 2 , 1 3 , 1 4 , 1 5 , 1 6 ，1 7 , 1 s 1 但为得到全局和超线性收敛，一般 要对求解不等式q p 子问题得到的牛顿步方向d o p 进行修正，这需在每步迭代求一个 或多个q p 子问题因此，随着问题规模的扩大，其计算量和所需的存储量变大特别 是对带有不等式约束的二次规划问题的求解，所需解的精度越高，花费的时间也越多， 稳定性相对也越差另外，s q p 方法存在一个重要缺陷，即迭代过程中形成的二次规 划子问题不一定可解，虽然可以通过采取某些调整措施使其可解，但势必会增加算法 的复杂性和计算量【1 9 2 引，或者无法建立算法的收敛性，至今，这一问题还未能得到很 好的解决对s q p 算法的详细介绍及最新进展和收敛性分析，参见文献【4 ，2 2 , 2 5 ，2 6 i 即使 s q p 算法具有超线性速度，每步迭代的计算量也较一阶最优性条件计算大所以寻求 一些适合于大规模约束优化问题的快速收敛算法，无论是对非线性最优化领域的理论 研究还是实际应用，都具有重要意义 相对二次规划来说，求解线性方程组的理论要完善的多，通过有效的利用系数矩 阵的对称性和稀疏性等一些良好性质，可以较快的求出线性方程组问题的解且求解 一个线性方程组所需的工作量和存储量相对于一个二次规划问题要少得多，且精度较 高，稳定性也较好因此探讨利用线性方程组代替二次规划子问题来获得迭代方向以 构造约束优化问题的求解方法足较理想和有意义的 1 2 2q p f r e e 算法的发展 针对问题( 1 1 1 ) ，q p f r e e 算法的产生基于如下事实： 给定一个适当的指标集l ，在点z 处，考虑如下关于( d ，a ) 的线性方程组 哆支1 7 j 二譬! + a l 入= 0 ( 1 2 1 ) g l ( x ) + a 三d = 0 ， 、7 即， ( 竺孑l ) ( 妥) = 一( 呈笛) ， 其中 9 ( z ) = ( 9 j ( z ) ，j l ) ，a l = ( v 乌( z ) ，j l ) 在可行点z 处，对于上述线性方程组，如果d = 0 ，a 0 ，则 v ，( z ) + a l 入= 0 ，仍( z ) = 0 ，0 ，j l ， ( 1 - 2 2 ) 假如令= o ，j j l ，显然，( 1 - 2 2 ) 表明z 即为( 1 1 1 ) 的一个k k t 点 l 2q p - f r e e 算法回顾与研究现状 5 记( 1 2 1 ) 产生的牛顿步方向为d s s l e ，对d s s l e 经过类似于s q p 类算法的上述 修正，同样可证明：在一定条件下，q p f r e e 类算法具有全局收敛性及超线性收敛速度 相对来讲，求解线性方程组比求解含不等式约束的二次规划要简单得多，故q p f r e e 类算法的计算量比s q p 算法少，但由( 1 2 1 ) 知，和s q p 类算法比较，q p f r e e 类 算法需解决如下问题： 1 确定指标集l 使( 1 2 1 ) 有解； 2 解决近似乘子a 的非负性； 3 构造一适当效益函数，使d ，为其一个下降方向 其实早在1 9 6 9 年m u r r a y , b i g g s 等就提出了上述q p f r e e 类算法的思想，见文【2 7 1 后来文【2 8 】进一步研究了该类思想针对问题( 1 - 1 1 ) ，为求得牛顿步方向d q p ，文【2 8 】考 虑求解如下等式约束二次规划： s t m i n 黔f ( x + ) t d + 墨d t h v g j ( x ) d 0 ，j lc 1 2 m ) ， ( 1 - 2 - 3 ) s t 玩( z ) + r= ， l ，m ) ， r 7 其中l 1 j2 ，m ) 为一适当近似积极约束集显然( 1 2 3 ) 的求解等价于( 1 2 1 ) 的求解，故引用文1 2 8 】的说法，该类算法可称为“s e q u e n t i a le q u a l i t yc o n s t r a i n e dq u a d r a t i c p r o g r a m m i n ga l g o r i t h m ”( 序列等式约束二次规划算法) 2 0 世纪8 0 年代文献【3 2 ，3 5 l ，针对问题( 1 - 1 1 ) 提出旨在不求解二次规划子问题的q p f r e e 算法其中每步迭代考虑如下的线性方程组： 日d o + v z l ( x ，a o ) = 0 ， 心v 夕j ( z ) r d o + a o j g j ( z ) = 0 ，j = 1 一m ， ( 1 - 2 4 ) 其中l ( x ，a ) = f ( x ) + a j g j ( z ) 是l a g r a n g i a n 函数，足l ( x ，a ) h e s s i a n 阵的近 j = l 似，当前点z 是解z + 的估计，c f 0 足搜索方向，而k 为x + 相应的k k t 乘子向量算 法通过将序歹, j - - 次规划方法中的一个或多个二次子规划用具有相同系数矩阵的若干线 性方程组来取代，在保证算法具有快速收敛性质的同时充分利用求解线性方程组的 一些优点，不仅降低了每一步的计算工作量，而且克服了子问题不相容的困难理论分 析和数值实验均表明，这类方法具有迭代时间少，存储量相对较小，收敛速度快等优点， 因而可以用来求解大规模非线性优化问题从而引发了人们对q p f r e e 算法的广泛研 究 文【3 2 】中，p 砂和肛 0 ，却非当前乘子的近似对于每步迭代，搜索方向d 由两 步计算得到：首先，通过求解( 1 2 4 ) 得到下降方向如，然后对如修正，得到可行下降 方向d 初始点是内点，且利用线搜索截断步方法保证迭代点不会脱离可行集的内部 在一定的条件下，得到了全局收敛性，但由于截断步导致失去了超线性收敛的性质 文【3 5 】中，肛 0 被看成与z 4 相应的当前k k t 乘子向量每步迭代，通过求解( 1 2 4 ) 得到基本方向d o ，修正方向d l 通过求解如下线性方程组得到： 兰z 啬耋d 戳花：- j u j l l d o l l p ，j 一仇， ( 1 2 - 5 ) 约v 仍( z ) t + 乌( z ) = p ，= l 一仇， r 叫 6 第一章绪论 其中y 2 ，搜索方向五是d 0 和d 1 的凸组合为了克服m a r a t o s 效应，高阶修正方向 d 通过求解以下线性最小二乘问题获得： m i n 三i l d i | 2 s t 乌( z + a ) + v 乌( z ) t d = 一砂，je ，( z ) ( 1 2 6 ) 其中i ( x ) 为在点z 处的近似积极约束集，妒是变量参数显然，( 1 2 6 ) 相当于一个线 性方程组，但和线性方程组( 1 2 4 ) 和( 1 2 5 ) 比较有不同的系数矩阵同时，提出一个 曲线搜索，以防止步长被截断和迭代点离开可行集的内部在适定条件下，证明了全局 收敛性和文( 3 2 】不同，此算法得到了两步超线性收敛但其算法每步迭代除求解两个 线性方程组之外，还需求解一个最小二乘问题，计算工作量仍很大且在算法的收敛性 方面，只能得到算法产生的点列收敛到原问题的一个稳定点，必须进一步假设稳定点 的个数有限才能得到算法收敛到k k t 点此外，算法的收敛速度也仅为二步超线性 且假设条件较强 在文【3 6 】中给出了一个求解问题( 1 1 1 ) 的新算法该新算法每步迭代只需求解三 个同系数矩阵线性方程组，计算量较文 3 5 】大为减少，且算法的一步超线性收敛性也得 到了证明与文【3 5 】中的算法相比，文【3 6 】中算法的一个重要特点，就是其每步迭代只需 求解具有相同系数矩阵的线性方程组，完全摆脱了求解最小二乘问题的困难因此，又 称其为序列线性方程组( s s l e ) 方法但为了保证新算法的全局收敛性，同文【3 5 样， 文仍需较强的假设条件( 如需初始点为可行内点，算法产生的稳定点个数有限等) ，并 且算法结构也较为复杂 针对文【3 5 】中算法存在的另外一个问题，即在l i c q 条件下，当一个与接近有效的 约束相对应的乘子变得很小时，方程组的系数矩阵就会出现病态，特别是当严格互补松 弛条件不成立时，这种病态性就很容易发生从而无法保证乘子序列的一致有界性，导 致收敛性失败类似的问题也存在于文【3 0 5 9 】中为了克服迭代矩阵的病态性，文【3 9 】在 k k t 系统非光滑方程组的基础上，通过应用f i s c h e r - b u r m e i s t e r 非线性互补函数，提 出了一个新的可行q p f r e e 算法这主要得益于近来f i s c h e r - b u r m e i s t e r 非线性互补 函数在非线性互补问题与变分不等式问题中的成功应用【4 0 ，4 1 i 每步迭代，该新算法需 求解三个具有如下形式的同系数矩阵线性方程组： ( 矾七，v 夕。z 七，t v e 七g d i a 9 0 7 ( z 七) ( 妥) = 一( v 琶z 七) ， c 1 2 7 ， 七) v 夕( 矿) te 七八a 厂 c 卜” 其中，e 为一适当向量， 谚= 丽筹丽，e 七= 一砌咖渺m = ( 1 一丽杀丽) 5 在较文【3 5 】弱的条件下( 无需假设稳定点的个数有限) 得到了全局收敛和超线性收敛速度 但，在每步迭代中，需要求解三个线性方程组和一个线性最小二乘问题以产生搜索方 向，因而算法的结构相对较复杂 文f 6 2 】进一步研究了内点q p f r e e 算法该算法利用所谓工作集定义减少了子问题 的计算量，且不需假设稳定点孤立但在算法的每步迭代中，包括工作集的计算，需求 解五个线性方程组，而全局收敛需假设近似h e s s i a n 阵一致正定 j 3 本文主要工作及内容安排 7 一般说来，找满足t 0 i n t x 的点要比找z o x 更难因此文 3 0 ，6 0 ，4 s 提出了求 解问题( 1 - 1 1 ) 的可行q p f r e e 方法通过积极集减少约束，文【钙】用一个显式公式得 到修正的可行下降方向但每步迭代仍需求解三个线性方程组和额外计算近似乘子向 量，且全局和超线性收敛仍要求稳定点孤立的假设文恻的超线性收敛无需严格互补 条件，借助广义梯度投影技巧得到一辅助可行下降方向，从而得到算法的全局收敛但 此辅助可行下降方向只确保了线性收敛，若初始点选取较差，且远离( 1 1 1 ) 的解，算 法的收敛可能较慢而文【3 0 】则需求解四个线性方程组 在文【2 9 中通过引入一种近似有效集识别技术得到一个工作集，对不等式约束优化 问题( 1 一1 1 ) 给出了几个局部牛顿型算法，算法每步只需求解一个系数矩阵对称的线 性方程组来得到迭代方向扩，避免了矩阵病态性的发生；同时，线性方程组子问题只涉 及工作集中的约束，其他约束都被忽略，从而大大减少了计算量而且，无需严格互补 假设条件成立，他们证明了算法的一步超线性甚至二次收敛性无论是从降低假设条 件还是从减少计算量的角度来讲，文【2 9 】的提出无疑足一个突破性的进展因而引起了 众多学者的广泛兴趣在文【4 2 】中把文【2 9 中的算法推广到一般约束问题，得到了一个新 的s s l e 算法无需严格互补假设条件，算法一步超线性收敛而文献【4 3 4 4 , 4 7 】也在无 需严格互补假设条件下提出了不同算法 1 3本文主要工作及内容安排 1 3 1 假设条件 为书写方便，本节针对问题( 1 1 1 ) ，对全文作如下基本假设 在算法的全局收敛性分析中，假设： h1 3 1 可行集非空，即x 0 h 1 3 2 函数，观u i ) 连续可微 h1 3 3 对任意的z x ，向量组( v 9 j ( z ) ，j ，( t ) ) 线性无关，即l i c q 条件成 立 h 1 3 4 各算法产生的点列 3 7 知) 有界 h1 3 5 问题以一j u 的稳定点是有限的 h1 3 6 矩阵序列 玩) 一致正定，即存在常数b a o ，使得 a l l y l l 2 y t 矾y b l l y l l 2 ，vk ，vy r n 在算法的超线性收敛性分析中，另作如下假设： h 1 3 7 函数，g0 i ) 二阶连续可微 h1 3 8 矾一矾，k _ o 。 8 第一章绪论 h1 3 9 在k k t 点z 及其对应的乘子向量a + 二阶充分条件和严格互补条件 成立a 满足 万，j = 1 一m 其中 h 1 3 1 0 矩阵序列 巩) 满足 乓( 巩一v ：z l ( z k , a 七) ) 扩l i = o ( 1 l d 七1 1 ) ， p k = i n a k ( a t a k ) 一1 a 善，v ：z l ( x 七，a 南) = v 2 f ( x ) + e 入；v 2 吼( z 南) j c l ( z + ) 1 3 2本文内容安排 本文对可行q p f r e e 算法进行了研究本文共分六章，各章主要内容安排如下： 第一章介绍了一些与本文有关的基本概念及q p f r e e 算法的研究历史、现状 第二章针对文献【3 5 3 9 】的算法提出了一个q p f r e e 内点算法 文献 3 5 3 9 】的算法，通过求解线性最小二乘问题获得高阶修正方向与文献【3 5 ，3 9 】不 同，本章算法的高阶较正方向d 通过求解下面线性方程组得到： h d + v 。l ( x ，入) = 0 ， 心v 毋( z ) t d - 4 - 入j a j ( z ) = 瓦，歹= 1 一m ， 其中歹= ( 玩，j ，) 是适当向量从而，所提的算法计算量较小 第三章利用积极约束集策略研究了一个可行q p f r e e 算法 与文【3 2 ，删不同，初始点可以不是内点，并用线搜索代替文【3 5 】的曲线搜索 首先，在x 南处，构造一个近似积极约束集通过求解一个规模较小的的线性方程 组得到下降方向稚再利用一些矩阵的分解技巧，求解一个具有显示表达式的可行方 向s ，且保证辅助方向d k = 稚+ s ：为在z 岛处的一个可行下降方向至于克服m a r a t o s 效 应的高阶校正方向钟则通过求解一个较小规模的线性方程组( i 厶i n 阶) 而得借 助a r m i j o 线搜索，辅助的可行下降方向d 詹保证了算法的全局收敛，同时借助于步长恒 为1 的试探性直线搜索，方向稚+ 钟确保了算法的超线性收敛率理论上，证明了当迭 代次数k 充分大时，步长为l 的试探性搜索恒成立，故此时可避免计算辅助的可行下降 方向扩 第四章针对文献 a s 的算法提出了一类计算有效的序列等式约束二次规划算法 不同于文【2 引，为避免定义精确罚函数，避免定义复杂的罚权重和深刻的理论分析， 本文通过求解线性方程组来修正方向稚，得到目标函数，的可行下降方向扩 首先? 在x 七处，构造一个近似积极约束集以及一适当向量a 七= ( 口k ，j 以) 求解 如下等式约束二次规划 m i n v f ( x 知) t d + 墨矿仇d s t 毋( z k ) + v g j ( x k ) t d = 一m i n 0 ，穆) ，j 以， 得方向稚文中向量n 南= ( q k ，j 以) 的选取保证当始= 0 时，z 岛即为问题( 1 1 1 ) 的k k t 点，从而自动保证了近似l a g r a n g i a n 乘子的非负性要求然后通过求解规模 i 3 本文主要工作及内容安排 9 相当的线性方程组来修正稚以得到可行下降方向d 七克f 艮m a r a t o s 效应的高阶校正方 向d k 则通过求解一个较小规模的线性方程组( i 以i 礼阶) 而得，从而降低了序列等式 约束二次规划类算法的计算工作量 第五章针对不等式约束提出了一个改进的可行q p f r e e 算法 以往可行q p f r e e 算法其可行下降方向需解两个或多个线性方程组( 有时包含非 线性的子问题) 本章新算法的最大特点只需求解一个线性方程组就可得到可行下降方 向，也就足说，可行下降方向由下面线性方程组得到： ( z tg ) ( 妥) = 一( v m ，( v z ) ， 其中u 为适当向量较以往可行q p f r e e 算法降低了计算量 克服m a r a t o s 效应的高阶校正方向扩由如下线性方程组得到： ( z t 剐妒- ( 埘 其中彬为克服m a r a t o s 效应适当定义的向量 最后，对上述所提出的各种算法进行了数值实验，数值结果充分表明所提出的算法 具有有效性、可行性和稳定性 第六章对全文的工作进行总结，并对今后的研究方向作出一些展望 第二章求解不等式约束优化问题的一类q p f r e e 内点算法 本章提出了一类求解不等式约束问题的可行内点q p f r e e 算法迭代点始终在可 行集的内部本算法只需求解三个具有相同系数矩阵的线性方程组在一定的条件下， 证明了算法具有超线性收敛性 2 1引言 求解优化问题( 1 1 - 1 ) ，存在两类具有超线性收敛性的算法：序列二次规划算法 ( s q p ) 【5 ，6 ，7 ，8 ，3 1 ，3 4 , 3 7 】和q p f r e e 类算法 3 0 】一般而言，s q p 算法的每步迭代需求解 一个或多个二次规划子问题，因而计算量较大在文献 3 2 矧中，提出了求解问题( 1 1 1 ) 的q p f r e e 算法，其中每步迭代考虑如下的线性方程组： h 如+ v z l ( x ，a o )