非光滑凸优化的若干算法

《非光滑凸优化的若干算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、南京师范大学博士学位论文非光滑凸优化的若干算法姓名：后六生申请学位级别：博士专业：基础数学指导教师：孙文瑜20070518摘要本文主要研究目标函数是凸函数的非光滑优化问题．在光滑的非线性优化问题中，非单调技术和过滤集技术获得了很大成功．我们把这些技术引入到非光滑优化中，得到了非光滑优化的非单调算法和过滤集算法．我们给出了这些的算法收敛性证明，以及收敛速度分析．分三部分介绍如下：一、非单调近似点捆集方法Grippo等人对非单调线搜索技术做了系统的研究(f221[23112411251)，Facchinei和Lueidi[11]提出了非单调线搜索的捆集

2、算法，我们进一步研究非单调技术在Bundle算法中的应用．我们把非单调技术引／X,j!1]Schramm和Zowe[501的算法中，乇要是接受成功步的准则改变了．该算法不采用线搜索，而是一种“隐式”的信赖域方法，因此我们的算法与Facehinei和Lucidi的算法是不同的．我们给出了算法的整体收敛性证明，二、非光滑优化的非单调信赖域算法首先，非光滑优化问题minf(x)转化为rainF(z)，F(z)是，(z)的Moreau-Yosida正则化．用捆集方法得到Ffz)的近似梯度，再利用梯度近似值和Hessian近似，构造一个二次规划信赖域子问题．

3、利用截断CG方法解这个子问题，然后利用非单调信赖域策略接受步长．算法中所解的信赖域子问题是Sagara和Fukushima[49]所给出的．我们将非单调技术用于Sagara和Fukushima[49]的信赖域算法，给出了一个非单调的信赖域算法，并且证明了该算法的整体收敛性与超线性收敛性．三、拟牛顿过滤近似点方法研究过滤技术在非光滑优化问题中的应用．利用问题rain，(z)与rainF(曲的等价性，首先由割平面技术求得zk的一个近似的近似点矿(xk)，使得仇：=芦0k一矿(zk))∈钆f(f(。k))．其中“∈(0，a0‰忆O／是一常数．然后，在拟牛

4、顿方法中用ga(Xk)：=％近似代替9@k)，并且用“：=旷(xk+t)一矿0％)校正￡k+1．计算彤k+D：=

5、I讥I

6、和，(¨1)：=，(矿(zk)+dk)，我们用这样定义的数对(^(柚，，(‘))定义过滤集．我们定义的过滤集与无约束光滑优化中的过滤集不同，如果(htk+n，，(≈+1’)被过滤集接受，那么令z々+l=矿(z々)+氐，并把(^(。+”，，(‘十1))加入过滤集．否则，令z＆+1=矿(zk)．我们证明了算法的总体收敛性以及超线性收敛性．关键词过滤技术，非单调技术，信赖域方法，凸优化，非光滑优化，Moreau-Yosida正则化，捆

7、集法，近似点方法，拟牛顿方法．AbstractInthisthesis，westudythenonsmoothoptimizationproblemwheretheob-jectivefunctionisconvex．Nonmonotoneandfiltertechniquehavebeenprovedverysuccessfulinsmoothnonlinearoptimization．Weapllythesetechniquestononsmoothoptimizationandgetthreealgorithmsfornonsmoothopt

8、imizationproblems，Thesealgorithmshavebeenprovedtobeconvergentgloballyandsuperlinearly．Grippoerehavestudiednonmonotonelinesearchtechnique，FacehineiandLueidiproposednonmonotonebundle-typeschemeforconvexnonsmoothmini-mization．Wecombinethenonmonotonetechniquewiththealgorithmpropos

9、edbySchrammandZoweandwegetanewalgorithm．Themajordifferenceisthatweusethedifferentruletoacceptaseriousstep．Wedon’tIlsethenonmonotonelinesearch．andourmethodisan“implicit”trustregionmethod．Weprovetheglobalconvergenceofthealgorithm．Thenousmoothminimizationproblemminf(x)canbetransf

10、ormedintoadifferentiableconvexminimizationproblemminF(x)，wher