有效集信赖域算法及其全局收敛性理论的研究和数值试验

R→RR→R={，.，}=0Journalof the Egyptian Mathematical Society（2016）24，672埃及数学学会埃及数学学会会刊www.etms-eg.orgwww.elsevier.com/locate原创文章邻点惩罚有效集信赖域算法Bothina El-Sobky埃及亚历山大大学理学院数学和计算机科学系助理教授接收日期：2015年12月17日;修订日期：2016年3月25日;接受日期：2016年4月20日2016年5月24日在线发布摘要本文利用有效集策略、Coleman-Li策略和罚函数法，将变量有界的一般非线性规划问题转化为变量有界的无约束优化问题。一个信任区域的全球化策略被用来计算一个步骤。在可信的假设下，给出了算法的全局收敛性理论.对该算法进行了初步的数值试验。给出了算法在一些经典问题上的实现。1. 介绍2010年数学学科分类： 90C30; 90C55; 65K05; 49M37，版权所有2016，埃及数学学会. Elsevier B. V.制作和托管这是CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。其中f：n，a：n m，E I1m和E Iα∈{R{−∞}}n，β∈{R{∞}}n，mn，和αβ。的={个在本文中，我们考虑以下约束优化-问题最小化f（ x）函数f和a i，i1，...， m被假定为至少两次连续可区分。 我们将可行集F= {x：α≤x≤β}和严格内部可行集int（F）={x：αx<β}。服从i（x）=零i∈E，ai（x）≤0i∈I，α≤x≤β，*通讯作者。联系电话：+201156646045。电子邮件地址：bothinaelsobky@yahoo.com（一、一）本文利用文献[1]中的一个有效集策略，将上述问题转化为有界变量的等式约束优化问题。所建议的活动集的头特征是它是由步长自然地识别和更新的。参见[2本文利用罚函数法对得到同行评审由埃及数学学会负责从上述步骤到变量有界一些罚函数已被提出，并已作出许多贡献，解决这些方法的收敛性，见[5，6]。S1110-256X（16）30025-6 Copyright 2016，Egyptian Mathematical Society.制作和主办：Elsevier B.V. 这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。http://dx.doi.org/10.1016/j.joems.2016.04.003制作和主办：Elsevier关键词有效集;罚函数法;内点;Coleman–Li strategy;Trust全局收敛性邻点惩罚有效集信赖域算法673;=⎧⎪⎨,−∇;≥−∞22=∈x（j）2∈2T利用文献[7]中的更多详情见[7在本文中，我们使用信赖域策略来评估一个步骤。信赖域策略是一种全局化方法，它意味着对局部方法进行修改，即使出发点离目标很远L（ x，λ，μ;r）=φ（x;r）−λT（x−α）−μT（β−x），（2.4）其中λ和μ分别是与不等式约束x−α≥0和β−x≥0点x∈是问题（1.1）的解的一阶必要条件是乘子λ∈Rn，且μ∈Rn，使得（x∈，λ∈，μ∈）满足lution. 求解约束++问题的大多数信赖域算法最优化问题尝试将信赖域思想与序列二次规划方法相结合参见[2在可信的假设下，我们的算法的收敛性理论。本节的其余部分将介绍一些表示法，φ（xα≤x≤β，（2.6）对于所有对应于x（j）的有限界，我们有λ（j）（x（j）−α（j））=0，（2.7）在论文的其余部分使用这张纸被安排得乱七八糟如下在第2节中，详细描述了主μ（j）（β（j）−x（j））=0，（2.8）形成序列二次规划子问题的步骤本文介绍在第3节中，给出了一个邻域点信赖域算法的详细描述。第4-哪里φ（x<$r<$）f（ x<$）r<$A（x）W（x）A（x）。设Z（x）是对角缩放矩阵，其对角ele-e-部分由下式给出：在重大假设下。第10节包含一个材料-实验室实现的邻域点信赖域算法和我们的数值结果。第11最后总结--z（j）（ x）=（x（j）α（j）），如果（φ（xr））（j）0且α（j）>，，（β（j）−x（j）），如果（φφ（x;r））（j）0且β（j）+∞，ing的评论。本文利用符号fk=f（ xk），fk=第一个，否则。（2.9）W k W（x k）等来表示特定点处的函数值。我们将目标函数fk的Hessian表示为Hk或其近似。最后，所有的范数都是l2-范数。2. 一个序列二次子问题受[1]中的有效集策略的启发，我们定义了一个0-如果i∈E，∈≥i更多详情请参见[7，8]。使用对角尺度矩阵Z（x），点x∈F解问题（1.1）的一阶必要条件是x∈F，并解以下非线性系统Z2（x）<$φ（x; r）= 0.（2.10）任何满足条件（2.10）的点x<$F称为更多详情请参见[5]。一个系统（2.10）在某点x∈F是连续的但不可微的。当z（j）=0时，∈wi（ x）=1， 如果i I和a（ x）0，如果i∈I且ai（x）0，（2.1）这些点通过限制x intF来避免。 也当一个变量x（j）有一个无穷大时，下界和无穷大上界，且（φ（x;r））（j）=0。使用上面的矩阵，问题（1.1）被转换为以下最小化f（ x），假设A（ x）T W（ x） A（ x）=0，但是这些点并不重要，所以我们定义一个向量（x）其分量是：n（j）（x）= n（（z（j））2），j = 1，.， n使得当（φφ（x;r））（j）=0时，φ（j）为零因此，我们可以写如果（φφ（x;r））（j）≥0且α（j）>−∞，- ;+∞α≤x ≤β，其中A（x）=（a1（x），.，am（ x））T 是一个持续不断的过程，（j）（x）=1， 如果（φ（xr））（j）<0和β（j）<，000， 否则。（2.11）tiable函数利用罚函数法，将上述问题转化为如下变量R假设x int（F），并在系统上应用牛顿tem（2.10），则我们有[Z2（x）<$2φ（x;r）+diag（<$φ（x;r）） diag（<$（ x））]<$x= −Z（ x）<$φ（x;r），（2.12）minimize f（ x）+W（x） A（ x）（二、二）哪里在α≤x≤β条件下，其中r>0是惩罚参数。让<$φ（x;r）=H+r<$A（ x） W（ x）<$A（x），（2.13）而H是目标函数f（x）的Hessian或一个近似值，R2模拟。 将等式的两边相乘。（2.12）由Z−1（x）和φ（x; r）= f（x）+2 <$W（x）A（x）<$.（二、三）与有界问题（2.2）相关的拉格朗日函数由下式给出：使用x=Z（ x） s缩放步长，则我们有[Z（ x）<$2φ（x;r） Z（ x）+diag（<$φ（x;r）） diag（<$（ x））]s= −Z（ x）<$φ（x;r），（2.14）2674B. 埃尔-索2∈Rk2 2≤=K=K联系我们⎪⎧⎪KKKKKKKK2K步骤Scp. 即Predk1Predk2KKKKtcp=0≤δk且（Zk<$φ（xk;rk））T⎩kk2k kK K注意，公式2.14表示下列序列二次规划问题的一阶必要条件最 小 化 φ （ x;r ） + （ Z<$φ （ x;r ） ）Ts+1sT Bs ，（ 2.15）其中B=Z（x）<$2φ（x;r）Z（x）+diag（<$φ（x;r））diag（<$（x））. （2.16）也就是说，满足问题（2.15）的一阶必要条件的点xx x将满足问题（1.1）的一阶必要条件。在下面的部分中，我们提出了我们的邻点信赖域算法解决问题（1.1）的主要步骤。3. 邻点信赖域算法本节专门介绍一种新的边界点法。int（F）. 计算阻尼参数τk的方法在下面的算法（3.3）的步骤4中给出可能需要另一个阻尼参数θk来满足xk∈int（F），其中θk定义如下。若（xk+τkZksk）∈int（F），则设θk=1.否则，我们设置xk+1=xk+θkτkZk sk，使得θk∈[1−σ<$Zk sk<$， 1]且σ>0是预定义常数。很容易看出1−θk=O（<$Zksk<$）。3.2. 接受sk并更新δk在得到sk后，用罚函数φ（xk;rk）作为评价函数，检验步长sk是否可接受.这是通过比较Predk和Ardk来完成的。实际减少量Aredk定义为：Aredk=φ（xk;rk）−φ（xk+Zkτksk;rk）其中reτk=θkτk。一个redk可以写为Aredk=f（xk）−f（xk+Zkτksk）+2[W k A k−W k+1A k+1]。（3.4）预测的减少Predk被定义为3.1. 评估步骤sk在本节中，通过求解以下方程来计算步长sk：Predk= −（Zk<$fk）RKTτs−1τ2sTGs2T2信赖域子问题minimize q（ Z s）=φ（x;r）+（Z<$φ（x;r））T s+1sT Bs哪里+2[WkAk− <$Wk（ Ak+（Zk<$Ak）τksk）]，（3.5）如果δs≤δk，（3.1）其中δk>0是信赖域的半径不需要得到子问题（3.1）解的非常精确的近似。相反，只要由sk得到的预测减少大于或等于，就可以使用对子问题（3.1）的解的任何近似Gk=ZkHkZk+diag（<$φ（xk;rk））diag（ηk）.我们测试sk和更新信赖域半径δk的方法在下面的算法中给出。算 法 3.1 （ 测 试 s k 并 更 新 信 赖 域 半 径 算 法 ） 。 选 择0<η1<η2 1，δmax> δmin，0<α1 1<α2。<到一个分数的预测减少得到的柯西当Aredk<η或Pred≤0。Kqk（0）−qk（ Zk sk）≥<$ [qk（0）−qk（ Zk scp）]，（3.2）设δkα1sk。评估一个新的SK。K如果η ≤Aredk<η，则设x=x+τZs.对于某个ε∈（0，1]，其中scp由下式给出：δk+1max（δk，δmin）。如果结束CP CP若Aredk≥η2，则n个集合xk+1=xk+τkZksk.sk= − tk（ Zk<$φ（ xk;rk）），参数tcp定义为：Predkδk+1min δmax，max δmin，α2δk。如果结束为了更新惩罚参数rk，我们使用一个方案sug-<$（Zk<$φ（xk;rk））<$2（Zk<$φ（xk;rk））TBk（Zk<$φ（xk;rk））如果<$Zk<$φ（xk;rk）<$3（Zk<$φ（xk;rk））TBk（Zk<$φ（xk;rk））袁世凯[12]。我们更新rk的方法在下面的算法中给出。Bk（ Zk<$φ（xk;rk））>0，⎪δ设置rK=1。计算Predk由Eq。（3.5）。K<$Zk<$φ（xk;rk）<$否则，请执行以下操作。K1K+1算法3.2（更新r算法）。邻点惩罚有效集信赖域算法675如果（3.3）因此，由Stei-haug[11]引入的广义狗腿算法可用于评估步长。一旦计算了步长sk，就计算阻尼参数τk以确保：Pred k ≥<$Z k<$A k W k A k <$min {<$Z k <$A k W k Ak<$，δk}.（3.6）设rk+1=rk。否则，设rk+1=2rk。676B. 埃尔-索联系我们=∈ǁ ǁ ≤ǁ ∇ ǁ + ǁ ∇ǁ≤={}∈∇⎩（i）∈ +∈u（iR>−∞且Zksk <0（i）（k， 如果α∗∗K第五（i）（k， 如果β< ∞和Zksk >0个（2.10），点（x，1，να）称为KKT点。∗ikkEnd if对于以下情况，要么是<$Zk<$fk<$+<$Zk<$Ak WkAk<$≤ <$1，要么是<$sk <$≤ <$2，[GA 1]函数f和ai，i= {1，.，m}被假定为至少两次连续可导的<$x∈▲。当<$1>0和<$2>0时，算法停止[GA2]所有f（x），f（x），2f（x），ai（x），a i（x），i1，.，m在▲中一致有界。3.3. The master algorithm我们的算法的主要步骤如下所示。算法3.3（主算法）。第0步。intx（F）=0 计算矩阵W0、Z0和Z0。设置r01。选 择 <$1 ， <$2 ， α1 ， α2 ， η1 ， η2 和 σ ， 使 得 <$1>0 ，<$2>0，0<α1 1<α2，0<η1<η2≤ 1，且σ >0。<选择δmin、δmax和δ0，使δmin≤δ0≤δmax。设k=0。步骤1.如果Z Kfk ZkA k W k A k<$1，然后停止。步骤3.步骤sk通过求解子问题（式3.1）来计算。如果sk<$2，停止，结束。步骤4.(a) 计算[GA3]证明了Hessian矩阵序列{Hk}是有界的.在上述一般假设中，我们不假定a i（x），i 1，.，m对所有的x都有逆。所以，我们可能有其他类型的驻点。下一节将介绍这些情况。5. 驻点在本节中，我们定义了四种驻点，Fritz John点，不可行Fritz John点，不可行Mayer定义5.1（Fritz John点）。 点x∈▲称为Fritz John点，如果存在γ∈R且Lagrange乘子向量ν∈Rm不全为零，使得：γ<$Z（ x<$）<$f（ x<$）+Z（ x<$）<$A（ x<$）ν<$=0，（5.1）⎧⎨α(i)−x(i)K（i） K = Z（一）(i)（一）W（ x） A（ x）=0，（5.2）1，否则，(b) 计算γε，（νε）i≥0，i= 1，2，.，（5.3）上述条件称为Fritz John条件。为⎧⎨β(i)−x(i)KKK =Z（一）(i)（一）更多详情见[13]。如果γf =0，则等式（5.1）-（5.3）对应于KKT条件-1、否则。∗γ∗(c) 计算τk=min {1，min {u（i），v（i）}}。（第3.7节）(d) 设xk+1=xk+τkZk sk。如果xk+1∈int（F），则转到步骤5。否则，设xk+1=xk+θkτkZk sk，end。步骤5.计算公式2.1给出的Wk+1。步骤6.测试步骤并使用以下命令更新信赖域半径算法（3.1）。步骤7.使用算法（3.2）更新惩罚参数rk。步骤8.计算公式2.9给出的Zk+1和公式2.9给出的Zk+1，定义5.2（不可行的弗里茨约翰点）。一个点x<$∈▲称为不可行Fritz John点，如果存在γ<$∈ R和一个Lagrange乘子向量ν<$∈ Rm不全为零，使得：γ<$Z（ x<$）<$f（ x<$）+Z（ x<$）<$A（ x<$）ν<$=0，（5.4）Z（ x<$）<$A（ x<$）W（ x<$）A（ x<$）=0但<$W（ x<$）A（ x<$）<$> 0，（5.5）γε，（νε）i≥ 0，i= 1，2，.， M.（5.6）上述条件称为不可行Fritz John条件。更多详情请参见[13]。如果γ = 0，则方程（5.4）-（5.6）称为不可行KKT条件，点（x∈，1，ν∈）称为不可行KKT（2.11）。γ点步骤9.设置k=k+1，然后转到步骤1。在第5 - 9定义5.3（不可行的梅耶-布利斯点）。 A点x称为不可行的Z（ x<$）<$A（ x<$）W（ x<$）A（ x<$）=0，W（x▲∈是4. 一般假设设{x k}是由算法（3.3）生成的点序列，设▲是n的凸子集，包含所有迭代x k int（F）和x kτk Z k s k int（F），对于所有试验步s k。在集合▲上，我们提出了下列一般假设，在这些假设下，我们的全局收敛理论得到了证明.一般假设：∗邻点惩罚有效集信赖域算法677上述条件称为不可行Mayer-Bliss条件。更多详情请参见[14]。在定义（5.1）-下面的三个引理提供了与定义（5.1）-（5.3）中给出的条件等价的条件678B. 埃尔-索--.ΣΣd∈RnKk→∞/=k→∞{}=--=我我（2）limki→∞mins∈Rn−m <$Wki（Aki+（Zk<$Aki）Tτ<$kis）<$2=KKKKK Kk→∞KKKK我我我我我k→∞ d∈RnkK+引理5.1. 假设GA1-GA 3.一个子序列x ki的迭代序列渐近满足不可行的(2) limki→∞.mins∈Rn−m<$Wki（Aki+（Zk<$Aki）Tτ<$kis）<$2WkAk=1。条件，如果它满足：(1) limki→∞i。WkiAki>。0的情况。证据 让子序列{ki}重命名为{k}以简化删除符号，避免双索引。条件2相当于lim ki →∞ <$W ki A ki <$2.证据让子序列{k i}重命名为{k}，以简化不包含双指标的非条件。最小的zersk对于mins<$Wk（Ak+（Zk<$Ak）Tτ<$ks）<$2sa，利姆min. Uk+Wk其中Uk是Wk Ak方向上的单位向量，d=s。2吨WkAkτkZkAkWkAkZksk+τkZkAkWkAk=0，（5.7）根据条件2，我们有利姆τ2sTZkAkWkATZksk+2τksTZkAkWkAk=0.设dk是以下问题min.，（5.11）那么，从最优性条件我们有k→∞k k k k（5.8）（Zk<$Ak）Wk（Zk<$Ak）Tτ<$2d<$k+（Zk<$Ak）WkUkτ<$k=0，（5.12）我们考虑两种情况：(i) 如果limk→∞sk=0，则公式（5.7）中的n为lim{τkZk<$AkWkAk}=0.（5.9）(ii) 如果limk→∞s=0，则通过迭代等式1，（5.7）从我们考虑两种情况：(i) 如果在上面的等式中lim k→∞d<$k = 0，那么我们有，limk→∞（Zk<$Ak）WkUkτ<$k=0。(ii) 如果limk→∞d<$k 0，则从（5.10）和d<$k是a的事实对于公式5.11中的最小化问题，我们有lim{d<$kT（Zk <$Ak）Wk（Zk<$Ak）Tτ<$2d<$k左移2s<$T并从公式5.8中减去，我们得到k→∞k+2UTW（Z}=0。利姆τ2sTZkAkWkATZksk=0.从左起乘以2 d<$T 然后减去它从上述限制，我们有但这意味着tlimk→∞{τ<$kZk<$AkWkAk}=0。因此limτ<$2d<$（Z<$A）W（Z<$A）Td<$=0。在这两种情况下，k→∞kkkk k k k klim{Zk<$Ak Wk Ak} = 0，其中relimk→∞τk=1。定义的条件这意味着limk→∞Zk Ak Wk Ukτk0。因此，在这两种情况下，我们有lim{Z<$A W U}= 0，（5.13）（5.3）保持在极限状态。 QKk→∞KKK引理5.2. 假设GA1-GA3.迭代序列的子序列x ki渐近满足不可行Fritz John条件，如果它满足：(1) lim ki→∞W kiA ki> 0。(2) lim ki →∞ Z ki <$A ki W ki A ki = 0.证据让子序列{ki}重命名为{k}以简化符号，避免双索引。根据条件2，我们可以写lim Z k Ak Wk Ak0的情况。k→∞设（νk）i=（WkAk）i，i=1，m.由于limk→∞<$Wk Ak<$>0，则limk→∞（νk）i≥0，对于i=1，，m和limk→∞（νk）i>0，对于你的身份因此limk→∞Zk<$Akνk= 0。因此，在有限的，γ=0，定义式（5.2）的条件成立。Q如果limk→∞fk Zk Akνk 0，则在极限中满足不可行（KKT）条件。否则，满足不可行的Fritz John条件。引理5.3. 假设GA1-GA3. 一个迭代的子序列{x ki}，邻点惩罚有效集信赖域算法679K∇=其中limk→∞τk1。接下来的证明使用了与上面引理中类似的论证。Q从引理（5.3）我们可以看到，对于满足Fritz John条件的迭代序列的任何子序列，Wk A T的最小奇异值的相应子序列没有远离零的这意味着主动约束的梯度是线性相关的。在下面的部分中，我们介绍了证明我们的主要结果所需要的一些引理6. 重要引理下面的引理表明，在任何迭代k处，预测的减少Predk至少等于通过柯西步骤获得的惩罚函数的二次模型引理6.1.假设GA1-G A 3. 对于所有k>k′，rex是与迭代无关的正常数K1.Z如果满足以下条件，则序列渐近满足Fritz John(1) 对所有的ki，有W kiA ki> 0且lim ki→∞W kiA ki =0。Predk≥K1τk<$Zk<$φ（xk;rk）<$minδk，KKKBk.（6.1）680B. 埃尔-索KKK2.×kT2.ΣKK∈∈RK<$Zk<$φ（xk;rk）<$+KK不<$Zk<$φ（xk;rk）<$KCIBBǁ=T˜Σ证据 由于试验步s k满足柯西分数递减条件（3.2）。然后我们考虑两种情况：(i) 如果scp= −δk（Zk<$φ（xk;rk））且<$Zk<$φ（xk;rk）<$3其中i = 1，2，...，M. 然后Wk1=Wk+ Dk。（6.5）≥δk[（Zk<$φ（xk;rk））TBk（Zk<$φ（xk;rk））]，则qcpTcp1cpTcp证据证明类似于[3]中引理6.2的证明。Qk（0）− q k（Z k sk）= −（Z k<$φ（x k; r k））sk− 2 skB K SK引理6.4. 假设嘎-嘎。在任何迭代k，存在1 3δk2=Zk1δ2不与k无关的正常数K1，使得DkAk- 2<$Z<$φ（x;r）<$2（（Zk<$φ（xk;rk）） Bk（ Zk<$φ（xk;rk）））KKK1其中Dk∈ Rm×m是对角矩阵，其对角元素≥2 δk<$Z k<$φ（x k; r k）<$。（6.2）(ii)如果 scp= − < $Zk<$φ（xk;rk）<$2（Z<$φ（x;r）），以及在（6.4）中定义。证据证明类似于[3]中引理6.3的证明。Qk（Z k <$φ（x k; r k））T B k（Z k <$φ（x k; r k） ）kkK<$Z k<$φ（x k; r k）<$3 ≤δk（（Zk<$φ（xk;rk））TBk（Zk<$φ（xk;rk）），则q（0）−q（ Z scp）= −（Z<$φ（x;r））T scp−1scpTB scp2引理6.5。设GA1>0，不依赖于k，使得k k kkKKKk kk k21<$Zk<$φ（xk;rk）<$42 （Zk<$φ（xk;rk）） Bk（ Zk<$φ（xk;rk））≥.（6.3）|≤K 3 τ k r k s k。|≤K3τ˜krkǁskǁ.（6.7）证据 从Eqs。（3.4）和（6.5）我们有R200亿美元KAredk=f（xk）−f（xk+Zkτksk）+[ATWkAk2K根据不等式（3.2）、（6.2）和（6.3），我们有T-A（xk+Zkτksk）（Wk+Dk）A（xk+Zkτksk）].qk（0）−qk（ Zk sk）≥K1<$Zk<$φ（xk;rk）<$ minδ，<$Z k <$φ（x k;r k）<$.Bk根据上述公式，Eq. （3.5），并使用柯西-施瓦茨不等式，我们有2根据上述不等式和以下事实，陶尔克|阿雷德-普雷德|≤|S Z（x）f（x）kk2kKK2qk（0）−qk（Zkτksk）≥τk[qk（0）−qk（Zksk）]，当0≤τk≤1时，qk（0）−qk（Zkτ<$ksk）≥K1τ<$k <$Zk<$φ（xk;rk）<$min−f（xk+<$1Zkτksk））Zksk|τ2+ 2 | sk diag (∇ φ(x k; r k)) diag (ψ) s k|+rkτk|Zk（Ak−A（xk+2Zkτksk））WkAksk|rkτ22但是，由式（3.5）给出的预测减少量可以写成如下形式− <$A（xk+<$2sk）Wk<$A（xk+<$2Zkτ<$ksk）rkτ22[英语泛读材料|+2DkAk+rkτk|Zk<$A（xk+<$2Zkτ<$ksk）DkAksk|P redk=q（0）−q（Zkτksk）。rkτ2T T+2个|skZk[A（xk+2sk）DkA（xk+2Zkτksk）]Zksk|因此Predk≥K1τkZk<$φ（ xk;rk）<$min.δk，<$Z k <$φ（x k;r k）<$。BkQ对于某个<$1和<$2（0，1）。从引理（6.4）和一般假设出发，完成了证明. Q7. 当rk趋于无穷大时的收敛性在这一节中，迭代序列的收敛性是引理6.2. 假设GA1和GA3。则W（x）A（x）在▲中是Lipschitz连续的。证据证明类似于[1]中引理4.1的证明。Q由上面的引理，我们得到了A（x）TW（x）A（x）是可导的，且λA（x）W（x）A（x）在▲上是Lipschitz连续的.引理6.3. 在任何迭代k处，设D（x k）m×m是对角矩阵，其对角元素为如果（Ak）i0且（Ak+1）i≥0，则为n= 1，TT+| sZ k[A k W k A× δk，K.KK不邻点惩罚有效集信赖域算法681ǁǁ当参数rk趋于无穷大时，从算法（3.2）中，我们观察到序列{rk}仅当存在无限个索引子序列{ki}索引可接受步骤的迭代满足，对于所有k∈{ki}Pred k<<$Z k<$A k W k A k <$min {<$Z k <$A k W k Ak<$，δk}.（ 7.1）下面的引理研究了当lim sup k→∞W k A k时的情况>0。引理7.1. 假设GA1-GA3. 如果r k→ ∞，则当k → ∞时，（dk）i=−1 if（Ak）i≥0 and（Ak+1）i 0，<否则，（6.4）存在索引迭代的子序列{kj}，满足对所有k∈{kj}，<$Wk Ak<$$> ≥<$1>0，则⎪682B. 埃尔-索≥rkkrkǁ ∇ ǁ ≥→∞rkkrk1KiǁKi∇∇Ki→ ∞ ǁ∇ǁ2≥ ε3。（7.4）krk公司简介RKMayer-Bliss条件在极限情况下。使用引理（5.1），-Wk（ Ak +（Zk<$Ak）τ<$ksk）<$}≥rkε1→∞。×δk，RKKRK0的ε1，根据定义（5.3），我们有：ZKAk Wk Ak对 于 某些ε2> 0。由于rk，则存在无限个可接受的迭代，不等式（7.1）在此条件下成立。我们考虑两种情况：(i) 若<$WkAk<$2−<$Wk（Ak+（Zk <$Ak）Tτ<$ksk）<$2≥ε1，则有可接受的步骤，使得不等式（7.1）成立。但不等式（7.1）可以写成：Pred k0的条件这两个矛盾证明了不[rkiG ki +Zk<$AkiWki<$A Zkρkirkiki引理 Q×1Grkii+ZkAkiWKIATZkǁǁWki、AKi下面的引理研究当rk→ ∞ask→∞，且limin fk→∞<$Wk Ak<$=0。是有界的 因此，渐近地，WkiAki 在于Z∈A零空间 WATZ+ρkiI或Z（f+引理7.2. 假设GA1-GA3. 如果r k→ ∞，则k → ∞，且KKIKiKiKrkiK KI存在迭代序列的子序列{kj}，满足对于所有k∈{k}且lim <$W A<$= 0，则ar ki<$A kiW kiA ki）<$→0。 第一种可能性只有在ρki 当k→ ∞k →0位于ma的零空间中，K王空军kj→∞王空军王空军rkiiWkiAki索引为{ k j }的迭代序列的子序列满足Fritz John的极限条件。证据让子序列{ki}重命名为{k}以简化符号，避免双索引。通过使用一个矛盾，我们证明了这个引理。所以我们假设在 极 限 中 不 存 在 满 足 可 行 Fritz John 条 件 的 利 用 引 理（5.3），存在一个常数ε3，使得这与假设（7.4）相矛盾，并意味着迭代序列的子序列满足极限中的Fritz John条件第二种可能性意味着当ki→∞时，→0。因此，作为ki，r ki Z KA kiW kiA ki 必须有界。这意味着迭代序列的子序列满足Fritz John限制条件Ss对于所有足够大的k(iii) 如果limsupk→∞KWkAk <∞和limin fk→∞KWkAk >0。| WA|ǁW A ǁs k 因此，和第二种情况一样，当k → ∞时，（7.7）式的右边趋于零。这意味着Kk<$（Z k <$A k W k <$A T Z k+ρkI）s k<$我们考虑三种情况：Z k（(i) 如果lim in f k→∞sk =0，上述不等式给出了一个条件，KKKKKKK矛盾WkAkS但这意味渐近地，Zk（fk（Zk<$AkWk<$ATZk+ρkI） sk<$(ii) 如果limsupk→∞k= ∞。从计算rk<$Ak Wk Ak）<$→0或krkK+rk{ Wk Akǁ邻点惩罚有效集信赖域算法683→0。作为SEC-sk，我们有WkAkZk第二种情况，这两种可能性意味着迭代序列的子序列满足极限中的Fritz John条件Zk（ fk+ rk<$ Ak Wk Ak）= −（ Bk+ρkI） s，这就完成了证明。 Q684B. 埃尔-索≥≤ <$b. 设<$Z <$φ（x;r）<$>2kkK布拉克=≥k→∞21K12B2δmaxk→∞22b2δmaxK4KKAredKJ. P red−1。=Pred≤Kτδ≤K.K=−8. rk有界时的收敛性在本节中，我们假设参数rk是有界的。这意味着，我们必须保证这样一个整数的存在性，定理9.1. 假设GA1-GA 3.然后由算法生成的迭代序列满足lim inf[<$Z k<$f k <$+<$Z k<$A k W k A k<$]= 0。（9.1）则对于所有k≥k<$，rk=r<$<∞。k→∞引理8.1. 假设GA1-GA3. 在任何索引为k的 迭 代 中 ， 如果 <$Z k<$φ（x k; r<$k）<$$>+<$Z k<$A k W k A k）<$$>><$1，则存在一个证据 首先，我们证明，lim inf <$Z <$φ（x;r<$）<$+<$Z<$A W A<$= 0. （9.2）正常数K4取决于<$1但不取决于k，使得KKKk→∞KKKKP redk≥K4τkδk.（8.1）证据 根据等式（2.13）、（2.16）和一般假设，GA1−GA3，则对所有k，存在b2>0，使得我 们 用 反 证 法 证 明 （ 9.2 ） 。 假 设 对 所 有 的 k ， 有<$Zk<$φ （ xk;r<$k ） <$+<$Zk<$AkWkAk<$><$1 。 设k≥k<$，考虑迭代指数k的一个试探性步长指数xedj小于kj好的。使用引理（8.1），我们有任何可接受的步骤索引kj，‹12有利用不等式（6.1），我们kj−（9.3）Askgoesstointy，nτkj→1和above不等式im-P redk≥K1τk<$Zk <$φ（xk;r<$k）<$min.δk，<$Zk<$φ（xk;r<$k）≥1Kττ<$min。一、 ‹1 Σδ≥K4τkδk，其中K4=1K1<$1min {1，‹1 }。 Q引理8.2. 假设GA1-GA3.如果 <$Z k<$φ（x k;r<$k）<$+<$Z k<$A k W k A k）<$$>><$1，则在有很多的试验，例如，满足条件≥η层，lim δkj= 0.（9.4）这意味着信赖域的半径不受以下限制。如果我们考虑一个有限的整数kj>k，并且如果prvi-我们的步骤被接受;i. e. 如果j1，则δk1δmin。 因此，在这种情况下，δkj是有界的。假设j>1。I. 例如，至少有一个被拒绝的对于一些有限的J。Predkj1试验步骤。对于被拒绝的试验步骤，我们有引理（8.3）证据 以来<$Z<$φ（x;r<$）<$+<$Z<$A W A）<$><$，则si根据引理（6.5）和（8.1），我们有Aredk|Aredk−P redk|K3r<$τkδ2K3r<$δkk k4k k42rK3对于所有i 1，2，. j 1. 由于ski是一个被拒绝的试验步，那么从更新信赖域半径的方法（见算法（3.1））和利用上述不等式，我们有现在，当步骤skj被拒绝时，δkj变得很小，并且最终δ=αsα>α（1 −η1）K4。1经过多次试验，（即，（五）接受;规则将得到满足。这就完成了证明。Qkj1kj−12rK3引理8.3. 假设GA1-GA3. 如果<$Z k<$φ（x k; r<$k）<$+<$Z k<$A k W k A k）<$$>><$1，则在给定的迭代k处，第j个试验步骤满足因此，δkj是有界的。但这与公式（9.4）相矛盾。因此，这种假设是错误的。因此，我们认为，�s�kj�≤（1−η1）K42rK3，（8.2）liminf <$Z k<$φ（x k; r<$k）<$+<$Z k<$A k W k A k<$= 0.但这也意味着（9.1）。这就完成了对那就必须接受证据通过使用一个矛盾，我们证明了这个引理。假设步骤skj被拒绝，并且不等式（8.2）成立。然后，由不等式（6.7）和（8.1），我们得到定理 Q从上面的定理，我们得出结论，给定任何<$1>0，算法终止，因为<‹1（1−η1）<| |

下载后可阅读完整内容，剩余1页未读，立即下载