（运筹学与控制论专业论文）求解等式约束优化问题的基于拟牛顿校正的既约hessian+sqp方法.pdf

求解等式约束优化问题的基于拟牛顿校正的既约h e s s i a ns q p 方法 摘要 本文研究用既约h e s s i 钮s q p 方法求解等式约束问题与一般s q p 方法相 比，既约h e 蹈i a ns q p 方法能节省大量的存储空间因此，这类方法能有效地求解 较大规模的等式约束问题然而已有的这类方法的全局收敛性分析需请求较强的 条件，如假定l a g r 觚g e 函数的既约h 稻s i a n 矩阵序列的一致正定性，而这种假定 通常很难被满足因此，在没有上述假定的情况下研究用既约h e s s i a n 方法求解约 束问题具有重要的理论与实际意义 本文提出了既约h e 鹃i 衄s q p 方法的两种修正在第一章中，我们介绍了非 线性规划的基本理论，包括b f g s 校正技术，然后给出了既约h e s s i a ns q p 方法 的基本结构在第二章我们首先推广了求解无约束问题的m b f g s 校正技术，并 将其应用到求解等式约束优化问题中，提出了一个修正的既约h e 鹪i 锄s q p 方法， 并且在较弱的条件下建立了全局收敛性结果分析表明该方法同时具有局部r - 线 性收敛性和2 步超线性收敛速度我们在第三章研究了结合m b f g s 与c b f g s 两 种方法的修正既约h e 鼹i a ns q p 方法，提出带混合校正技术的既约h e 船i a ns q p 方法，这种方法与第二章的方法具有相同的收敛性及优点在第四章我们针对第 二章，第三章所提出的算法进行了数值实验，数值结果表明本文所提出的算法是有 效的数值实验结果的比较表明第三章中的算法在各个方面均比第二章中的算法 要更为有效 关键词：等式约束问题；既约h e s s i a ns q p 方法；b f g s 校正；全局收敛性；局 部r - 线性收敛性 硕士学位论文 a b s t r a c t i nt k st h e 8 i 8 ，w ea r ec o n c e m e dw i t he q u a u t yc o n s t r a i n e do p t i 皿z a t i o np r o b l e m s i ti sw e u - k n 0 1 w nt h a tt l es e q l l e n t i a lq u a 山a t i cp r o g r 锄血n g ( s q p ) m e t h o d s a r ew e l c o m ef o r8 m a ua n dm i d d l es i z ep r o b l e m f b rl 盯g es c a l ep r o b l e m ，h o e v e r ，s q pm e t h o dm a yn o te 伍c i e n t 鹊e v e nn o to ”ra u t h er e d u c e dh e s s i a n s q pm e t h d dc a nb e 印p l i e dt os o l v el a r g es c a l ep r o b l e md u et oi t sr e q u i r e m e n t o fl i 嘟s p a c ef o rs t o r a g e e ) d s t i n gr e d u c e dh e 鹃i a ns q pm e t h o 凼a r ep r a c t i c a u y e 伍c i e n t h 删r ，t h ec o n d i t i o i l sf o rar e d u c e d h e 豁i a ns q pm e t h o d 缸er i 9 0 r o 璐 i ng e n e r a lt h eu i l i f o r mp o s i t i v ed e f i n i t i o no ft h er e d u c e dh e 船i a n 印p r 0 晒m a t ei s n l 戈豁s 舭孓 i nt 地t h e s i s ，b 粕i n go na nm b f g su p d a t ef o ru n c o 璐t r a i n e do p t 妇i z a t i o n ， w ep r o p 0 8 eaw a yt oc o n s t r u c tq u 够i n 哪吨o nu p d a 七ef b rt h er e d u c e dh e 蹈i a na 】p p r o 姬m a 土i n g i nc h 印t e ro n e ，w ei n t r o d u c es o m ew e ul 【n o w ni t e r a t i 0 i nm e t h o i s i 1 1 c l u d m gb f g s m e t h o d w bt h e ni n t r o d u c et h eb a s i ss t e p so ft h er e d u c e d h e 豁i a n s q pm e t h o d i nc h a p t e rt w o ，w e6 r s t 砒r o d u c et h em b f g sf 0 砌l l l aa n dt h e n 印p l yi tt ot h ee q u a l i t yc o n s t r a i l l e dp r o b l e 略u n d e rm i l dc o n d i t i o 璐，w ep r 0 、，et h e 酉o b a l 舢r g e n c eo ft h er e l a t e dr e d u c e dh e 鼹i a ns q pm e t h o d w ba l s oo b t a i n t h e1 0 l i n e a ra n dt w os t e ps u p e rl i n e a rc o n v e r g e n c eo ft h ep r o p o s e dm e t h o d i n c h a p t e rt l l r e e ，b yc 0 皿【b i n i n gt h em b f g sa n dc b f g su p d a t ef 0 】姐u l a ，w ep r 伊 p 0 8 ea n o t h e ru p d a t ef o m m af o rt h er e d u c e dh e s s i a n 印p r o 函m a t i o n t h er e l a t e m e t h o dr e t a i 璐t h es a m ec 0 n v e r 群i n c ep r o p e r t y 鹤t h em e t h o di nc h a p t e rt w o w ba l s od os o m en u m e r i c a le x p e r i m e n t 8 i nc h a p t e rf b u r ，t h er e s m t ss l l o wt h e e m c i e n c y0 ft h ep r o p o s e dm e t h o d s k e yw r o r d s ：e q u a l i t yc o n s t r a i l 趟p r o b l e m ；r e d u c e dh 嘲i a ns q pm e t h o d ； b f g su p d a t e ；g l o b 以c o n v e r g e n c e ；1 0 c 甜r - l i n e 盯c o l l v e r g e n c e 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本入在导师酶指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法 律后果由本人承担。 作者签名：磐查 日期：如口孑年r 月f 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保露、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编 本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密瓯 ( 请在以上相应方框内打“”) 日期：如口p 年月谚日 日期：撕扩年，月谚日 豇 色陶 船别 名名签签者师作导 硕士学位论文 第1 章绪论 1 1拟牛顿法的理论与基本结构 无约束最优化问题的数学模型如下： 血n ，( z ) ，z 尺n( 1 1 ) 其中，：j p r 1 称为目标函数，是一个连续可微的函数我们用v ，0 ) 和v 2 ， ) 分 别表示，在z 处的梯度和h e 鹃i a n 阵 定义1 1 如果存在e o ，使得对所有满足忙一矿0 ，( 矿) ，则称矿为( 1 1 ) 的严格局部最优解 定义1 2 如果对所有z 舻，有，( z ) ，( 矿) ，则称矿为( 1 1 ) 的总体最优解如果 对所有z j p ，有，( z ) ，( 矿) ，则称矿为( 1 1 ) 的严格总体最优解 判断矿舻是否是( 1 1 ) 的最优解的条件有如下三种形式： 一阶必要条件：设函数，：j p _ r 连续可微，若z 是问题( 1 1 ) 的一个局部最 优解，则成立 v ，( 矿) = o 我们称满足上式的点矿为函数，的稳定点 二阶必要条件：设函数，：册_ r 二次连续可微，矿是问题( 1 1 ) 的一个局部 最优解，则成立 v ，( z ) = o ，1 且v 2 ，扛+ ) 半正定 二阶充分条件：设函数，：酽一r 二次连续可微，则矿是问题( 1 1 ) 的严格局 部最优解的充分条件是 v ，( z + ) = o ， 且对v 0 t l 舻，有 t 上t v 2 ，( 矿) o 在求解此类无约束最优化问题时，通常所采用的方法多为迭代算法，迭代格式 一般为： z 七+ l2z 詹+ a 七政， 其中巩为搜索方向一般地，以需要满足v ，( 孤) t 以 0 是由某种线性搜索得到的步长 一1 一 求解等式约束优化问题的基于拟牛顿校正的既约h e s s i a ns q p 方法 该迭代法称为下降算法，最近几十年以来关于下降算法的研究在众多学者的 努力下得到了飞速的发展到目前为止我们所常用的算法主要有以下几种，这些算 法各自都有自己的特点，不可避免的，这些算法也在某些方面或多或少存在着某些 缺点 ( 1 ) 最速下降算法在这个算法中，取步长也= 一v ，( z 七) 该算法的优点是计算 简便，并且存储信息所需要的空间比较小，可以用于较大规模最优化问题的求 解但是该算法也有比较明显的缺点，就是仅有线性收敛速度，就是说该算法 的收敛速度太慢 ( 2 ) 牛顿法在这个算法中，取步长比= 一z 如v ，( 巩) 其中巩是v 2 ，0 七) - 1 的近 似，v 2 ，( 孤) 表示，在处的h e 船i a n 矩阵该算法的优点是收敛速度快，可以 达到二阶收敛速度，缺点是每次迭代都需要计算目标函数的h e 幽a n 矩阵，计 算量很大 ( 3 ) 拟牛顿法在这个算法中，取步长以= 一风：v ，( 钆) 拟牛顿法的优点是其具 有超线性收敛速度，并且在大多数情况下，拟牛顿法可以产生下降方向但是 拟牛顿法在迭代过程中需要储存一个一般是稠密的矩阵，因此该法不是很适 合较大规模稀疏问题的求解 ( 4 ) 共轭梯度法在这个算法中，取 d 知= 二号； 三：；+ 口七以一，：三三： 不同的共轭梯度法，参数口七的选取也是不同的该法的优点在于克服了最速下 降算法收敛速度慢的缺点，同时又能够避免存储和计算牛顿法所需的二阶导 数信息所以对较大规模优化问题来说，该算法也是一种比较好的选择 ( 5 ) 超记忆梯度法在这个算法中，取 l v ，( 钆) ， 七 o 使得 ，( z 七+ a 七d 七) ，( z 七) + p 1 q 七v ，( z 七) t d 七 ( 1 4 ) 利用函数妒 ) = ，( 孤+ q 血) ，上式可等价地写为： 垆( q 七) 妒( o ) + n q 七( o ) ( i i ) w b 舀p o w e u 型线性搜索给定常数p 1 ，晚满足o p l ；，n 0 ，则矩阵风+ l 也是正定的 。 求解( 1 1 ) 的b f g s 算法如下： 步0 ：取初始点z o 舻，初始对称正定矩阵玩舻黼取e 0 ，令七= 0 步1 ：若i j v ，( 瓢) 0 e ，则算法终止，得问题的解孤，否则，转步2 步2 ：解线性方程组 v ，( z 七) + 鼠d ；o 得解以转步3 步3 ：由某线性搜索方法确定步长q 七 步4 ：令 z 七+ 12z 七+ q 七以 如果 i i v ，( ) l i e ， 则z 七+ 1 即为所求解否则，由拟牛顿修正公式( 1 8 ) 计算得出凤+ 1 一4 一 硕士学位论文 步5 ：令后= 七+ 1 ，转步1 若将本算法中的风的修正公式换成其它公式，则可得到相应的拟牛顿法的计 算步骤 众所周知，如果风正定，则毗是，在z 七处的一个下降方向步长a 七的计算过程 中所使用的线性搜索包括精确线性搜索，非精确w b 型线性搜索，如n l j j o 型线 性搜索以及满足g 0 l d s t 血条件的非精确搜索等等b f g s 方法中矩阵最+ l 显然 能够满足拟牛顿条件弧= 鼠+ 1 钆 1 2 既约h e s s i a ns q p 方法的理论与基本结构 在本论文中，我们研究用修正的既约h e 跚i 姐s q p 算法以解决如下的等式约 束优化问题： 竺留：。 q 聊 s t c ( z ) = 0 其中， c ( z ) = ( c l ( z ) ，c 垒( z ) ，( z ) ) t 问题( 1 9 ) 中的拉格朗日函数三：舻+ m r 定义为 l ( z ，入) = ，( z ) + 入t c ( z ) ， 这里向量a 被称为拉格朗日乘数 假设函数，：舻_ 脚c ：册_ 胛是二次连续可微的，问题( 1 9 ) 的解存在的 一阶必要条件是存在拉格朗日乘数”满足条件： v 霉l z 入+ 二：! 亍2 + a z a = 。 c 1 1 。， c ( 矿) = o ， 、 这里 9 ( z ) = v ，( z ) ， a ( z ) = v c ( z ) = ( v c l ( z ) ，v ( z ) ) t 满足( 1 1 0 ) 的点称为问题( 1 9 ) 的k k t 点，并且同时满足 矿v ：霉l ( z ，入) d o ，v d d 月，i a ( z ) t d = o ，d o ) ，( 1 1 1 ) 于是z 是问题( 1 9 ) 的严格局部最优解条件( 1 1 1 ) 被称为二阶充分条件 设z ) 是一个矩阵，它的列组成a ( z ) t 的零空间的正交基于是一阶必要条 件( 1 1 0 ) 可以被描述为 z ( z ) t 夕( z ) = o ，c ( z + ) = 0 ( 1 1 2 ) 求解等式约束优化问题的基于拟牛顿校正的既约h e s s i a ns q p 方法 并且二阶充分条件( 1 1 1 ) 可以被等价地描述为既约h e s s i a n 阵 z ( z ) t g ( z ，入+ ) z ( z + ) 是正定的，这里， g ( z ，a ) = v 乙l ( z ，a ) 从( 1 1 2 ) 我们看到，函数 i i z ( z ) t 夕( z ) 1 1 2 + i i c ( z ) 1 1 1 可以被看做在某种意义上估计点z 与k k t 点的距离的残函数 既约h e 鹃i 观s q p 算法的迭代过程如下： 令z 七为当前的迭代点，我们记a = a ( z 七) ，磊= z 七) ( 以后我们还会使用类 似的简记方法，如记仇= c ( 瓢) 等等) 下一个迭代点z 七+ 1 通过。七+ l = + q 七政得 到，这里步长q 七通过某种线性搜索规则来决定，可以使用某种效益函数，该效益 函数砂在点z 七+ l 的值小于妒( z ) 的值并且以是二次规划( q p ) 子问题 冀n 絮，臀擘玩珈 ( 1 1 3 ) s t a 和+ = o r 一7 的解，其中风是既约h e 韶i a n 阵刁g ( z 七，a 知) 磊的近似 结合b ”d 和n o c e d a l 【5 】以及a m i r i 【6 1 中的相关估计，我们有拉格朗日乘数在 点z 知的估计为： 入量= 一( a 看a 知) 一1 a 舌9 * ， ( 1 1 4 ) 步长出的计算可以通过分解巩来完成，即 噍= k + 讥， ( 1 1 5 ) 其中 h k = 一z k b 三1 况g k ， = 一a 七( a 玉乱) - 1 显然矩阵么j 似一m ) 满足 z k = o 。况z k = i ( 1 1 6 ) ( 1 1 7 ) ( 1 1 8 ) 明显，满足以上两种条件的矩阵反不是唯一的一个获得玩的有效方法是通过矩 阵a 的q r 分解： 忙c ，( 黔 一6 一 硕士学位论文 这里k 和玩的列正交，r 七是一个非奇异的m m 上三角矩阵 c o l e m 趾和c o 皿( 1 9 8 4 ) 【，】提出了一种既约h e 锵i a ns q p 方法，即用一系列 的正定矩阵去逼近( 矿，”) 处的既约h e 鹃i 龃矩阵，其中用到了约束函数的切空 间上的标准正交基磊，他证明了2 - 步超线性收敛性但是在他的算法中，不能保 证剪：船 o ，因此，不能保证玩对所有的k 均是正定的本文在c 0 l e m a n 和 c o 皿( 1 9 8 4 ) 【刁的基础上，利用l i f i l k u s h i m a 阁关于无约束问题修正b f g s 技巧， 结合l i u “p ，l u 】的相关结论，从而能够使风对所有的k 均正定 矩阵风在既约h 髑i a ns q p 方法中起着重要作用，它可以通过拟牛顿方法生 成在所有拟牛顿方法中，b f g s 方法是非常受欢迎的( 见文【1 1 ，1 2 】) ，b f g s 修正 形式前文已述( 1 8 ) 但是鲰有不同的形式，例如c 0 l e m 趾和c o 皿【上瑚采用 弧= 刃( v 七己( z 知+ q 七，k ，a 七) 一v 知l ( z 七，入七) ) b ”d 和n o c e d “1 4 】同样使用这种类型的玑玑的另一种不同的形式是： z 陪= 凌1 1 ( v 霉l ( z 七+ 1 ，入七+ 1 ) 一v z l ( z 七，a 知+ 1 ) ) 这种类型的玑首先由c a b a y 【l l 】提出而且被n o c e d a l 和o v e r t o n 【l 蠲使用，m u h a y 和w h g h t ，x i e 和b ”d 【均l 则利用另一种形式的玑： 3 睡= 兹( v 王工( z 七+ l ，儿) 一v 善l ( z 七，入七) ) 保持取正定是非常重要的，它使得( 1 1 3 ) 产生的方向d 是某个效益函数的下降 方向；另一方面，若矩阵风正定，则子问题( 1 1 3 ) 是一个严格凸二次规划问题此时， 该问题有唯一解，而且求解也相对容易因此，研究矩阵风的正定性是一项非常重 要的工作对于反正定的研究在最近很受重视( 见文【1 2 ，1 3 ，1 5 ，1 6 】) p a e u i “】提 出了一个修正的b f g s 公式，该公式可保证产生的矩阵是正定的数值计算结果 表明该修正公式的s q p 算法的数值效果较好，然而该算法的局部收敛性尚不清 楚众所周知，如果凤正定，并且鼠+ 1 是通过( 1 8 ) 的b f g s 修正形式所得到的，于 是当且仅当可蚕s 七 o 时，风+ l 是正定的当b f g s 方法被应用于解决约束性优化 问题时，条件靠s 七 o 可以使用w b l f 苔p o w e u 线性搜索技术来实现但对于约束问 题，通过线性搜索是不容易保持矽：s 七 o 的，我们希望通过修改这种修正规则来保 持取的正定性为了达到此目的，一种方法是使用精确的零空间信息，被称为零空 间分割修正策略；另一种方法是使用全步信息，被称为步分割修正策略对于这些 b f g s 修正策略，相关的既约h e 鹃i a ns q p 方法具有一些非常好的全局收敛特性 和一些快速的局部收敛特性这些方法的全局收敛性条件一般包括二阶充分条件 1 3问题研究背景及发展情况 最优化计算方法是数学学科中最近几十年一个十分活跃的领域，随着计算机 一7 一 求解等式约束优化问题的基于拟牛顿校正的既约h e s s i a ns q p 方法 不断的更新换代所带来的计算速度的飞速发展，最优化算法在经济，生产管理，交 逶，运输，物理帮通信等众多领域已经有7 广泛丽又深入的应焉。另外，在生产组 织以及资源分配等管理科学方面，最优化方法也已成为一种重要的辅助性决策手 段 在解约束优化阿遂斡方法中，s q p 算法是很受欢迎的一种算法。s q p 算法( 见 文f 7 ，1 8 2 2 】) 对于解决中小规模的优化问题是非常有效的，此类问题的核心工作 是在每次迭代求解一个二次规划( q p ) 子问题而这个q p 子问题的构造对s q p 算法的收敛性起着十分重要的作用我们知道，s q p 算法一般用来求解中夸规模 的优化问题，但是实际生活中的许多问题往往规模比较大，即所谓的较大规模问 题，它们往往所涉及的变量维数很高，通常上千维，有的甚至能够达到万维，百万 维一般来说，较大规模闯题，0 ) 祷二阶导数珏e 鹪i a n 阵v 2 ，( z ) 常常是对称正定的， 尤其具有某种稀疏的结构 在求解较大规模问题时，我们希望能够得到收敛速度快，计算量少并且存储量 小的算法而需求解中小型最优化问题的传统算法来求解较大规模潞题时，许多的 优点已经变得不是很重要，比如数值效果较好的b f g s 算法，虽然校正矩阵最l 能 够继承正定性和对称性，却不能继承稀疏性，这极大地制约了s q p 算法的在现实 中的应用因此，研究如何求解较大规模闯题具有非常重要的现实意义 s q p 算法最早由w 涵。珏王9 6 3 ) 提出，w i 硒鼗提出了拟牛甥艮s q p 算法。年 代末和7 0 年代初，随着解无约束优化问题的拟牛顿方法的发展，拟牛顿s q p 算 法的研究弓l 起了学者们的高度重视p o l o m a r 静m a n g 勰谢a n ( 1 9 7 6 ) 提出了一个类 拟牛顿s q p 方法。在该类方法中，他采用对l 8 舒趾黔函数的整体h e 豁i 溅矩 阵( 即既对x 又对l a g r a n g e 乘予的h e 鹳i a n 矩阵) 的近似进行修正的方法来修正 h a n ( 1 9 7 6 ，1 9 7 7 ) i z 胡证明了p s & s q p 和b 粥孓s q p 方法的局部收敛性而且，若 采用精确罚丞数进行搜索，则算法具有全局收敛性。自诧，s q p 算法的研究受到广 泛重视、 b f g s 方法具有较好的数值效果和快速的收敛性，并且已有比较完善的局部 收敛理论( 见文【1 9 ，麓，2 翻) ，对全局收敛性的研究也取得了比较重要的成果。特剐 是对于凸函数的极小化问题，若采用精确线性搜索或某些特殊的非精确线性搜索， 则b f g s 方法其有全局收敛性( 见文f 1 4 ，8 ，2 6 ，2 7 1 ) 但是对于非凸函数的最优 化遍逐，即使采惩精确搜索，标准的方法也不具有全局收敛性，为了克服b f g s 方 法的这种缺陷，文献f 2 4 】介绍了b f g s 的修正形式m b f g s ( m o d i 矗e db f g s ) 算法， 文献f 8 】介绍了保守b f l g s 修正c b f g s ( c a u t i o nb f g s ) 算法 许多优化研究工作者在研究b f g s 方法在求勰无约束非凸阕题时鲶全局收敛 性问题已取得了不少的成果。l i f 蚀u 8 l l i m a f 8 ，2 5 1 ，p a e u 【2 9 ，3 0 】，矾l a n f 3 1 1 ，d a i f 3 2 l ， m a 8 c a r e n h a s 醐，w r e i ，卜y u a n 【4 】等等都阐述了自己的研究方法 一8 一 硕士学位论文 由已有的关于b f g s 方法的研究成果可知，为确保b f g s 算法的全局收敛性， b f g s 方法通常需要作某些方面的一定的修正本文将进一步研究在保持b f g s 方法仿射不变性的前提下b f g s 方法的修正形式 b f g s 方法的核心内容是b f g s 校正公式，利用这一公式产生h e 鹃i a n 矩阵 的近似，避免了直接计算h e s s i a n 矩阵因此，这一校正公式现在已被广泛使用 在其它优化方法中，例如，它已经被用在求解非线性方程组( 见文【3 5 】) ，约束优化问 题( 见文【1 4 ，3 6 】) ，半无限规划问题( 见文【3 7 1 ) 以及随机规划问题( 见文【3 8 】) 等的数 值方法中 最近几十年，对于使用s q p 算法解决较大规模的优化问题的发展已受到越来 越多的关注在这些方法中，既约h e 鹤i 趾s q p 算法已经受到高度重视( 见文【3 9 ， 4 0 ，4 1 1 ) 与一般的s q p 算法相比，既约h e 鹤缸s q p 算法的一个显著优点就是 在算法执行过程的拟牛顿矩阵需要更少的存储空间，而存储空间的节约对于求解 较大规模问题尤其重要文献【1 8 】利用拟牛顿校正技术提出了求解无约束优化问 题的既约h e 豁i a n 拟牛顿方法，但更多的研究工作者侧重于研究利用既约h e 髑i 锄 方法来求解约束问题( 见文【7 ，1 4 ，1 9 ，2 0 ，4 2 】) 在既约h e 蹈i a n 方法中，每次迭代 需构造一个q p 子问题，它的目标函数的h e 踌i 缸矩阵拟牛顿矩阵通常是拉格朗 日函数的既约h 嘲i 缸矩阵的近似 迄今，s q p 算法的研究工作已取得了丰硕成果国内外对既约h e 硝i 眦s q p 方 法中的b f g s 修正已经做过很多不同的研究，n o c e d a l l 和c 帆疵o n ( 1 9 8 5 ) 【“】提出 了单边及双边的投影h e 鹦i 姐方法在单边的投影h 嘲i 趾方法中证明了局部1 步 超线性收敛性，而在双边投影h e 蹈i 柚s q p 方法中证明了在某种假设条件下的2 - 步超线性收敛性但他的b f g s 修正公式必须是在满足一定的修正准则的情况下 才进行修正r f 0 n t e c i u a ( 1 9 8 8 ) 【4 跏提出了一种2 步线性收敛算法与c o l e m 缸和 c o n n 不同之处在于他将步长分为水平方向的步长和垂直方向的步长两个互相垂 直的向量，且仅利用水平方向的步长对风进行修正在对步长进行分解时他使用 了一个正交投影算子而不是标准正交基，比较容易满足连续性条件，比前者适用 的范围更广而且，他把这一方法推广用在了几种不同的乘子修正公式中在二 阶充分条件下，证明了该算法是2 - 步超线性收敛的，若在每一次迭代过程中再计算 一次约束函数的值，则算法为1 步超线性收敛的，但该文并没有全局收敛性研究 ) ( i e 和b y r d ( 1 9 9 9 ) 【1 5 】在既约h e 鹃i a ns q p 方法的基础上加上线性搜索得到全局 收敛性算法同时他把n o c e d a l l 和o v e r t o n 的修正法则改为一种新的修正法则正 曲率法则，这样能够得到更好的数值结果，他还证明了当利用两个常用的效益函数 f l e t h e r 效益函数和精确罚函数进行线性搜索时的收敛性，但是他抛弃了修正准则， 采用修正b f g s 修正公式进行修正 正如我们所说，一般的s q p 算法对于解决较大规模的优化问题并不是非常有 一9 一 求解等式约束优化问题的基于拟牛顿校正的既约h e s s i a ns q p 方法 效的，此论文的目的是通过在既约h e 鸽i a ns q p 方法中对b f g s 公式进行修正， 使得它对于解决较大规模优化问题是实际有效的 本文在某种程度上类似于r f 0 n t e c i u a 的算法，首先在对风进行修正时，结 合m b f g s 的修正式，我们得到本文的第一种算法其次结合m b f g s 与c b f g s 的修正式，我们得到本文的第二种算法并且，利用z 。精确罚函数进行线性搜索，在 较弱的假设条件下，我们建立了它们的收敛性理论 1 4本文主要结构 在第一章里，我们介绍了文章所研究问题的背景和发展情况以及本文所需要 的一些基本知识，大概说明了本文的研究方法 第二章和第三章我们分别详细介绍了基于修正b f g s 公式的既约h e 鹤i a n s q p 方法和基于m b f g s 和c b f g s 的既约h e s s i a ns q p 方法，并且分别给出了 与之相应的算法在没有假定f 二阶连续和对应的l a g r a n g e 函数的既约h e 鹃i a n 阵一致正定的情况下我们证明了该算法的收敛性和局部r - 线性收敛性 第四章是我们选用文献 4 5 】中的数值函数对本文重点分析的两种算法的数值 实验结果，同时我们把本文的算法的数值结果与具有通常的b f g s 校正的既约 h e 硝i a ns q p 算法的数值结果做了对比分析 一1 0 硕士学位论文 第2 章基于修正b f g s 公式的既约h e s s i a n s q p 方法 2 1引言 在前文所述的既约h e 鹃i 衄s q p 方法中，若二阶充分条件成立，则既约h e s - s i 缸阵对称正定做为其近似，取也应该保持对称正定此外，若风正定，则子问 题是一个凸二次规划问题，其解与它的k k t 点重合因而，对该问题的求解相对 容易本节，我们在求解无约束优化问题的b f g s 法的基础上，研究保证风对称 正定的修正公式并建立相应的既约h e 豁i a n 阵算法的收敛性性质 求解无约束问题 m i n ，( z ) ，z j 护 的b f g s 修正公式如下： 氟- = 瞰一鬻+ 篆， ( 2 1 ) s ：_ ，k s 士5 ： 其中， 乳5 孤+ l z 知， 3 睡= v ，( z 七+ 1 ) 一v ，( z 七) 该修正公式的一个重要性质是若凤对称正定且雍s 知 o ，则玩+ l 对称正定使 得可：s 七 o 成立的一个充分条件是f 是一致凸函数此外，若采用w o 型线性搜 索，也可保证靠s 七 o 然而，对于约束问题，如何保证y 舌s 七 o 目前尚无有关结 论另一方面，l i - f 、i l k u s b 蛔a 【溯最近对b f g s 公式进行了修正，对无约束问题，该 修正公式可以保证耖如七 o ，而且，此性质与f 的凸性以及所使用的线性搜索无关 l i - f u k u s l l i m a 【6 】对玑的取法是： 弧= 以+ 仇l l v ，( z 七) i i s 七，【0 ，q ， 其中， 以= v ，( z 七+ 1 ) 一v ，( z 知) ， 栌1 + 麟 一器 0 州v 弛圳l - 1 易知，上面的修正公式满足 瘊s 七l i s 七1 1 2 o 因此，只要风正定，则鼠+ z 正定该性质同样与f 的凸性及线性搜索无关 一1 1 求解等式约束优化问题的基于拟牛顿校正的既约h e s s i a ns q p 方法 2 2基于m b f g s 的修正的既约h e s s i a ns q p 方法 我们将上述思想应用于求解等式约束问题( 1 9 ) 的既约h e s s i 蛆b f g s 方法中， 使矩阵风对所有的k 保持对称正定性。 我们定义 其中， s 七= z 吾( z 七+ 1 一z 七) ， 晚= z 吾( v 卫z ( z 七+ q 七 七，a 七+ 1 ) 一可乙z ( z 七，a 七+ 1 ) ) ， ( 2 2 ) 弧= 氏+ 蚓i 风l i s 七， 仁1 一 稚，。批| l ， 玩= ( 黧) ( 2 3 ) ( 2 4 ) 不难得出， 鼎= 赫溉訾“2 警s p o 仁5 ， 即若s 七0 且凰0 ，则 可看s 七i i 凰m 1 2 o ( 2 6 ) 如果风对称正定并且上k 0 ，则由( 1 8 ) 所迭代产生的风+ 1 也是对称正定的；当上k = 0 时，即当等式 。 f i = o 成立时，瓢为k k t 点 需要特别说明的是，我们的风的取法与j i a n gl 幽中的取法有所不同，在 j i a n gl 【蛐中，取 而k = 日( z 七，入知+ 1 ) ， 这需要假设l a g r a n g e 函数的既约h e 豁i a n 阵的一致正定性才能有算法的收敛性， 而本文中我们的风的取法可以满足在不需要该假设的情况下就能够得到算法的收 敛性 接下来我们首先将求解无约束优化问题的m b f g s f 2 5 】方法应用于既约h e s - s i a ns q p 方法中，根据( 2 2 ) 所定义的飘，以，纨和( 2 3 ) ( 2 4 ) 所定义的如，风以及等 式( 1 8 ) 中的鼠的迭代方法，结合一般的既约h e 鹃i a n 修正b f g s 算法，同时选 一1 2 硕士学位论文 取常用的精确z 1 罚函数做为算法的效益函数，我们能够得出本文的第一种算法如 下我们称之为算法1 算法1 步0 ： 给出初始点z o ，初始l a g r a n g e 乘子知，初始对称正定矩阵岛，常数 0 ，0 0 ，叩( 0 ，1 ) 令七= 0 步1 ： 解二次规划子问题( 1 1 3 ) ，利用公式( 1 1 5 ) ，( 1 1 6 ) 和( 1 1 7 ) 得解靠，由( 1 1 4 ) 计 算得到相应的l a g r a n g e 乘子a 七+ 1 步2 ： 令九p ) = ，( z ) + t i i c ( z ) 1 1 1 罚因子u 七的值通过公式 t l 七+ t = i 气知+ ，l i + 2 6 ， 契焘u 七a 七+ l i i + 6 ； ( 2 7 ) 否则 、 来修正 步3 ： 令q 七是q 1 ，p 1 ，矿，) 中满足不等式 的最大值其中， 步4 ：令 九七( 钆+ q 以) 九七( 钆) + q 叩d 丸七 七，也)( 2 8 ) 丸( z ) = ，( z ) + 牡l ic ( z ) 0 - z 七+ l = z 七+ q 知d 七 ( 2 9 ) 步5 ：由b f g s 方法( 1 8 ) 得到风1 步6 ：令七= 南+ 1 ，转步1 注 ( 1 ) 上面我们已经讲到，以= + 玖是子问题( 1 1 3 ) 的唯一解，因此对于所有的k ， 风是正定的； ( 2 ) 在( 2 4 ) 中仇的取法与j i a n gl 【4 4 】有所不同在j i a n gl 【蛐中取 吼叫址- ，= r 黔。) ， 这种取法的一个缺点是在证明算法的收敛性的时候需要假设l a g r a n g e 函数 的既约h e 鼹i a n 阵是一致正定的，而如果按照算法1 的冠k 的取法，则不需要假 设l a g r a n g e 函数的既约h e 鹃i a n 阵是一致正定的就能证明这种性质，相对于 j i a n gl f 蛐来说，算法1 的适用性更为广泛 一1 3 一 求解等式约束优化问题的基于拟牛顿校正的既约h e s s i a ns q p 方法 ( 3 ) 在算法1 中，我们使用精确罚函数。作为效益函数，丸( z ) 是一个精确z - 罚函数 且是不可微的，但其方向导数存在，d 丸( z ；d ) 是九在点z 处沿方向d 的方向导 数函数九不是处处可微的但它是定向可微的九在点。处沿方向毗的方向导 数可以通过如下计算得出： 九七( z 七十q 毗) 一u 七( z 七) = ，( z 七+ 口以) 一，( z 七) + t 正七( 1 i c ( z 七+ 口d 詹) i i l i i z 七j | 1 ) = 碗毗+ 饥( i i + q 4 j i 以i i l i i “1 1 1 ) + d i l 呶i i ) = q ( 夕吾呶一t 川仇1 1 1 ) + o ( q l i 也i i ) 两边同时除以大于零的口，且两边取极限，当a 一0 时，我们得到 d 丸七( 孤，毗) = 靠以一心后1 1 1 1 1 ( 2 1 0 ) ( 4 ) 前面我们已经得到 9 吾魄= 入融，纸魄2k 银， 而且 d u 知( z 七，呶) = 靠 七+ a 虿c 七一t 七i i c 七1 1 1 ，( 2 1 1 ) 通过在算法1 的步骤2 中选择的u 七，我们有 d 九七( ，呶) 靠k 一( 仳七一l i 儿i i ) i i i i l ，一靠磊毋1 刀鲰一6 i i c 七| l 所以，当且仅当刀鲰= o ，= o 不同时成立时，d 丸七( ，噍) l l k l l ，那么当z 七不是问题( 1 9 ) 的k k t 点，并且反正定时，必 有d 札( z 七；毗) o 引理2 1 设瓢是由算法1 产生，且参数满足 “知i i 入七i i + p ，v ，( 2 1 3 ) 其中p 是一个常数则有 d 九七 七；以) 一0 刀鲰i 饥l ic o s 以一pi i 仇1 1 1 v 七，( 2 1 4 ) 1 4 硕士学位论文 且对于任意k 存在常数五( o ，l 】( q 与k 有关) ，使得 九( 锹+ 五也) “七( ) + 五，7 d q 七( z 七；也) ( 2 1 5 ) 证明： 我们首先证明( 2 1 4 ) 成立 由九。的定义有 d 丸七( 孤；畋) = 鳍巩一t 知1 1 1 1 1 由k ，垠的表达式( 1 1 6 ) 和( 1 1 7 ) 知 d 札七( z 七；d 七) 靠_ l 七一( u 七一| i a 七+ l i l 仪) i l c 七1 1 1 一靠磊巧1 刃鲰一p i i c k i i l = 一c o s 以i i 嚣1 刃鲰i i i | 刀鲰i i 一纠i 鲲1 1 1 由( 1 1 7 ) 知， l iki i 0 日蚕刀鲰i l ， 则( 2 1 4 ) 成立 所以，对 o ，使得对比d ， i la 0 ) 0 螈， 0a 扛) ( a ( z ) t a ( z ) ) 一10 朋_ a 一1 5 求解等式约束优化问题的基于拟牛顿校正的既约h e s s i a ns