《基于平均值的非单调线搜索方法综述》3300字

基于平均值的非单调线搜索方法综述目录TOC\o"1-2"\h\u17137基于平均值的非单调线搜索方法综述 113871.1基于平均值的非单调线搜索方法的相关定义及算法概述 1265291.2算法全局收敛性的证明 2174561.3R−线性收敛性的证明 41.1基于平均值的非单调线搜索方法的相关定义及算法概述为了克服Grippo等三位学者所提出的非单调线搜索方法的局限性，Zhang和Hager围绕前者提出了一类新型的非单调线搜索方法。其中最为核心亦最具有突破性的改变即是用一系列函数值的平均值替换了式（1.2.4）中的最大值函数。修正后的线搜索方法包括以下两部分核心内容。1）线搜索更新过程。线搜索过程要求得到的步长αfxk+α∇fxk+或能满足Armijo搜索准则，即令αk=αkρℎk，ℎk是能使式（1.2）代价更新过程。Qk+1=ηkQ Ck+1=ηkQ其中各参数须满足：0≤ηmin≤ηmax≤1，ηk∈ηmin,ηmax，0<δ<σ<1<ρ。Ck和Qk事实上，ηk的选择将在很大程度上影响此方法的非单调程度。当ηk取0时，Ck与fxkCk+1=i=0kf1.2算法全局收敛性的证明Zhang和Hager已经证明在适当条件下，该非单调线搜索方法在适当假设成立前提下，对非凸目标函数均具有良好的全局收敛性。为证明该方法的全局收敛性，我们首先需要证明引理1。引理1:当目标函数fx在水平集L=x∈R∇fx且下降方向始终满足方向假设（1.2.5）时，在该非单调线搜索的每次迭代过程中，均有fxk≤Ck成立。更进一步地，当目标函数fx有下界且下降方向证明：定义函数Dkt我们对其进行求导，得到导数Dk'又因为∇fxkTpk≤0，代入步长更新公式（fk=D根据Wolfe规则及Armijo规则的定义可知，当∇fxkTdk<0且目标函数有下界时，必然能搜索到满足标准Wolfe规则、标准Armijo规则的αk。又结合式（2.2.4事实上，太小的步长更可能导致算法陷入下降速率缓慢的困境中。Zhang和Hager提出的这种非单调线搜索框架能够有效规避这种风险，他们在文章中证明了由该方法生成的步长是具有下界的。引理2：当该算法采用的迭代方向始终为下降方向，即满足∇fxkαk≥对于采用Armijo线搜索准则的步长，αk≥证明：我们需要对上述两种情形进行分类讨论。当αk∇fx又因为梯度∇fLipschitz连续∇fxk+结合式（2.2.7）及（2.2.8）并运用Cauchy-Schwarz不等式，式（2.2.5）即可得证。对于αk满足Armijo准则的情况，我们进行进一步地分类。若ραk≥μ，显然此时有α≥μ/ρf又因为梯度∇fLipschitz连续，易得整理上式后可得，(δ−1)∇基于引理1、引理2，Zhang和Hager证明了该单调非线搜索方法的全局收敛性，即由该算法生成的迭代序列xlim证明：首先分情形讨论。当αkα结合（1.1）式及方向假设，我们可以写出f当ρf当αk满足Wolfe准则时，代入Wolfe情形下对应的α令w=min⁡fk+1≤再将式（2.2.9）代入代价更新公式，可得C因为Ck≥fk且f又因为Q假设limk→∞∇f(xk)k=0因此假设不成立。limk→∞1.3R−线性收敛性的证明当目标函数为强凸函数时，该非单调线搜索方法被证明在适当条件下能够R−线性收敛到最小值。假设fx为强凸函数，在x∗处具有唯一最小值f∗，函数梯度∇fx在有界集上Lipschitz连续，下降方向pk始终满足方向假设（1.2.5）。fx证明：由梯度的Lipschitz连续性可得∇又根据方向假设及α∇再结合三角不等式，我们可以得到∇f(x代价更新公式可以被写为Ck+1−f结合（2.2.9）式，可得C又因为Q所以有C在接下来的证明中，我们需要引入未知常数b作为衡量梯度大小的尺度。当Ck+1−f∗已知fx∇fx−∇其中μ'>0是凸性量度。又因为x∗μ根据凸函数的性质，可知gt=fx∗f结合式（2.3.4），可以写出f当∇f将上