非线性等式约束优化问题的一类既约Hessian算法研究_图文

1、首都师范大学硕士学位论文非线性等式约束优化问题的一类既约Hessian算法研究姓名：王玮申请学位级别：硕士专业：应用数学指导教师：陈兰平20070406摘要对于解决非线性约束最优化问题，罚函数法、可行方向法、逐步二次规触法（）和既约法是目前应用比较广泛的几种方法其中，逐步二次规划法已经成为求解中小规模非线性约束最优化问题的一类最重要的方法，而既约法以每次迭代计算量小且算法所需内存也小等优点更是得到了许多研究者的青睐既约法一般可分为双边既约法和单边既约法年。和首先提出双边既约的思想，后来一些学者对此进行了研究并提出一些算法这些算法一般都具有局部步卜超线性收敛速度年，和，提出单边既约法，并且证明了

2、此方法具有局部步超线性收敛速度本文结合单边既约法较快的收敛速度和双边既约法保持正定又较小的存储的优点。提出一种分别对单边既约的近似阵和双边既约的近似阵校正的既约算法，在一定条件下证明了算法具有局部步卜超线性收敛速度；进一步地，在新算法的基础上又提出一种具有全局收敛性的既约逐步二次规划法数值实验表明。本文提出的两种新算法是有效的整篇论文内容安排如下在第一章中，首先简要的介绍了最优化问题的提出以及判断最优解常用的最优性条件，回顾了非线性最优化问题常用的几类方法在第二章中，就非线性等式约束问题，提出一种既约校正算法，此算法分别对函数的单边既约的近似阵和双边既约的近似阵进行校正证明了若每次迭代至少有一

3、者被校正时，算法具有步一超线性收敛速度，并给出数值结果在第三章中，以第二章提出的算法为基础，构建一种解决非线性等式约束问题的既约方法为避免效应，此方法采用的光滑精确罚函数的逼近形式作为价值函数，在一定条件下证明了算法的全局收敛性并且给出数值结果关键词：约束最优化，既约，拟牛顿方法，逐步二次规划，局部超线性收敛，全局收敛性，（出，髓，：，首都师范大学学位论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰写过的作品成果对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明本人完

4、全意识到本声明的法律结果由本人承担学位论文作者签名卫弗日期，御年月日首都师范大学学位论文授权使用声明本人完全了解首都师范大学有关保留，使用学位论文的规定，学校有权保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版有权将学位论文用于菲赢利目的的少量复制并允许论文进入学校图书馆被查阅，有权将学位论文的内容编入有关数据库进行检索有权将学位论文的标题和摘要汇编出版保密的学位论文在解密后适用本规定学位论文作者签名。豆移日期；唧年，月日非线性优化问题简介这一章里，将简要介绍非线性最优化问题的发展现状第一节。简要地阐述最优化问题的提出以及判断最优解常用的最优性条件；第二节。总结了非线性最优化问

5、题几类常用的方法，重点是约束优化的几类方法；在最后一节，明确提出构建薪算法的动机和技术手段最优化问题的提出及最优性条件最优化理论与方法是一门应用性很强的年轻学科虽然最优化可以追溯到十分古老的极值问题，但直到年提出一般线性规划问题的单纯形法之后。它才成为独立的学科，随着现代科技的发展和计算机的广泛应用，进一步推动了最优化理论和算法的研究今天，最优化理论与方法在经济规划，政府决策，生产管理、交通运输和军事国防等方面都得到了广泛的应用，已经成为一门十分活跃的学科一般来说，最优化问题可归结为求解如下的极小值问题卿）其中，。是决策变量，（）为目标函数。彤为可行域根据变量的类型，最优化问题可分为连续型最优

