无约束优化问题的稀疏拟牛顿法

《无约束优化问题的稀疏拟牛顿法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、曲阜师范大学硕士学位论文无约束优化问题的稀疏拟牛顿法姓名：孙国申请学位级别：硕士专业：运筹学与控制论指导教师：时贞军2003.3.12曲阜师范大学硕士学位毕业论文无约束优化问题的稀疏拟牛顿法论文分四章叙述．第一章为绪论．简要介绍稀疏拟牛顿法的提出，研究情况及研究价值。第二章针对校正矩阵为对角阵的情况提出了Armijo步长规则下的对角稀疏拟牛顿法．21引言Barzilai和Borwein提出了两点步长梯度法，其基本思想是利用迭代当前点以及前一点的信息来确定步长因子，其迭代公式Zk+1=Xk—o^gk可以看成是z

2、k+1=Xk—Dkgk，其中Dk=akI是一个矩阵．为了使D^具有拟Newton性质，计算血≈使或者其中于是，可分别求得及min

3、1Dil8k—l—Y☆一l8k一12zk—Xk一1，Yk一1。gk～gk一1OLk=if_1Yt一1川玑一1112a女=胁一lWs￡lYk—Ill曲阜师范大学硕士学位毕业论文很多学者对这类算法进行了研究，得到了若干重要结论，数值实验的结果也证明了这种算法比Cauchy法有效．于是我们在cauchy、牛顿、拟牛顿等算法的基础上并受Barzilai和Borwein算法思想的启发，提出了

4、稀疏拟牛顿法．其主要思想如下：设f(x)的Hesse矩阵的逆近似阵风+。为稀疏矩阵，并且满足拟牛顿条件，但是由于砜+-的稀疏性，拟牛顿条件式可能无法满足，此时可以通过求解m娩II风+1Yk一乳嵫使乩+l满足近似拟牛顿条件．迭代具有如下形式，Xk+2=窖七+l+口≈+1dk+1，dk+l=一风+lgk+l，a^+t为搜索步长，这就是所说的稀疏拟牛顿法．这种方法的存储量小，并且具有较好的收敛性质，适合解决大型问题．设校正矩阵Hk=diag(hI，醒，⋯，^2)，计算上k使得minlIH女Yk一。一s≈一1幢以下文

5、中”Il均为”II。．又因其中Ⅳ；-DSt一1分另q表示向量玑_l，s女一，的第i个分量．求得碡=恕，(城一，≠O)．为保证的Hk的下降性质，限制氓在一定范围内，即要求o巩，hl=Uki∈I={l，2，⋯，n}尸一《一醵tk∽。∑㈦nm=2一乳一批kH．mm一畦酥。∑㈦mv上m9“

6、1％一骓H^，●●●●(●●●●、曲阜师范大学硕士学位毕业论文2Armijo步长规则下的对角稀疏拟牛顿法假

7、设2．1：，∈C，的水平集L(如)={z∈R“If(x)曼f(xo)}有界此假设说明，，(z)和g(z)=V，(z)在L(xo)上都有界．算法2．1stepO．0<“<1，XO，XI∈Rn，k：=1；stepl．若119kll=0，则停．否则转step2；step2．求解问题(SP)计算仇，令dk=一风gk；step3．X＆+1=z^4-akdt，其中。女为{1，i1，毒，⋯)中满足下式的最大者，f(xk)～f(xk+adk)≥一a#g：d≈；step4．k：=k+1，转stepl．在问题(SP)中，以，巩在

8、每次迭代时可取正常数，也可取不同的正数．在本文中取‰=CIl协悒巩=Lk-I-C2，其中c1>0，c2>0引理2．1若假设2．1成立，算法产生无穷点列{zk)，则COS<一gk，dk>≥畿，其中<一9k，dk>表示一gk与dk之间的夹角．事实上，因{llgkll)有界，比如存在Mo>0使I协

9、

10、≤Mo，则丝≥黜氅=蕊c1UkClt22C1瓦C2怕硎2一M0+M0+”“”‘推论2．1．若假设21成立，算法产生无穷点列{xk}，则存在">0使COS<一g女，dk>≥圳鲰限2．3全局收敛性曲阜师范大学硕士学位毕业论

11、文定理21若假设1成立，则算法或有限步终止于问题的稳定点，或产生无穷点列{‰}，其任意极限点都是问题的稳定点。2．4线性收敛性假设2．2：设／(x)在极小点矿的领域内二次连续可微，且卫>0M>m>0，使得当归～z+11<￡时，有mJpyIp2SyTV2，(z)∥SMllYll2，Vy∈R“．引理2．2若假设2．2成立，则有；mI}z一27*112≤，(。)一，(z+)s；Mllz一。+ff2lf可(。)f}芝rn}fz—X+

12、f引理2．3若假设2．1，2．2成立，算法产生点列{zk}收敛到矿，则infak：Y

13、o>0．定理2,2若假设1,2成立，算法产生点列{z^)收敛到极小点z+，且00，对Vx，Y∈N(x+，E)，有下式成立V2，(Ⅳ)～V2／(x)11Sr

14、l茁一Y其中r>0．引理2．4设F：酽—}j沙在开凸集D上连续可微，则对任何z，n，"∈D有F(Ⅱ