（应用数学专业论文）二次规划的改进有效集算法.pdf

摘要 二次规划是最基本也是最简单的一类非线性规划问题。由于其特殊性，并且非 线性规划问题的求解可以通过二次逼近转化为求解一系列的二次规划子问题，故 对二次规划的算法研究具有十分重要的意义 本文的研究主题是二次规划的算法研究第一章是预备知识，介绍了一些与非 线性规划相关的基本概念如梯度，h e s s i a n 矩阵，凸集，凸函数，t a y l o r 展开 式，下降方向及可行方向等第二章是求解二次规划的改进指标集算法，这里的 改进包括两个方面，一方面是在求解等式约束二次规划子问题时，引入了一种降 维算法，这种降维算法来自于李泽民教授提出的求解等式约束非线性规划问题的 一种新途径；另一方面是对搜索方向作了改进，即在尹，时，以点的梯度 投影方向作为搜索方向这两方面的改进，其最终目的都是为了减少迭代次数， 提高运算效率，通过第三章的实例及收敛性证明，充分说明了改进算法的有效性 和优越性 关键词：二次规划；有效集算法；投影梯度法；降维法 a b s t r a c t q u a d r a t i cp r o g r a n _ ：n i n gi sak i n do fs i m p l e s ta n dm o s tp r i m en o n - 1 i n e a r p r o g r a m m i n gp r o b l e mi th a v eb ev e r yi m p o r t a n ts i g n i f i c a n c et os t u d y a l g o r i t h mf o rq u a d r a t i cp r o g r a n n i n g ，d u et oi t sp a r t i c u l a r i t ya n dt h e s o l u t i o no fn o n 。1i n e a rp r o g r a m m i n gc a nb et r a n s f o r m e dt os o l v eas e r i e s o fq u a d r a t i cp r o g r a m m i n gp r o b l e m sb ym e a n so fq u a d r a t i ca p p r o x i m a t i o n t h et h e m eo ft h i sp a p e ri st h ee x p l o r a t i o no fa l g o r i t h mf o rq u a d r a t i c p r o g r a 咖n i n g i nc h a p t e rl ，w ei n t r o d u c e ds o m eb a s i cc o n c e p t i o nc o n c e r n e d w it hn o n li n e a rp r o g r a m m i n gs u c ha sg r a d i e n t ，h e s s i a nm a t r i x ，c o n v e xs e t ， c o n v e xf u n c t i o n ，t a y l o re x p a n s i o n ，d e s c e n td i r e c t i o na n df e a s i b l ed i r e c t i o n ，e t c i nc h a p t e r2 ，w eo f f e r e dam o d i f i e da l g o r i t h mf o rq u a d r a t i c p r o g r a m m i n gp r o b l e m t h em o d i f i c a t i o ni n c l u d et w oa s p e c t s ，o nt h eo n eh a n d w ei n t r o d u c e dam e t h o do fd e s c e n ti nt h ep r o c e s so fs o l v i n gq u a d r a t i c p r o g r a n m i n gs u b p r o b l e m sw i t he q u a l i t yc o n s t r a i n t sw h i c ho w et oan e w a p p r o a c ho fo p t i m i z a t i o na d v a n c e db yp r o f e s s o rz m l i ，o nt h eo t h e rh a n d w em o d i f i e dt h ed i r e c t i o no f s e a r c h ，n a m e l yr e g a r d e dg r a d i e n t - p r o j e c t d i r e c t i o na st h ed i r e c t i o no fs e a r c hw h il e i x t h ef i n a la i mo f t h o s em o d i f i c a t i o n si st or e d u c et h ed e g r e e so fi t e r a t i o na n di m p r o v et h e e f f i c i e n c yo fo p e r a t i o n a sa p p r o v e db ye x a m p l e sa n dt h ec o n f i r m a t i o no f c o n v e r g e n c e ，t h em o d i f i e da l g o r i t h mf o rq u a d r a t i cp r o g r a m m i n gi sm o r e e f f e c ti v ea n dm o r ea s c e n d a n t k e yw o r d s ：q u a d r a t i cp r o g r a n u n i n g ；a c t i v e s e ta l g o r i t h m ；g r a d i e n t - p r o j e c ta l g o r i t h m ； m e t h o do f r e d u c t i o no f d h n e n s i o n i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表 示谢意。 学位论文作者签名：易弓砭彳签字日期：川年占月中日 学位论文版权使用授权书 本学位论文作者完全了解江西师范大学研究生院有关保留、使用 学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许论文被查阅和借阅。本人授权江西师范大学研究生院 可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：易证年 签字日期：严矿年1 月甲日 日 龟厂b 徉幽 f 年 打矽 名期 签 日 师字导签 二次规划的改进有效集算法 引言 最优化是一门应用相当广泛的学科，它讨论决策问题的最佳选择之特性，构 造寻求最佳解的计算方法，研究这些计算方法的理论性质及实际计算表现虽然 最优化可以追溯到十分古老的极值问题然而，它成为一门独立的学科是在上世 纪4 0 年代末，d a n t z i g 提出求解一般线性规划问题的单纯形法之后，随之而来 的是线性规划、非线性规划、随机规划、多目标规划、几何规划、整数规划等各 种最优化理论的迅速发展，新方法不断出现，实际应用日益广泛同时在计算机 技术的发展推动下，最优化计算方法在经济计划、工程设计、生产管理、交通运 输等方面得到了广泛应用，成为了一门十分活跃的学科 二次规划问题是指目标函数为二次，而约束为线性的规划问题，它是一类最 简单且最基本的非线性规划问题至今人们在二次规划求解方面做了很多探索， 获得了很大的进展，有了比较有效的算法如文献【1 ，2 3 】中的l a g r a n g e 乘子法、 有效集法、内点算法和线性互补算法等研究二次规划的算法不仅是为了解决问 题本身，同时也是为了更好地求解非线性规划问题，因为一般函数在极小点处常 可用二次函数很好地近似，这样非线性规划的求解就可以转化为求解一系列的二 次规划问题，或者说是用二次规划来逐步逼近非线性规划( 序列二次规划法) 硕1 ：学位论文 1 预备知识 1 1 非线性规划 非线性规划问题的一般描述如下 ( n c p ) m i n f ( x ) ； ? s t 曩( x ) = 0 ，f = 1 ，2 ，m 。，( 1 1 ) 岛( j ) 0 ，i = m 。+ l ，m ( 1 2 ) 其中，工= ( 玉，而，) t r ”，f ：r “专r 1 为目标函数，鸟：彤一r i , i = 1 ，2 ，他， g l ：r “专r ，i = m e + l ，m 为约束函数， ( 1 1 ) 为问题( n c p ) 的等式约束，( 1 2 ) 为 问题( n c p ) 的不等式约束 称集合s = 缸r ”恢( 工) = o ，i = 1 ，2 ，；( 工) 0 ，i - - m 。，埘 ，为问题 ( n c p ) 的可行域s ，可行域s 中的点称为问题( n c p ) 的可行解或可行点给定上 述符号后，则非线性规划i h 题( n c p ) x n - n - i 简记作r a i n f ( x ) 在( n c p ) 中，若目标函数和约束条件均为线性的，则规划问题是一线性规划 问题，若目标函数和约束条件至少有一个是非线性的，则称该规划问题是一非线 性规划问题，此时约束条件也可只由( 1 1 ) 或( 1 2 ) 组成：若约束条件为空集，则 称规划问题为无约束优化问题；若约束条件均为线性函数，目标函数是二次函数， 则称规划问题为二次规划问题 记e = l ，2 ，他) ，j r = 所。，聊) ，l ( x ) = i l g j ( x ) = o ，i e l 对任何x r “， 称集合j ( j ) = e u i ( x ) 是在工点的有效指标集合。 称集合s 中的点工为( n c p ) 的( 全局) 最优解，若vx s ，有f ( x ) f ( x ) 成立；称集合s 中的点工为( n c p ) 的局部最优解，若存在工的一个邻域 ( x ，万) = 伽r “i i i x 一x i i - 0 ，使v 五( 0 ，万) 都有何+ 甜) 0 ， 使得对任意的五【o ，万】，i + 尉s 成立，则称向量d 是点i 处关于可行域s 的 4 二次规划的改进有效集算法 可行方向 定理1 1 0 2 2 1 设厂：r “寸r 在i r “可微如果存在向量d r 4 ，使得， 夥( 习7 d 0 ， 则d 必为f ( x ) 在点i 处的下降方向 对于具有线性约束条件的非线性规划问题 m i nf ( x ) ； s 1 a x b ， e x = 巴 ( 1 3 ) 其中，f ：r “j r 连续可微函数，彳是m x n 阶矩阵，e 是l x 刀阶矩阵，b 是聊维 列向量，p 是，维列向量有如下关于确定可行方向的充要条件 定理1 1 1 2 2 1 设i 是上述问题( 1 3 ) 的可行解在i 点有4 i = 岛，4 i 如，其 中彳= ( 芝) ，6 ( 砂则 零向量d 点i 的可行方向的充要条件是4 d 乳尉= 0 1 1 5k u h n - t u c k e r 条件 对于前面提到的，形如问题( n c p ) 的含等式和不等式约束问题的最优性条件 有下面的定理 定理1 1 2 1 1 ( k r 必要条件) 设，是问题( n c p ) 的可行解，在该点 厂，g ta i ( x ”可微，( f 仨l ( x ) ) 连续，曩o d 连续可微，并假设v g , ( j ) ， ( f i ( x ) ) 和v 噍( f ) ( ，e ) 线性无关如果工是问题( c p ) 的局部最优解，则存 在坼o l ( x ) ) 和v f ( f e e ) ，使 v f ( x ) + 咋( ，) + k v 囊o ) = 0 i e ，( ，) 眦 ( 1 4 ) 0 ，v i i ( x ) ， 若再假设吕( i 仨i ( x ) ) 在z 可微，则k t 条件可写成 5 硕士学位论文 v f ( x ) + v g , ( x ) + v v 曩( 工) = o fe，tee 蜀0 ) = 0 ， t g i 0 ， f ei ， f ei 我们将条件( 1 4 ) 称为( n c p ) 问题的尺一r 条件，满足k r 条件的可行点称为 k r 点而和h 分别是相应于约束g j ( 工) os n 鬼( 工) = 0 的l a g r a n g e 乘子， q 吕( 工) = 0 称为互补松弛条件 需要说明的是一般情况下k r 条件并不是最优性的充分条件，只有在一定的 凸性假设下充分性才能成立比如对于凸规划，k 一丁条件既是必要条件，也是充 分条件 1 2 二次规划 一个带有二次目标函数的线性约束的最优化问题称为二次规划问题其一般 模型为 ， ( q p ) n f i n ( x ) = 圭x r g x + c r x ； s j a r x = b j ， i = 1 ，2 ，小。( 1 5 ) a f x 熟，f = 他+ 1 ，m 其中厂：彤一r ，g 是刀刀对称矩阵，令e = l ，2 ，他) ，= + l ，册) ，则e 与，分别对应等式约束和不等式约束的有限的指标集，c ，x s n a t ) ，i e e u j 都 是刀维向量 如果g 是半正定矩阵，则问题( q p ) 中的目标函数是凸函数而对于二次规划， 可行域只要不空就必定是凸集，所以当g 是半正定矩阵时，任何k 一丁点必为二 次规划的全局极小点，并且当g 为正定矩阵时为唯一全局极小点 1 2 1 等式约束二次规划问题的l a g r a n g e 乘子法 对于只含有等式约束的二次规划问题( e q p ) m 访厂( 曲2 圭x r g x + c r x ； ( 1 6 ) s t a t x = 岛， i = 1 ，2 ，m 6 二次规划的改进有效集算法 假设彳= ( q ，呸，) ，b = ( 岛，6 2 ，屯) r 利用问题( 1 6 ) 的特殊性，存在同时确 定其最优解和相应乘子的方法这就是基于问题( 1 6 ) 的l a g r a n g e 函数而导出的 l a g r a n g e 乘子法问题( 1 6 ) 的l a g r a n g e 函数为 。 ( x ，五) = i l 再_ r g x + c r x - a 7 ( a r x - 6 ) ， 二次规划问题的k t 必要条件为 。 v ，l ( x ，1 , ) = g x + c - 以= 0 ， v l ( x ，彳) = 一一2 x + b = 0 ， 7 其矩阵形式为 ( 一g 4 r - 。a ) ( 旯x ) = 一( 三) c 7 ， 定理1 1 3 【i q 假设彳为列满秩矩阵，且g 为对称正定的，则矩阵( 三r - 。, 4 ) 为非奇异的，从而存在唯一的j 及兄满足方程组问题( 1 7 ) 由定理1 1 3 可知，等式约束二次规划问题( 1 6 ) 的求解在满足一定条件下可 通过求解方程组( 1 7 ) 得到 7 硕士学位论文 2 二次规划的改进有效集算法 一个带有二次目标函数的线性约束的最优化问题称为二次规划问题通常， 二次规划问题叙述如下： ( q p ) n u n f ( x ) = 去，g x + c7 工； 厶 s 1 a ；x = 岛，i = 1 ，2 ，m e ， 矿工6 ： ，f = ，唿+ 1 , - - - , m 其r p f ：r 4 专尺，g 是刀，对称矩阵，令e = l ，2 ，m e ) ，= + 1 ，m ) ，贝, t j e 与，分别对应等式约束和不等式约束的有限的指标集，c ，x 和 q ) ，f e u j 都 是刀维向量 如上所述的二次规划问题是一类比较简单的非线性规划问题，在最优化理论 与算法的研究中处于十分重要的地位，一方面，它在现实生活中有着广泛的应用； 另一方面，许多非线性规划问题的求解要以二次规划的解法为工具，因此备受最 优化研究界的重视 2 1 带等式约束的二次规划求解 这一节，我们介绍一种求解带等式约束的二次规划问题的个新算法，即具 有如下形式的二次规划问题： ( e q p ) n l i n f ( x ) = 乏1 石t 伍+ c r x ； s ：i a t x = 岛， i = l ，2 ，m 引理2 i t l 0 1 ( 隐函数定理)设有方程组h ( x ) = 0 ，其中x r “，h ：r 4 一尺1 ， 设朋 刀，记办( 功= ( ( x ) ，( z ) ，( 力) 若p = ( 矸，毛o ，衅) r “满足： ( 1 ) 在石。的某邻域内j i l c 9 ，p l ； ： ( 2 ) h ( x o ) = 0 ； ( 3 ) m m 阶雅可比矩阵 窖 二次规划的改进有效集算法 j = a ， ( x o ) a ( x o ) 屯ak 纸( x o ) a h r , ( x o ) a x 为非奇异的 则存在p = ( 0 小z ) r ”的一个邻域u ，使得x i ，一，毛是j = ( + ，毛) u 的函数，记作薯= 谚( j ) ，i = 1 ，m ，具有下列性质： ( 1 ) 谚c pp 1 ： ( 2 ) # = 谚( j o ) ，f = 1 ，聊； ( 3 ) 曩( 识( j ) ，九( j ) ，j ) = 0 ，i = l ，m ，i u 现在考虑等式约束问题 ( 正)m i n 厂( x ) ； s f g ( 工) = 0 其中石r ”，厂：r “一r ，誊：r ”专r 4 ，m 0 ，歹i ( x ) ，则由定理2 4 及k r 条件可知尹即为原问题( 2 1 4 ) 的最优解 b ) 若矽，j i ( x ) 中有负值，设衫= m i n 2 jl j ，( x ) 】，显然 o ，这 时令，”= 尹，以+ 。= 以、 ，) ，重复计算( 2 1 5 ) 2 ) 若尹，因矿，分别是( 2 1 5 ) 的最优解与可行解，故必有 厂( ) 岛，此时尹虽然是( 2 1 5 ) 式的最优解，但不是原问题的可行解 令d = - i 一，因为厂( 尹) 厂( ，) ，故是下降方向选取适当的， 使得，”= ，+ d 为可行点，并计算有效指标集以+ l ，重新计算( 2 1 5 ) 式 1 7 硕士学位论文 2 2 2 投影方向 定义2 5 【2 2 1 设u 是的子空间对于任意的x e ”可唯一地分解为 x = y + z ，其中y u ，z u 上， 由e ”n u 的这种映射记为p ，即p x = y ，称p 为由f 到其子空间u 的正交投影 矩阵 定理2 6 嗍设q ，口2 ，a r 是子空间u 的一个基底向量组，由行向量 口j ，口；，缉t 所组成的矩阵记为 n r = n j 以； ： 衫 或n l - - ( a , ，哆，口，) ， 则由f 到u 的正交投影矩阵p 可表示为 p = n ：博r n ：丫l nrl 由矿到【，上的正交投影矩阵qn - i 表示为 q = i - n ：( nr n ：丫1 n r 其中，是r l 阶单位矩阵 推论l 若p 是正交投影矩阵，则，= p 尸p = p 推论2 若尸是正交投影矩阵，则尸是半正定的 定理2 7 2 2 1 设x 是问题( q 一的一个可行解，假设厂在x , - y 微，在x 点处有向 量组 口j ) ，j x ( x ) u e 为线性无关的，则= 最 口； ： 越 是满秩的，q = ，一r ( n n r ) - 1 n 为正交投影矩阵，d = 一q v f ( x ) 为负梯度方向的投影方向，若d 0 ，则必为下 降可行方向 证明因为q 是正交投影矩阵，所以有 1 8 二次规划的改进有效集算法 、盯( x ) rd = 一1 盯( x ) r ! 三! v 厂( 石) = - v f ( x ) 7q r i 2 r 盯( 工) = 一i i q v f x ) 1 1 2 o ， 故d 是下降方向又因为 n d = 一n q v f ( x ) = - n ( i n r ( n n 7 ) 一n ) v f ( x ) = 一( 一 9 v f ( 曲= 0 ， 由定理1 1 1 可知，d 是可行方向 2 2 3 改进的有效集算法 由上两部分的讨论可知，有效集算法是一个非常有效的求解凸二次规划的方 法美中不足的是在调整以的过程中，当尹，时，则以扩= 尹一，作为搜索方 向，虽然这也保证了d 为下降方向，但不能保证为最速下降方向如果要提高收 敛速度的话，我们希望能找到一个d 能尽可能快地收敛于原问题的k r 点又 因为投影方向可看作是负梯度方向一可( ) 在点满足现有等式约束意义下的 最速下降方向基于以上考虑，可以将投影梯度算法的方法引进来，将一夥( ) 在 点的投影方向作为搜索方向从而对有效集算法作如下的修改： 设，是问题( 2 1 4 ) 的一个可行解，且有效指标集为以o ) = e u i ( x ) ，求解 相应的等式约束i h tj 题( 2 1 5 ) ，假设所得的解为尹且相应l a g r a n g e 乘子向量为矿， 首先检验 z ；0 ， w i ( x ) ， ( 2 1 8 ) 彳矿 岛，v f i l ( x ) ， ( 2 1 9 ) 两个条件是否同时满足，若满足，则尹为原问题的最优解 否则判断= 是否成立，如果成立，则必有条件( 2 1 8 ) 不成立此时 ， jjz l ( x ) ，使得剪 o , i l l ( x k ) ) ，找出，+ 1 对应的有效指标集以+ ， 重新求解( 2 1 5 ) 式下面给出具体的算法步骤： 算法2 2 步1 选定初始点一及相应的有效指标集以，令七= 1 ； 步2 运用算法2 1 求解等式约束二次规划问题( ) 式，设其解为，相应 l a g r a n g e 乘子为； n f i n 厂( x ) = 互1 t g x + c r 工： s t a t x = 岛，i 以( j ) ( ) 步3 检验妒，是否满足条件( 2 1 8 ) ，( 2 1 9 ) ，若满足，则妒为原问题的最 优解，否则转步4 ， 步4 若尹：，转步5 ，否则转步6 ； 步5 找出= m i n 2 j1 1 l ( x ) ) ，令工“1 = 尹，以+ 。= 以 ，) ，k = k + l ， 转步2 ； 步6 取m = ： ， ，2 9 1 9 ) = ，( x ) ，计算g = ，一孵( m w ) 1 i ，及 夥( ) ，从矿出发沿扩= - q , v f ( x ) 方向作一维搜索，记工“1 - x + 吼d ，计算 步长幺= 疵 篙笋肛叫，) ，找彬点的有效指标鼽。， 令七= j j + 1 ，返回步2 二次规划的改进有效集箅法 2 2 4 算法的收敛性 对于上一章中算法2 2 的收敛性有下面的两个定理 定理2 8 若g 为半正定的，则由算法2 2 产生的点列 工) ，满足对任意的整 数k 0 ，必有f ( x k + 1 ) 厂( z ) 证明算法2 2 中在不满足最优性检验条件的情况下无非出现两种情况，即 i = 工和i x 若尹= i f ，则由算法2 2 中步5 ，显然有厂( 工“1 ) = 厂( ，) ； 若尹，算法2 2 采用了负梯度方向的投影方向作为搜索方向且由定理 2 7 可知 w ( 矿) r d o ， 另由g 为半正定，所以目标函数为凸的， 即有 f ( x “1 ) 厂( ) ， 综上可知，对任意的七o 有f ( x k + 1 ) f ( 2 ) 定理2 9 设点列 由算法2 2 产生，且矩阵g 为半正定的，x 1 f f ：f q k 都= f f 口i ，f e u i ( x * ) 线性无关，则算法必有限终止于问题( q p ) 的k r 点 证明由算法2 2 中步3 可知，如果算法有限终止，则必终止于问题( 的 k r 点下面证明算法2 2 必有限终止 假设算法不有限终止，由于只有有限多个约束，以只可能有有限个不同的集 合，因此至少有一个z 将重复出现无限次设j o ，故尹= 佳号) r 为原问题的最优解 解法2 ( 算法2 2 ) 已知g = ( 三：) ，c = ( 一- 一。) r ，e = 刀，= - ，2 ，3 1 取初始可行点x 1 = ( oo ) r ，则以= 2 ，3 ) ，运用算法2 1 求解相应等式约束问题 r a i n f ( 工) = i i 工_ t g x + c r x ： s j 玉20 ， 一而= 0 解得i 1 = ( oo ) r ，五1 = ( 雹) r = ( 一1 1 0 ) r ，此时不满足条件( 2 1 8 ) ，( 2 1 9 ) 因为妒= 一，且硝= m i n 2 ：，爿) ，所以令x 2 = 一，以= 以 3 l = 2 ，运用算法 硕士学位论文 2 1 重新计算等式约束子l 司题 m i n f ( x ) = 丢x r g x + c o ： s j 一五= 0 解得i 2 = 0 三) ，五2 = ( 鸳) = ( - 争，不满足检验条件( 2 1 8 ) ，( 2 1 9 ) 因为i 2 x 2 ，取2 = ( 一1 。) ，计算q = ，一孵( n e n ；) 1 2 = ( ：) ，可( 石2 ) 划( 珊 则d 2 = 一q 可c x 2 ，= ( 品) ，哆= m i n 二! 竺三爹；垒! i 衫d 2 。， - ，3 ) ) = 孟， 从而x 3 = x 2 + o t z d 2 = ( 03 ) 7 ，且有以= 1 ，2 ) ，运用算法2 1 重新计算等式约束问 题m i n f ( x ) = 丢，g x + c t 工： s j 3 玉+ 2 x 2 = 6 ， 一= 0 解得尹= ( o3 ) 7 ，彳3 = ( 霄雹) r = ( 一1 7 ) r ，不满足检验条件( 2 1 8 ) ，( 2 1 9 ) 因为i 3 = 工3 ，且雩= m m g ，墨) ，则令= 尹，以= 以 2 ) = 1 ) ，运用算法2 1 重新计算等式约束问题 r a i n y ( x ) = l x r g x + c r z ： 多j 3 五+ 2 x 2 = 6 解得_ = 偿詈) 2 ，= ( 彳) = ( 争o 且有衫尹 包，v f 2 ，3 ) ，故尹为原问题 的最优解 由上两例可见算法2 2 具有的优越性首先，两种算法都是要反复的求解等式 约束二次规划子问题，而算法2 2 在求解等式约束二次规划子问题时采用了算法 2 1 ，它本身就是一个降维算法，i ：gl a g r a n g e 乘子法要节省存储空间而且，从 例3 2 两种算法的比较中，我们可以看到，有效集算法的迭代次数为5 次，而改 进算法的迭代次数为4 次，这就意味着改进算法以更快的下降速度向最优解靠 近，从而提高了收敛速度本人通过大量的实例证实算法2 2 确实具有更快的收 敛凉度 二次规划的改进有效集算法 参考文献 1 m s 巴扎拉，c m 希蒂著，王化存，张春柏译，非线性规划一理论与算法 m 贵州人民出版社，1 9 8 6 4 陈开明非线性规划 m 复旦大学出版社，1 9 9 1 2 t f c o l e m a na n da r c o n n o nt h el o c a lc o n v e r g e n c eo faq u a s i n e w t o n m e t h o df o rt h en o n l i n e a rp r o g r a m m i n gp r o b l e m s i a mj n u m e r a n a l ，2 5 ( 1 9 9 8 ) ， 4 3 3 4 6 0 3 c w c r y e r ，n u m e r i c a lf u n c t i o n a la n a l y s i s ，c l a r e n d o np r e s s ，o x f o r d ， 1 9 8 2 4 3 w c d a v i d o n ，v a r i a b l em e t r i cm e t h o d sf o rm i n i m i z a t i o n ，a r g o n n en a t i n a l l a b sr e p o r t ，a n l 一5 9 9 0 5 g b d a n t z i g ，l i n e a rp r o g r a m m i n ga n de x t e n s i o n s ，p r i n c e t o nu n i v e r s i t y p r e s s ，p r i n c e t o n ，n e wj e r s e y ，1 9 6 3 6 管梅谷，郑汉鼎线性规划 m 山东科学技术出版社，1 9 8 3 7 何坚勇最优化方法 m 清华大学出版社，2 0 0 7 8 胡毓达非线性规划北京：高等教育出版社，1 9 9 1 9 胡运权等运筹学( 修订版) m 清华大学出版社，2 0 0 5 1 0 李泽民最优化问题的一种新途径 j 重庆建筑工程学院学报，1 9 9 0 ，1 2 ( 1 ) 4 9 - 5 5 1 1 刘光中凸分析与极值问题 m 高等教育出版社，1 9 8 4 1 2 d g l u e n b e r g e r i n t r o d u c t i o nt ol i n e a ra n dn o n l i n e a rp r o g r a m m i n g ( 2 n d e d i t i o n ) m a s s a c h u s e t t s ：a d d i s o n w e s l e y ，1 9 8 4 1 3 g p m c c o r m i c k n o n l i n e a rp r o g r a m m i n g ：t h e o r y ，a l g o r i t h m s ，a n da p p l i c a - t i o n s n e wy o r k ：j o h nw i l e ya n ds o n s ，1 9 8 3 1 4 w s u n ，o nc o n v e r g e n c eo fa ni t e r a t i v em e t h o df o rm i n i m a xp r o b l e m ， j o u r n a lo fa u s t r a lj a nm a t h e m a t i c ss o c i e t y ，s e r i e sb