6、化和离散型最优化（也称组合优化）连续型最优化问题又可分为目标函数和约束函数均为线性时的线性规划问题，以及目标函数和约束函数中至少有个为非线性时的非线性优化问题本论文研究方向是非线性优化问题非线性优化问题通常有如下形式：砌。）（）（），一，。；（）（）（），。，；冗）及（），）都是定义在形上的函数，其中至少一个为非线性函数满足（）一（）的点称为可行点。所有可行点所组成的集合被称为可行域，记为，显然（），。；：功，）（）当时，问题（）一（）是无约束优化问题，否则，是约束优化问题在约束优化问题中。如果只有等式约束，即。，则称为等式约束问题另一种特殊情形是所有的约束函数都是线性函数，这时我们称问题（，

7、）一（）是个线性约束优化问题下面我们给出非线性优化问题的全局最优解和局部最优解的定义定义设矿，如果，（），（），成立，则称矿是问题（）一（）的全局极小点，如果对一切且矿有，（）（）成立，则称矿是全局严格极小点定义设矿，如果对某一有，（），（），（，）（）成立，则称矿是问题（）一（）的局部极小点，其中（，）是以矿为中心以为半径的广义球（。，）霉一）如果对一切（矿，）且矿不等式（）成立，则称矿是局部严格极小点若记（）（）表示，（）的梯度，（￥），（）表示，（）的矩阵对于无约束问题，有以下最优化条件定理【（无约束优化必要条件）若矿为问题（）的一个局部极小点，（）在矿处可微，则必有（矿）如果，（）在矿

8、处二次可微，则必有（，），（矿）（）（）满足（）的点称为函数，（）的稳定点从上述可知，只要目标函数可微，局部极小点必是稳定点定理】（无约束优化充分条件）假设，（功在矿处二次连续可微，如果矿是（）的稳定点且对任何非零向量妒有（），则矿是无约束问题（）的局部严格极小点现在我们考虑约束优化问题显然，可行域上的一个点是否为局部极小点取决于目标函数在这一点以及该点附近的可行点的值所以我们有必要给出可行方向的定义（）定义引入记号，。），），（）纠臼（），），对矿舻，我们称集合（），（）是在点的积极集合（或有效集合），（）（）是在点的积极约束（或有效约束），（）“簪（）是在点的非积极约束（或非有效约束）定义

9、设矿，舻，如果存在使得，【，司，则称是在矿处的可行方向（，）（）在矿处的所有可行方向的集合记为定义设矿，舻，如果（），（），（矿），（）（）则称是在矿处的线性化可行方向在矿处的所有线性化可行方向的集合记为（，）定义设，肝，如果存在序列血，）和以（，）使碍矿以，（）且有如一和如一，则称是在矿处的序列可行方向在矿处的所有序列可行方向的集合记为（，）引理如果所有的约束函数都在矿处可微，则有（，）（，）（。，）定理设矿是（）一（）的一个局部极小点，如果（，）（，）则存在越，）使得（）（矿），埘均，：岛（），定义如果矿且存在”（姆，螺）满足（）一（），则称矿是问题（）（）的点（简称点），称”是在处的乘子

10、假定我们已知问题（）（）在解处的积极约束（）我们只需求解如下的等式约束优化问题砌，）（），（）由（）可得，（）的函数，即（）（）（，）一（）他）一地（）（）其中（，。）妒，以及（）（），南（）定义设矿是（）一（）的点。”是一相应的乘子如果是在矿处的线性化可行方向且有智矿（矿），（矿），则称是在矿处的线性化零约束方向在矿处的所有线性化零约束方向的集合记为（矿，”）如果在矿处的乘子是唯一的，我们用（。）来表示（矿，”）定义设矿是（）一（）的点，是一相应的乘子如果存在序列以，）和缸（，）使得矿以，（）（）：（以），且有以一和以一，则称是在矿处的序列零约束方向在矿处的所有序列零约束方向的集合记为（矿，

11、”）下面给出约束问题的优化条件定理【】（约束优化一阶必要条件）设矿是问题（）。（）的一个局部极小点，如果（）“，（矿）线性无关，则必存在智“，）使得（）一（）成立定理【】（约束优化一阶充分条件）设矿如果，（功和岛（），）都在矿处可微且矿，（矿），（，），（）则矿是闻题（，）一（）的局部严格极小点定理【】（约束优化二阶必要条件）设矿是问题（）（）的个局部极小点，是相应的乘子，则必有吃（，），（，），（）其中（，）是由（）定义的函数定理【】（约束优化二阶充分条件）设矿是（）一（）的个点，”是相应的乘子如果乞（，），（，），（）则矿是局部严格极小点非线性优化问题的常用方法本文主要研究约束优化问题，由

