（应用数学专业论文）线性等式约束非线性规划问题的wolfe改进算法.pdf

摘要 本文讨论了约束非线性规划问题的一种w o l f e 改进算法，为非线性规划算法 的研究提供了一种新途径首先本文在w o l f e 既约梯度法的基础上，针对具有线 性等式约束的非线性规划问题和二次规划问题，引入了精确的一维搜索，得到了 带一维搜索的新算法( 算法1 、2 ) ，并给出了算法的收敛性证明其次，本文把 上述算法应用于各个具有等式约束的非线性规划问题中：具有非线性等式约束的 非线性规划问题、具有混合约束的非线性规划问题、具有线性等式约束的非线性 多目标规划、具有一般等式约束的非线性多目标规划问题、具有混合约束的非线 性多目标规划问题，得到了一系列带一维搜索的改进算法文中对提出的各算法 进行了大量的实例验证，表明了带搜索的新算法的可行性和有效性 划 关键词：线性等式约束，非线性约束，二次规划，精确一维搜索，多目标规 a b s t r a c t i nt h i sp a p e r , a ni m p r o v e da l g o r i t h mo fw o l f ef o rt h ec o n s t r a i n e dn o n l i n e a r p r o g r a m m i n gp r o b l e mi sd i s c u s s e da n dw co f f e ra n e ww a yt or e s e a r c hm e t h o d so f n o n l i n e a rp r o g r a m m i n gb yt h a t f i r s to fa l l ，o nt h eb a s eo ft h er e d u c e dg r a d i e n t m e t h o do fw o l f e ，w ea d d e da c c u r a t eo n ed i m e n s i o ns e a r c h i n gm e t h o di n t o i ta n d g a i n e dan e wa l g o r i t h m ( a l g o r i t h m1 , 2 ) f o rt h en o n l i n e a rp r o g r a m m i n gw i t hl i n e a r e q u a l i t yc o n s t r a i n t sa n dq u a d r a t i cp r o g r a m m i n gp r o b l e m s ，a n dp r o v e dc o n v e r g e n c e o f a l g o r i t h m ，t h e n ，w eu s ea b o v ea l g o r i t h m si n t oo t h e r n 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 w i t he q u a l i t yc o n s t r a i n t s ，s u c ha s ：n o n l i n e a rp r o g r a m m i n gp r o b l e mw i t hn o n l i n e a r e q u a l i t yc o n s t r a i n t s ，n 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 w i t hm i x e dc o n s t r a i n t s ， n o n l i n e a rm u l t i o b j e c t i v ep r o g r a m m i n gp r o b l e mw i t hl i n e a re q u a l i t yc o n s t r a i n t s ， n o n l i n e a rm u l t i o b j e c t i v ep r o g r a m m i n gp r o b l e mw i t hg e n e r a le q u a l i t yc o n s t r a i n t s ， a n dn o n l i n e a rm u l t i o b je c t i v ep r o g r a m m i n gp r o b l e mw i t hm i x e dc o n s t r a i n t s w es e t u ps e r i e so fi m p r o v e da l g o r i t h m sw i t ha c c u r a t eo n ed i m e n s i o ns e a r c h i n gm e t h o d m o r e o v e ral o to fn u m e r i c a le x a m p l e sh a v eb e e ng i v e nf o rn e wa l g o r i t h m s ，s h o w e d t h en e wa l g o r i t h m sw i t ha c c u r a t eo n ed i m e n s i o ns e a r c h i n gm e t h o da r ef e a s i b l ea n d e f f e c t i v e k e y w o r d s ：l i n e a re q u a l i t yc o n s t r a i n t s ；n o n l i n e a rc o n s t r a i n t s ；q u a d r a t i cp r o g r a - m m i n g ；a c c u r a t eo n ed i m e n s i o ns e a r c h i n g ；m u l t i o b j e c t i v ep r o g r a m m i n g n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得或其他教育机构的学位或证 u 。书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示谢意。 学位论文作者签名：桓蓝霍 签字日期：2 糟年5 月巧日 学位论文版权使用授权书 本学位论文作者完全了解江西师范大学研究生院有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被 查阅和借阅。本人授权江西师范大学研究生院可以将学位论文的全部或部分内容 编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学 位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：懈 签字日期：加咎年占月玛日色赢 2 6侈k 彳硝 各啦 参 阳 稚 字 线性等式约束非线性规划问题的w o l f e 改进算法 引言 非线性规划是计算数学和运筹学交叉的学科，对非线性规划模型的研究源于 实际生活中对问题进行更为精确的描述并解决的迫切需要非线性规划理论是基 于线性规划理论发展起来的，自上世纪4 0 年代人们获得求解线性规划问题的单 纯形法之后，线性规划在理论上日趋成熟，并在实践中获得广泛的应用，然而随 着社会各个方面的发展，许多实际问题用线性规划理论建立模型并解决的效果并 不好，这种情形促使科学研究转移到非线性领域近几十年来许多专家和学者为 有效地求解非线性规划问题付出了艰辛的探索，促使非线性规划理论不断成熟和 完善对非线性规划算法的研究主要集中在如何提高算法的效率以及扩大算法的 适用范围按数学空间划分，理论上可将非线性理论的研究分为有穷维优化和无 穷维优化，由于现实条件的限制，目前已经实现的大多数非线性规划算法只限于 有限维空间，而且相应的理论也比较成熟在无穷维空间上，随着许多优化学者 和专家地深入研究，这方面的研究成果不断涌现，将很多有限维空间的理论推广 到无穷维空间 本文主要是在w o l f e 简化梯度法的基础之上对具有等式约束的非线性规划 和多目标规划问题提出了一些改进的算法，属于分析研究 硕士学位论文 1 预备知识 1 1 非线性规划的结构及一些基本概念 非线性规划问题的一般形式是 i m i n f ( x ) ； ( c p ) s t 吃( x ) = 0 ，i = 1 ，2 ，z ， 【 毋( ) 0 ，j = j + 1 ，研 ( 1 1 ) ( 1 2 ) 其中，x = ( ，x 2 ，x n ) t r 4 ，f ：尺4 一r 为目标函数，鬼：r ”专r i , f _ 1 ，2 ，； 毋：r “一r 1 ，j = ，+ 1 ，所为约束函数，其中( 1 1 ) 为问题( 删的等式约束，( 1 2 ) 为问题( c p ) 的不等式约束称集合s = x 尺”限( x ) = o ，f _ 1 ，2 ，l ；g j ( x ) o ， j = ，+ 1 ，m ) 为问题( n c p ) 的可行域，可行域s 中的点称为问题( n c p ) 的可行解 或可行点给定上述符号后，则非线性规划问题( c p ) 又可简记作囊p 厂( x ) 在 ( n c p ) 中，若目标函数和约束条件均为线性的，则规划问题是一线性规划问题， 若目标函数和约束条件至少有一个是非线性的，则称该规划问题是一非线性规划 问题，此时约束条件也可只由( 1 1 ) 或( 1 2 ) 组成；若约束条件为空集，则称规划 问题为无约束优化问题；若约束条件均为线性函数，目标函数是二次函数，则称 规划问题为二次规划问题 记e = l ，2 ，毋，= + l ，z ，( x ) = 歹i g j ( x ) = o ，+ l m ，对任 何x r “，称集合a ( x ) = e u i ( x ) 是在x 点的起作用集合 称集合s 中的点x 为( c p ) 的( 全局) 最优解，若 s ，有f i x ) f ( x ) 成立；称集合s 中的点x 为( c p ) 的局部最优解，若存在x 的一个邻域 ( x ，万) = x r ”l i i x 一x 0 研，v x sn ( x ，万) ，有厂( x ) 厂( x ) 成立没 对目标函数和约束条件作特别限制的条件下，我们一般只能得到( c 尸) 的局部最 优解 线性等式约束非线性规划问题的w o l f e 改进算法 1 1 1 梯度、h e s sia n 矩阵 假定厂：dcr ”专r 1 为连续可微函数( 厂c 1 ( d ) ) ，则定义厂( x ) 在x 处的梯 度为甩维向量 夥c 耻( 掣，警，掣) t 假定厂：d c r 8 一r 1 为二阶连续可微函数( 厂c 2 ( d ) ) ，则定义厂( x ) 在x 处 的h e s s i a n 矩阵为据嚣对称矩阵 h ( x ) = v 2 f ( x ) = a 2 f ( x ) a 2 厂( x )0 2 f ( x ) 研 缸：苏。饥钆 竺 盟翌丛茎! 坌：丛塑 钆鹾弧 a 2 f ( x ) a 2 f ( x )a 2 f ( x ) 挑魄瓯鹾 1 1 2 凸集、凸函数及t a ylo f 公式 定义1 1 例非空集合scr ”称为凸集，若对于任意的x 1 ，x 2 s 和任意实数 五( o ，1 ) ，有2 x 1 + ( 1 一兄) x 2 s 成立全空间r ”是凸集，规定空集。也是凸集 定理1 1 9 1 集合scr “是凸集的充要条件是对于任意正整数k 2 ，若点 x 1 s ，x 2 s ，x s ，则点丑x 1 + 五x 2 + + 五x s ，其中，以o ( i = 1 ，2 ， 量 ，七) 且五= 1 ，称a x l + + 五x 为x 1 ，x 的凸组合 定义1 2 9 1 设厂：scr ”专r 1 ，其中s 是一非空凸集，如果对于任意的x 1 ， x 2 s 及任意的实数名 0 ，1 都有f ( 2 x 1 + ( 1 一五) x 2 ) 2 f ( x 1 ) + ( 1 2 ) f ( x 2 ) 成 立，则称厂为s 上的凸函数 5 定理1 2 9 1 设scr ”是非空开凸集，f ：s 专r 1 在s 可微，贝, l jf 是s 上的凸 函数的充要条件是对于任意两点x 1 ，x 2 s ，都有厂( x 2 ) f ( x 1 ) + w ( x 1 ) t ( x 2 硕士学位论文 一x 1 ) 定理1 3 9 1 设scr 4 是非空开凸集，f ：s 专r 1 在s2 ：- 阶可微，则f 是s 上的凸函数的充要条件是：对于每一点x s ，f 在x 处的h e s s i a n 矩阵( x ) 在r ”中是半正定的 对于非线性规划问题( n c p ) ，若可行域s 是凸集，函数厂是可行域s 上的凸 函数，则称问题( n c p ) 为凸规划凸规划的任一局部最优解都是它的整体最优解 定理1 4 ( t a y l o r 公式) 设厂在开凸集线c 7 月“上可微，z 岛，当恻l 充 分小时，有厂( x + 厅) = 厂( x ) + 夥( x ) t h + o ( h 1 1 ) 1 1 3k u h n l t u c k e r 条件及收敛性定理 定理1 5 1 9 1 ( k u h n t u c k e r 条件) 设x 为( n c p ) 的可行解，在该点厂，g ，( j i ( x ) ) n - n - 可，傲，g j ( 萑，( x ) ) 连续，曩( f = 1 ，2 r ) 连续可微，再假设v g j ( x ) ( ，( x ) ) 和v h , ( x ) ( i = 1 ，) 线性无关如果x + 是( ( ) 的局部最优解，则存在 u i o = 1 ，) 和v j ( j ，( x ) ) ，使得 i i jv f ( x ) + 酗v 懈) + j e t ( x ) 匕w ) _ o ， ( 1 3 )气 f = l i i j ， 【 巧o ， v je ( x ) 条件( 1 3 ) 叫做( i 叩) 的k u h n t u c k e r 条件，简称k 一丁条件，凡满) 黾k - t 条件 ( 1 3 ) 的可行点都叫做( n c p ) 的k 一丁点 定理1 6 t l l 设s 是r 8 中一非空闭集，并设f ：r ”寸r 1 连续可微考虑f ( x ) ， 受约束于x s 的极小化问题此外，考虑任何一个这样的可行方向算法，其映 射a = m d 定义如下给出x ，( x ，d ) d ( x ) 意味着d 是厂在x 的一个下降可行 方向而且，y m ( x ，d ) 意味着y = z + 2 d ，其中见是f ( x + 2 d ) 受约束于五0 和x + 2 , d s 的极小化线搜索问题的解设 x ) 是由该算法产生的任一序列， 4 线性等式约束非线性规划问题的w o l f e 改进算法 并设 d ) 是相应下降可行的方向序列则不可能存在具有下面性质的子序列 ( ( x ，d ) 水： 1 x 一x ，尼k ， 2 d 专d ，k k ， 3 存在某个万 0 ，对一切兄 o ，万】和每个k k ，有x + 名d s ， 4 v f ( x ) t d 0 ，使得对于任意的五( o ，万) ，均有j + 名p s ，则称p 为点j 处 的可行方向 定理1 7 【9 i 设：尺”专r 1 在j r ”可微如果存在向量p 尺”，使盯( 足) t p 0 ，则p 必为f ( x ) 在点j 处的下降方向 考虑具有线性约束条件的非线性规划问题 m i n 厂( x ) ； c p h ， 篆兰 其中厂：r ”一r 1 是连续可微函数，a 是m r l 阶矩阵，e 是l xn 阶矩阵，b 是聊维 列向量，e 是，维列向量 定理1 8 【9 】设j 是问题( 即的可行解在又点有4 元= 6 l ，4 牙 6 2 ，其中， 彳= ( 芝) ，6 = ( 乏 ， 则非零向量p 是点j 处的可行方向的充要条件是4 p 0 ， e p = 0 一个向量p ，若既是函数在点j 处的可行方向，又是在点j 处的下降方 向，则称这个方向为函数在点j 处的可行下降方向 1 1 5 最优化算法的结构 硕士学位论文 最优化算法通常采用迭代方法求得最优解，因而对其研究主要包括对特定非 线性规划模型如何构造寻求问题最优解的迭代点列，迭代算法的收敛性及算法收 敛速度的估计等其基本思想是：从一个选定的初始点出发x o r ”，按照某一 特定的迭代规则产生一个点列 x ) ，使得当 x ) 是有穷点列时，其最后一个点 是( n c p ) 的最优解：当 x 是无穷点列时，它有极限点，并且其极限点是( n c p ) 的最优解 最优化算法的基本结构如下 步骤1 确定搜索方向d ，即构造厂在点x 处的可行下降方向作为搜索方向 d ； 步骤2 确定步长因子五，使目标函数值有某种意义上的下降； 步骤3 令x “1 = x + 五d ，若z “1 已满足某种终止条件，停止迭代，得到 近似最优解x “1 ；否则，重复上述步骤 1 2 多目标规划 多目标最优化问题是在给定的条件下，同时要求多个目标都尽可能好的最优 化问题多目标规划就由此而产生，它是数学规划的一个重要分支它的一般形 式是 ( 仰m ! n ( x ) = ( z ( x ) ，正( x ) ，f a x ) ) 1 其中，r = x r 4 ：h ( x ) = ( j z l ( x ) ，( x ) ) t = o ；g ( x ) = ( g 。( x ) ，g ，( x ) ) t o ) 解多目标规划目前有多种方法，本文解决多目标规划问题的途径是将多目标 规划转化为单目标规划问题求解下面介绍多目标规划几种解的定义 定义1 40 5 ( 绝对最优解) 设x r ，如果对任意的x r ，均有 f ( x ) 厂( x ) ，即有z ( x ) z ( x ) ，江l ，p ，则说x 是( 的绝对最优解；绝 对最优解可以说是一种最理想的解，实际中这种解往往不存在 定义1 5 1 5 1 ( 有效解) 设x 。r ，如果不存在x r ，使得f ( x ) f ( x ) ， 则说x 是( 胪) 的有效解 6 线性等式约束非线性规划问题的w o l f e 改进算法 定义1 6 ”1 ( 弱有效解) 设x + 尺，如果不存在x r ，使n f ( x + ) ( ) ， 则说x 是( 幽的弱有效解 定义1 7 【1 5 1 ( 真有效解) 设j r 是( 即) 的有效解，并且存在正数m ，对任 意的砸f p ) ，当x r ，彳( x ) z ( 贾) 时，必有某个_ ，( 1 j p ) 使得，( j ) 一 z ( x ) 蛆善p 五= 1 ) ， 八+ 叫娟，圳t 卜。，且喜五_ l ， 7 硕士学位论文 2 线性约束非线性规划问题的改进算法 文献 1 给出了求解非线性规划问题的一种既约梯度法，本文是在这个算法 的基础上引入了一维搜索，得出了求解具有线性等式约束非线性规划问题的一种 改进算法，且在后面给出了算法的收敛性，并通过实例对算法的正确性加以了验 证 2 1 线性等式约束非线性规划问题 考虑下面非线性规划问题 ( 露) 仁m i n 趔f ( x 乩) ； 其中厂：r ”一r 1 是二阶连续可微函数，a 是m l l 阶矩阵，设a 中有一个m 阶非 奇异子块 b = 口l 口1 岛 口2 以2 f 2 口以啦 口l a 2 & 口峨 ，并记n = 以l 口l 止 a 2 aa 2 a n 嘲la - ，l i l ( 其中m + p = 疗，且变量下标不一定连续) 下面我们来确定问题( 只) 的一个可行下降方向 设是问题( 曰) 的可行解，由上面假设，可以分解彳= ，) ，x t = ( 霹，磙) ， 其中b ；是m xm 可逆矩阵由于问题( # ) 是属于( p ) 的类型，于是由定理1 8 知， 若非零向量d 满足彳d = 0 ，则d 是( 置) 的可行方向若同时还满足耵( ) t d o ， 则d 就是( 日) 在点石处的可行下降方向 与a 的分解相对应，分解d t = ( d i ，d j ) ，由a d = o 得b 叱+ m = 0 ，即 d b = 一b n d , v ， ( 2 1 ) 厶 矗 略 蛳彤一 蛳 线性等式约束非线性规划问题的w o l f e 改进算法 又由似= 6 ，得且k 十m k = 6 ，即= b 1 b - b n x ，于是目标函数为 f i x ) = 厂( ，瓦) = f ( b b - b 一，“) ， ( 2 2 ) 设其梯度为， ，= v 厂( x ) 一( b 1 ) t v 占厂( x ) ， ( 2 ：3 ) 舯 吖c 耻l 警，辈，掣 ，i 吒吒吒j v 朋的- 【掣，掣，掣j _ ，1 哆， 令，t = ( 毋，巧) = 夥( x ) t - v 丑( x ) t ( b 。彳) = ( o ，v ，厂( x ) t - v 口( x ) t ( b - 1 忉) ， ( 2 4 ) 由( 2 1 ) 和( 2 4 ) 式得， v f ( x ) t d = v 且厂( x ) t d b + v ( x ) t d v = ( v ( x ) t - v 口( ) t b n ) d = 砖九， ( 2 5 ) 为使d 是可行下降方向，只要选“使砖九 0 ； ( 2 ) 若p g ) l o ，停止，无解；否则转( 4 ) ； ( 4 ) 令丑卅= 一罟，若h 卅一以i ，得最优步长五+ l ；否则令f = f + 1 ，转( 2 ) ， 得到解为以，令x m = x + 以d ，后= 后+ 1 ，返回s t e p 2 2 1 1 算法的收敛性 定理2 1 设彳是问题( 足) 的可行解，分解彳= ，) ，x t = ( 耐，霹) ，其 中b 是m m 可逆矩阵，假设厂在x 处可微，并令，t = v f ( x ) t v 口( x ) t ( b - 1 彳) ， 设d t = ( 以，) 按( 2 6 ) 式的规则构成，则x 是k 一丁点的充分必要条件是d = 0 证明x 是问题( e ) 的k t 点，是指存在向量“，使得v f ( x ) t + “t a = 0 ， 则上式可分解为： v v s f 。( x x ，) t t + + “u t t b = ：o 。, - c 2 7 ， 由v 占( x ) t + “t b = 0 ，可得“t = - v b 厂( x ) t b ，再代人v j v 厂( x ) t + 比t = 0 ，则 有v ( x ) t - v 口厂( x ) t b n = o ，得巧= o ，即，= 0 又由d 的定义( 2 6 ) 知 d = 0 ，从而d 口= 0 ，即d = 0 反之，若d = 0 ，则由d 的定义( 2 6 ) 可知，= 0 ，取“1 = 一v 口厂( x ) t b ， 则有( 2 7 ) 式成立，亦即x 是k 一丁点 定理2 2 考虑问题( 只) ，设厂( x ) 满足二次连续可微，水平有界，凸 函数，令 x ) 是由算法2 1 产生的点列，则 ( 1 ) f ( x ) ) 是严格单调下降数列，且! i mf ( x ) 存在， ( 2 ) ) 的每一个聚点x 满足d + = 0 ， ( 3 ) x ) 的任意聚点都是问题( 露) 的最优解 证明( 1 ) 由算法2 1 可知，方向d 为下降方向，即v f ( x ) t d 0 足够小时) ， f ( x + 1 ) - f ( x + 五d ) = m i n f ( x + 2 d ) 硕士学位论文 ( x + t d ) = 厂( x ) + a v f ( x ) d + 旯例卜 0 ，有f ( x + 2 d ) f ( x + ) ， 又 f ( x “1 ) = f ( x + 五d ) ( x + 2 d ) ， 令 k n ，k o o ，得厂( j + ) ( x + + l d ) f ( x + ) ， 与假设矛盾，故d = 0 ( 3 ) 因 x ) 为有界点列，所以 肖) 必有收敛子列，不妨设子列 x 盯) 收敛于 j ，即l i r ax 盯= j e h ( 2 ) 口t 知孑= 0 ，再由定理2 1 可知j 为k 一丁点，又因为 厂( x ) 为凸函数，所以j 是问题( 号) 的最优解 令 x 9 ) 是 x 。) 的任意子列，且l i r a x o = 膏， 盯 则 f ( x ) = ! j i r a f ( x 4 ) = i i m f ( x 。) = l i r af ( x 新) = 厂( x ) ， 1 i - - o o 七- - o o 一 故贾也是问题( 异) 的最优解 2 1 2 实例分析 算例2 1m i n f ( x ) = ( 五- 2 ) 2 + - 2 x l x 2 + ； i 五+ 毪+ 屯= 4 ， 矗l t 2 而一屯+ x 3 2 解取x o = ( 0 ，l ，3 ) t ，由题得盯( x ) = ( 2 ( 五一2 ) 一2 而，2 而一2 五，2 x 3 ) t ， 1 2 线性等式约束非线性规划问题的w o l f e 改进算法 11 ) 虿 一虿l 11 i 虿虿j 迭代次数五屯毛夥( x ) i k d 五 1 o 13 。( - 6 ，2 ，6 ) t ( 2 ，3 ) ( 6 ，3 ，一9 ) t 7 1 5 2 2 82 4 1 2 ( 一3 2 ，一0 8 ，一2 4 ) t ( 2 ，3 ) ( o ，0 ，0 ) t 由上表可知，计算结果与精确解x = ( 警，孚，一詈) t 是完全一样的，从而说明将一 维搜索引入可行下降算法是有效的 2 2 二次规划问题 考虑二次规划问题 ( q p e ) m i n f ( x ) 2 扩叽水； 【s j a x = b 其中g = ( 岛) 舢是对称的，g ( 晶，g ：，g 。) t ，a = ( ) 。，b = ( 6 1 ，6 2 ，瓦) t ， ( 聊 n ) ，设秩a = m ，假定a 中有一个m 阶非奇异子块 。 b = 口1 n 1 如 a z 4 口2 f 2 口口啦 扎： a 。 口l 口l 五 a 2 a 口2 口嘲口嘞 ( 其中m + p = 疗，且变量下标不一定连续) 下面我们来确定问题( q p e ) 的一个可行下降方向 q 厶 口2 厶 口毗 设x 是问题( 妒e ) 的可行解，由上面假设，可以分解a = ( b ，) ，x t = ( e ， 碟) ，其中b 是朋肋可逆矩阵若非零向量d 满足a d = 0 ，则由定义1 3 可知d 是( q p e ) 的可行方向若同时还满足v f ( x ) t d 0 ，则由定理1 7 可知d 就是 ( q p e ) 在点石处的可行下降方向 1 l b 得， r 、l碜 1 j z ，l v防慷 = 塞 肚 燃 ， 下 n v 得 可 1 1 = 2 口 法 驳 算 可 由 j r l 则 故 硕十学位论文 与么的分解相对应，分解d t = ( 刃，簖) ，由a d = o 得b g + 嗽= o ，即 d b = - b n d ， ( 2 8 ) 又由制= b ， b x s + m = 6 ，即= b b - b 。1 托k ，于是目标函数为， f ( x ) = 厂( ，扎) = f ( b _ b - b 1 呱，扎) ， 2 9 ) 设其梯度为厂， = v ( x ) 一( ) t v 矗厂( x ) = 四z + 乳- ( b 一1 忉t ( 口z + 踟) ，( 至1 0 ) 肌v c 耻( 掣，眢，掣 1 ， i 缎；g ；j 吖卜l 眢，哿，掣j ， i 戚，出；幽：j 令，t = ( 右，砖) = 町( x ) t - v b ( x ) t ( b - 1 彳) = ( o ，v 厂( x ) t v 口厂( x ) t ( b 一1 ) ) = ( o ，( g t x + g ，) t 一( 罐x + g 占) t ( b - 1 ) ) ， ( 2 1 1 ) 由( 2 8 ) 和( 2 11 ) 式得， 町( x ) t d = v b 厂( x ) t d b + v 厂( x ) t d ，= ( v v 厂( x ) t v 且厂( x ) t b n ) d ， = ( ( 哦x + g ) t - ( g x + g 口) t b n ) d = 砖“， ( 2 1 2 ) 为使d 是可行下降方向，只要选“使砖乩 0 即可因此可按下述规则来确定d ， 0 一乃：- 。l 儿，j 口 ( 2 1 3 ) d b = 一b h n d n j 一 又因为巧d ：兰，：d j ：一( j r 哆) o ，由( 2 1 2 ) 可知当九o 时，w ( x ) t d 0 ，令k = 0 s t e p 2 ：分解a = ( b ，) ，其中b 是a 中的一个研阶非奇异矩阵，且用表 1 4 线性等式约束非线性规划问题的w o l f e 改进算法 t - 一- j kb 在彳中列号组成的集合，即厶= f l ，f 2 ，0 ) ；用i t 表示 n 在彳中列号组成的 集合，即= z ，左，厶) ；且tu = 1 ，2 ，刀) s t e p 3 计算口= w ( x 。) t - v 占f ( x 。) t b a s t e 昨划= 鼢肌 办鬟三东群 s t e p 5 ：判别忙1 1 - 0 ； ( 2 ) 若p ( 丑) l o ，停止，无解；否则转( 4 ) ； “) 令丑+ - = 乃一罟，若l + 。一名l 0 ，使得x + 2 d 对每个兄 0 ，万】和每个七k 是可行的所以定理1 6 的条件3 也成立，证毕 2 2 2 实例分析 算例2 2m i n f ( x ) = _ 2 + 2 + - 2 x l x 2 + 毛； 1 6 线性等式约束非线性规划问题的w o l f e 改进算法 5 f j ，+ 五+ 毛2 4 ( m 0 解原问题可转化为 m i n f ( x ) = ( 五- 2 ) 2 + ( t - 1 ) 2 + o x 3 + o _ ； 她j + 恐- 2 + # - i - 0 【彳一恐+ = 0 取s = 0 0 0 1 ，由算法4 1 可得下列迭代表格： 2 1 硕士学位论文 迭代次数 而而 毛矗 022 oo 1 1 2o 8o o 2 1 0 1 1 7 6 4 70 9 8 8 2 3 5 200 31 0 0 0 0 4 5 80 9 9 9 9 5 4 2 00 从上表可知，在经过3 次迭代之后，计算结果与最优解x = ( 1 ，1 ) t ，最优值 f ( x ) = 1 已非常接近。 小结：从以上实例可以看出，把松弛变量引人不等式约束的方法是可行的， 计算结果也是令人满意的 线性等式约束非线性规划问题的w o l f e 改进算法 3 线性约束非线性多目标规划问题的改进算法 本章用线性加权法先将多目标问题转化为单目标规划问题，再结合前一章的 方法进行求解文中对各个算法进行了实例分析，结果表明，将可行方向法运用 在多目标规划问题中是很有效的 3 1 线性等式约束多目标规划问题 考虑问题 ( 即) m i n f ( x ) = ( z ( x ) ，厶( x ) ，厶( x ) ) t ； s t a x = b 其中f ：r ”一r p 为二阶连续可微函数 针对此多目标规划问题，使用线性加权法求解，首先将其转化为单目标规划 问题，当目标函数为二次函数或为二阶连续可微函数时，则可用算法2 1 进行求 解具体而言，有下列改进的算法5 1 ： s t e p l ：构造线性加权目标函数办( f ) = 五石，a = ( ，丑，乃) t + 或 ”， f = i i d。 其中 + = 五= ( 五，砟) t1 2 o ，且五= 1 ) ； ”= 名= ( a ，以) tk o ，且五 i i 2 1 ”1 = 1 ) ，五的值可由常规方法( 口一法或兄一法) 确定 s t e p 2 ：用算法2 1 求解单目标规划问题 口 ( 丑m i nh ( f ( x ) ) = 锚( x ) ； i = l s 1 a x = b 3 1 1 最优解与( v p ) 解之间的关系 引理3 1 ( 1 ) 设石 + ，若牙是( 相应万的最优解，则牙是( 阡) 的弱 有效解；( 2 ) 设( 即) 是凸多目标规划，若牙是( 阡) 的弱有效解，则存在万a + ， 使牙是( 铲) 。相应万的最优解 硕士学位论文 由以上引理可知