12、于约束优化问题的解法很多基本思想来自无约束优化问题的解法，且约束优化问题往往可以转化为无约束优化问题的求解，所以有必要先介绍一些常见的无约束问题的解法和理论根据无约束优化问题的算法大致分为两类：其中之一，在计算过程中要用到目标函数的解析性质（包括一阶导数和二阶导数），一般称这些方法为解析法；另一类只用到目标函数值，不涉及目标函数导数的计算，通常成为直接方法首先我们简要介绍一下解析法它是求解无约束优化问题；。（）（）常用的一类算法，它的基本思想是对于当前的迭代点瓤，首先确定个搜索方向靠，使得目标函数（）的值沿该方向是下降的，然后确定沿靠方向行进的步长并得到下一个迭代点。“巩在这里，我们要确定的搜

13、索方向应满足，（。）以使（）在点沿血方向下降为了行文的方便，在介绍线搜索和解析法几类算法之前，约定记号如下，（），女（），（如），一女，女确定的过程就是线搜索，也称一维搜索精确线搜索就是在也方向上寻求。最优。的行进距离，使得（）乎（）（）（）精确线搜索往往计算量很大，特别是当迭代点远离最优解时，效率很低而且，很多最优化算法的收敛速度并不依赖于精确线搜索的过程，所以在实际应用中，一般不采用精确线搜索非精确线搜索不要求（）成立。而仅要求找到的能使目标函数在某种意义上达到令人满意的下降，可以大大节省计算量常用的非精确线搜索如线搜索和线搜索两种搜索的条件如下：线性搜索条件：触舨碱槭琏陬魏扛咖帆十槲如口

14、（，百），卢（盯，）（）线性搜索条件：线性搜索主要是找一个儿，使，（，），且满足如下不等式（）（）口姆（鲰）改口（，）（）下面我们介绍几种常用的解析法最速下降法人们在处理（）这类问题时，总希望从某一点出发，选择个目标函数值下降最快的方向，以利于尽快达到极小点正是基于这样的一种愿望，早在年法国著名数学家最早提出了最速下降法后来，等人作了进一步的研究该方法取也一（以），即每步都以负梯度方向作为搜索方向因为负梯度方向是目标函数值下降最快的方向，所以该方法称为最速下降法这种方法每次迭代的运算量不大。并且初始点不用很接近最优点矿，但最速下降方向反映了目标函数的一种局部性质从局部看，最速下降方向是函数值下

15、降最侠的方向。选择这样的方向进行搜索是有利的但从全局看，由于锯齿现象的影响，即使向着极小点移近不太大的距离，也要经历不小的弯路，因此使收敛速率大为减慢因此，总的来说，最速下降法并不是收敛最快的方法，它的收敛是比较慢的牛顿法牛顿法的基本思想是在每次迭代时，用适当的二次函数去近似目标函数，并用迭代点指向近似二次函数极小点的方向来构造搜索方向，然后精确地求出近似二次函数的极小点，以该极小点作为，的极小点的近似值最直接而自然的二次模型，显然就是，的展开式中直到二次项的部分取（）（），其中（），（），因为方向比源于牛顿方程（）（），故称为牛顿方向当初始点充分靠近最优点。时，该方法二阶收敛并且对二次凸函数

16、具有二次终止性，但是当初始点却远离矿时，牛顿法可能不收敛。甚至连下降性也保证不了其原因是，迭代点不一定是目标函数厂在牛顿方向以上的极小点为克服上述缺陷，往往要引进阻尼因子即步长，可以证明其在一定条件下是全局收敛的牛顿法需要计算目标函数的及其逆矩阵，存储量、计算量都很大，并且在迭代过程中，（）可能出现奇异，使迭代被迫中止共轭梯度法共轭梯度法最初由和于年为求解线性方程组而提出的后来，人们把这种方法用于求解无约束最优化问题，使之成为一种重要的最优化算法共扼梯度法取初始搜索方向一（。），以下各方向由第次迭代负梯度一（）与已得到的共轭方向一的线性组合来确定即以“，呶，。一。，主；其中风为标量，著名的公式

17、有酽。筹器高饵删一卜蹦，），茚器（钯枷觑¨），瞥（，），矽：些（戚一蝴，）等对正定二次函数来说，以上公式是等价的。但对于目标函数是二次函数的无约束优化问题，它们产生的搜索方向是不同的一般说来方法收敛性；较好，方法和方法具有好的数值表现，方法的收敛性和数值表现都比较理想由于共轭梯度法至少具有线性收敛速度，而且迭代公式比较简单，只用到目标函数及其梯度值，避免了二阶导数的计算。从而减少了计算量和存储量。因此它是一种比较有效的方法拟牛顿法拟牛顿法是近年发展起来的一种求解无约束优化问题的最有效的方法特别是对高维问题有着明显的优越性拟牛顿算法的基本思想是：用不包含二阶导数的矩阵近似牛顿法中的矩阵

18、的逆矩阵，由于构造近似矩阵的方法不同，因而出现不同的拟牛顿法但近似×阶对称正定矩阵（）必须满足拟牛顿方程：挑（）拟牛顿法的搜索方向为一（）（），在著名的族拟牛顿法中，的校正迭代公式为风一等警丝州概咖碡（）饥一畿纛饥一面试磊固旧】其中口【，】，当分别为，时，即为著名的公式和公式校正公式。圾一等警蓑校正公式。娜矾一警蓑（咖（）方法具有二次终止性，方法除了具有二次终止性之外。还具有超线性收敛性对于方法，由于线搜索的不精确和计算误差的积累可能导致某一次迭代中的风奇异；而方法对线搜索的精度要求不高，并且由它产生的风不易变为奇异矩阵因此，方法比方法有更好的数值稳定性，使它更具有实用性拟牛顿法有许

19、多优点，比如，迭代中仅需一阶导数不必计算矩阵，当正定时，算法产生的方向均为下降方向，并且这类算法具有二次终止性拟牛顿算法的缺点是所需存储量较大，对于大型问题，可能遇到存储方面的困难在有些无约束优化问题中，目标函数的解析式比较复杂或者难以用明显的解析式表示出来，因而其导数很难求出或者无法求出，这就要求我们给出一些只涉及目标函数值的计算而不涉及目标函数的导数的求解方法这类方法也就是直接法，接下来我们就介绍几种比较著名的直接方法交替方向法最早的也是最简单的直接方法是交替方向法比较著名的算法有模式搜索法和方法摸式搜索法是由和于年提出的因此也称为方法这种方法的基本思想从几何意义上讲。是寻找具有较小函数值

20、的。山谷”。力图使迭代产生的序列沿。山谷”走向逼近极小点算法从初始基点开始。包括两种类型的移动，这就是探测移动和模式移动探测移动依次沿个坐标轴进行，用以确定新的基点和有利于函数值下降的方向模式移动浩相邻两个基点连线方向进行，试图顺着。山谷”使函数值更快减小模式移动的方向可以看作最速下降方向的近似，因此模式搜索法也可以看作最速下降法的一种近似由此可见，这种方法的收敛速度是比较慢的但是由于编程比较简单，对变量不多的问题可以使用，而且的确是一种可靠的方法方法又称为转辅法。这种算法的每次迭代包括探测阶段和构造搜索方向两部分内容探测阶段中，从一点出发，依次沿，个单位正交方向进行探测移动，一轮探测之后。再

21、从第一个方向开始继续探测经过若干轮探测移动，完成个探测阶段然后构造一组新的单位正交方向，称之为转轴，在下一次迭代中，将沿这些方向进行探测方法最早在年由提出后来、和对此方法进行了改进和分别讨论了如何比较经济地诗算每次迭代中需要的个正交方向单纯形法这里要介绍的单纯形法是一种无约束最优化的直接方法，并不是线性规划的单纯形法此方法最早由、和于年提出，后来由和改进单纯形是指胛中的个点为顶点的凸包单纯形法的基本思想是：在每次迭代时利用已有的单纯形去寻我个函数值更小的点如果得到这样个更好的点。则用这个新点作为一个顶点构造新的单纯形否则。将已有单纯形缩小重复迭代方法方法的本质上是共轭方向法，它是在年提出的方法

22、把整个计算过程分为若干个阶段，每一个阶段（一轮迭代）由次一维搜索组成在算法的每一阶段中，先依次沿着已知的个方向搜索，得一个最好点，然后沿本阶段的初点与该最好点连线方向进行搜索，求得这一阶段的最好点再用最后的搜索方向取代前个方向之一，开始下一阶段的迭代后来，注意到他的方法可能选取到接近线性相关的搜索方向，特别是变量很多时更是如此，为此他提出一种改进的方法，解决了这一问题虽然改进的方法不再具有二次终止性，但是，它的计算效果仍然令人满意下面我们重点介绍几种约束优化问题的常用方法可行方向法可行方向法可看作无约束下降算法的自然推广，其典型策略是从可行点出发，沿着下降的可行方向进行搜索，求出使目标函数值下

23、降的新的可行点算法的主要步骤是选择搜索方向和确定沿此方向的步长。搜索方向的选择方式不同就形成了不同的可行方向法下面我们就来介绍一些可行方向法可行方向法通过线性规划来确定下降可行方向，收敛速度比较慢方法是年和提出的一种求解线性约束问题的算法，其基本思想是将目标函数作线性近似，通过求解线性规划求得可行下降方向，并沿该方向在可行域内作一维搜索这种方法又称为近似线性化法，但是在实际应用中。此方法常常不收敛于年提出一种投影梯度法，后来，和又将此法进行了改进的投影梯度法的基本思想是当迭代点在可行域内部时，取该点处的负梯度方向作为可行下降方向，当迭代点在可行域边界上时，取该点处负梯度方向在可行域边界上的投影

24、产生一个可行下降方向约梯度法年，将线性规划的单纯形法推广到具有非线性目标函数的问题，提出既和于年成功地把既约梯度法推广于求解带菲线性等式约束的情形，提出了著名的方法（，广义既约梯度法）数值实例表明，方法是目前求解约束非线性最优化问题的最有效的方法之一由于可行方向法是先沿一线性化可行方向找到个较好的点，然后将该点利用方法。可行化”得到一个较好的可行点，每次迭代都要经过若干次迭代，因此，可行方向法所需计算量还是相当大的罚函数法罚函数法的基本思想是，借助罚函数把约束问题转化为无约束问题，进而用无约束最优化方法来求解早期求解非线性规划问题（）一（）的方法都是罚函数法由于这些早期方法均是需要求解一串罚函

25、数极小的方法，故它们也被称为序列无约束极小（）方法，简称罚函数可分为外点罚函数法内点罚函数法和混合罚函数法如果罚函数的极小点和原问题（）一（）的解吻合时。我们称该罚函数为精确罚函数罚函数法简单实用，它直接利用无约束优化的算法来求解约束优化问题但是罚函数法一般要求罚因子趋于无穷或者需要求解非光滑优化。所以利用一般无约束优化算法时常有困难，另外罚函数法的收敛速度通常也是很慢的由于（）提出的一个求解线性规划的内点法实质上等价于一个罚函数法，人们开始重新重视罚函数法解约束规划的其他方法在判别迭代点好坏时都用到某一罚函数。所以对罚函数的研究对于求解约束规划问题有着重要的作用最早的罚函数由（）提出，它只是

26、对等式约束问题提出的利用罚函数求解约束优化问题往往需要很大的罚因子。从而使求解罚函数极小时可能出现数值困难如果利用精确罚函数或。精确罚函数，则一般经过有限次迭代后得到原问题的精确解，但美中不足的是。三精确罚函数或厶。精确罚函数的极小是一个非光滑优化问题内点罚函数仅适合于不等式约束问题，即的情形两个常见的内点罚函数是倒数罚函数和对数罚函数因为内点罚函数在可行域的边界上无界，如果给定初始点在可行域内部，则利用求罚函数极小所产生的点列全都是内点从几何上看，内点罚函数在可行域的边界形成一堵无穷高的。障碍墙。所以内点罚函数也常称为障碍罚函数早期罚函数法的缺点是需要罚因子趋于无穷大，才可使求罚函数极小和求

27、解原问题等价乘子罚函数利用近似乘子，从而不需要无穷大的罚因子著名的乘子罚函数法有增广函数罚函数法和光滑罚函数法增广函数罚函数法的一个美中不足是增广函数是一个一次连续可微的函数，所以在求解过程中可能有数值困难光滑罚函数在一定意义下等价描述了原约束优化问题，它在很多约束优化的计算方法中有着直接的应用一个很重要的例子是。它可以作为效益函数来判别算法给出的试探点是否可被接受逐步二次规划法逐步二次规划法（）是解决非线性优化问题的最有效的方法之一，对于方法的研究已经成为近十年来非线性最优化领域的一个热点这类方法是通过解一系列的二次规划子问题来近似（）一（，）的的解，每一个二次规划问题都得到一个搜索方向呶，

28、算法一般通过价值函数确定搜索步长，使瓢十毗在某种意望匕近似极小值点文考虑般非线性约束问题（）一（），由法得到（）一（）的二次规划子问题为；，（），（）（）（，）“，其中（）（），。（）（），（），（），仉），仉，岛舻”是函数的的近似记（）一（）的解为靠逐步二次规划法用以作为搜索方向也是许多罚函数的下降方向，在一定条件下方法具有快速的局部收敛速度在约束优化中，线搜索中用到的函数是来判断试探点好坏的。所以这个函数被称为价值函数为了得到全局收敛性，算法经常使用罚函数作为价值函数，比如工精确罚函数，光滑精确罚函数但是罚函数有可能会破坏超线性收敛。这种现象通常被称为效应一般说来，利用光滑罚函数作为价值函

29、数可避免效应目前型算法存在两个重要问题：一是每步需要求解至个二次规划子问题以得到迭代方向，计算工作量较大，难以应用于大规模优化问题，也难以利用有些问题的稀疏、对称等良好特性；二是这些子问题可能无解，尽管此时可用其它措施重新定义迭代方向，但必然增加算法的复杂性，增大计算量，导致理论证明不完善文献提出序列方程组法在一定程度上解决了上述问题因为方法采用拟牛顿法构造，所以具备了拟牛顿法的优点，【、均、，【等基于此提出一些算法圳证明了这类方法都具有局部超线性收敛速度这些方法一般在反正定的情况下直接对取校正。在风不一定正定的情况下则对增广函数的进行校正由于增广项在靠近解的时候会导致矩阵病态，为解决这一问题

30、，【】使用一修正的校正公式来保证矩阵的正定性，但是遗憾的是此方法不能达到局部超线性收敛速度。而且会产生病态的逼近既约法既约法（简称既约法）是从法发展出来的方法它的基本思想是只利用既约或者是近似既约构造的求解约束优化的算法。这类方法的优势在于；在迭代过程中，由于只利用了函数的部分信息。所以矩阵的维数相对较小。每次迭代计算量较小。算法所需内存也小而且由于函数的既约在解处是正定的，所以用拟牛顿公式校正不需要引入增广项。从而避免了病态现象既约法一般可分为双边既约法和单边既约法和【踟首先提出双边既约法的思想。【】，【】、嗍、】分别对等式约束问题提出了一些算法并且对收敛性进行和了分析嗍，和【】提出了解决不

31、等式约束问题（）提出单边既约法，并且证明了此方法具有局部步的算法，这些算法一般都具有局部步卜超线性收敛速度超线性收敛速度的研究和在文献【】中给出了个利用厶价值函数的全局收敛的既约算法在第二章我们会对既约法作更详细本文的创新点近年来，许多学者对双边既约方法进行了研究，但是由于双边既约法忽略了一项的计算。使得收敛速度出现一步快步慢的现象，只能得到步卜超线性收敛速度本文提出一种分别对单边既约和双边既约校正的新算法，在一定条件下证明了新算法具有局部步卜超线性收敛速度我们还将分析新算法使用光滑罚函数作为价值函数时的全局收敛性在第二章中，就非线性等式约束问题，提出一种既约校正算法，此算法分别对函数的单边既

32、约的近似阵和双边既约的近似阵进行校正我们证明了若每次迭代至少有一者被校正时，算法具有步卜超线性收敛速度在第三章中，以第二章提出的算法为基础，提出一种解决非线性等式约束同题的既约方法为避免效应，此方法采用的光滑精确罚函数的逼近形式作为效益函数，在一定条件下证明了算法的全局收敛性在第二章和第三章中，我们都做了适量的数值实验，其中的测试函数均出自文献】一种非线性等式约束问题的既约算法在这一章中，就非线性等式约束问题，提出一种既约算法。此算法分别对函数的单边既约的近似阵和双边既约的近似阵进行校正我们证明了若每次迭代至少有一者被校正时，算法具有步（卜超线性收敛速度引言考虑等式约束问题（）其中，：矿一，：

33、，仇都是二次连续可微的记（）；岛（）（），（）（）。（）】，（）【（）。（）】假设，的矩阵在点是连续的矩阵函数，（）列满秩，且设（）的分解有如下形式：，（习（）。（）元（）【扛）（）】孑，的零空间孔是（）的局部极小点的一阶必要条件是（）（。），（。），（）其中（）是×阶列正交矩阵，（）是×一）阶列正交矩阵，（）是×阶上三角阵；（）的列张成（）的值空间，（）的列张成（）（）（）为乘子而（）表明。是函数（，）一）的稳定点设（，）是（，）二阶导数。即则轧是的（）局部极小点的二阶必要条件是（）（茹。，九归（￥。）半正定，二阶充分条件是（。）（，）（正。）正定证明见文献【】

34、既约方法是通过约束函数切空间上函数的二阶导数的近似信息来求问题（）的局部极小点它是由法发展起来的方法由于只利用了函数阵的部分信息，所以算法在每次迭代计算量小且算法所需内存也小记法试探步为（也，（民）则满足【毪第“。如卜【，（一），（【一（）简化即得【（）一【一（，）羟一川蛩酽【凳一。囝国一酽其中瓢儿（民），设国？则上式可以写为由（）得磙况昭巧一帆霹孙洲二兹篆纠【船（）蟊女一甜，若考虑（）的后两行（分块意义下）则可得（）蟹喾耀磊船【一磺翟鲰【仇（）即有曜一，耀一况弧一刃在求解过程中需要求，般采用最小二乘法即（）（）从而可解出呶当列满秩，且刃矸名旅正定时，（）一（）的解唯一唼“一珊解得巧（）既约方法一般有两种，即单边既约法和双边既约法两种方法一般都采用拟牛顿公式对函数的既约的近似阵进行校正常用的拟牛顿公式有公式。公式，公式，即风鱼生二里生生亟磊；巡一（礤靠）。，（。）单边既约法一般用）“代替刃，由（）可得（矿），城船蚍；（删玩慧一訾：卜一磐【蚝（¨）用（）校正得和在文献】中证明了单边既约法是局部超线性收敛的。但是没有保证仇磊的正定性双边既约法一般用（”“，。扣一“，代替巧反，用零矩阵代替蚕圪，则由（）可得一詈陋】一磐用保持正定性的校正公式如（）或（）校正玩得最如文献【】【】【中的方法，这些方法都只得到了步超线性收敛速度文献】提出在一定