用自动微分分划组的修正算法解大型稀疏无约束优化问题

《用自动微分分划组的修正算法解大型稀疏无约束优化问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、大连理工大学硕士学位论文用自动微分分划组的修正算法解大型稀疏无约束优化问题姓名：吉玉霞申请学位级别：硕士专业：运筹学与控制论指导教师：张宏伟20080605大连理工大学硕士学位论文摘要非线性最优化在科学计算和工程分析等领域中都起着非常重要的作用。在大规模稀疏非线性最优化的研究中，Newton型方法一直受到人们的青睐，对它的改进一直是人们关注的问题。近年来，结合稀疏Hesse阵的结构，按照分划组的思想将矩阵列分划进行迭代是国内外研究的一个热点。它们大都涉及求解函数的梯度和海森矩阵，通常使用的计算方法是符号微分和差分近似。对于大中规模问题来说，使用符号微分，成本昂贵，有时甚至不可行，在计算导数的方

2、向梯度时，利用差分法虽然可以降低计算成本，但得到的是近似值，而且确定恰当的差分区间也很困难。自动微分是一种新的能精确而有效地计算导数的方法，它优越于传统的微分方法。例如它比符号和差分方法的计算成本低，又比差分方法计算精确。本文第一章简单介绍了大型稀疏无约束优化的解法发展历程和求解方法的综述，指出了现存方法存在的问题并提出了本文研究的专题。第二章给出了在求解无约束优化问题时比较经典的方法。第三章介绍了自动微分的求导技术，明确阐述了自动微分的基本概念、方法，根据链式法则简单解释了自动微分的两种基本模式：前向模式和后向模式；并与差分法做了相关比较。第四章是在第三章的基础上进一步讨论自动微分在求二阶导

3、数时的应用，把自动微分与相容分划的思想相结合，根据大型稀疏Hesse矩阵的结构特点，提出了分别用直接法和间接法求目标函数的Hesse矩阵，比较了它们的优劣性。第五章是将自动微分应用于PGC算法，提出了新的算法ADPGC，该算法保留了PGC算法在每个分划组内把所有元素仅仅修正一次的优点，又保证了每步迭代中Hesse矩阵与向量的乘积都能得到精确值，提高了精度，减少了函数和梯度的赋值。并通过一些优化问题给出了实验结果，结果数据表明新算法具有较好的性质。关键词：无约束优化；自动微分；Hesse阵；稀疏性；分划用自动微分分划组的修正算法解大型稀疏无约束优化问题TheP础itionedGroupCorre

4、ctionTec王ⅡliquewithAutomaticDi彘rentiationforLa唱eScaleSparseUnconstrainedOptiIIlizationAbstractNolllillearoptim协ionplays觚iIIlportaIltroleiIlⅡ瑚1yfieldssuch够sciencecom喇ionarldengillee血ganalysis．ForsolVingnolllillear叩tiIIliZationprobleIIls，Ne、玑on—likeme血odisoneof也emoste伍cientmetllods趾ditisan咖ort锄tproble

5、mt0iⅡlpr0Venleme也0d．Recently，itisahotresearchathome趾dabroadi11portiollinggroupsofthem砌xtoi钯rationw址chisbaSedon吐les仇lctureoftheHessiall．MostofthemiIⅣ01vessolVingⅡle伊adientandHessianoft王leo巧ectfhnctio玛uSuallybymeaIlSofsymbolicdi保；renti撕on．Bmforthe111iddlea11dlargescdeprobl锄s，mecompmationcostbys1门mboli

6、cdifreremia廿onisve巧expeIlSive．When也edirectionderivativeisevaJualed，meconlput；撕oncostbydivideddi虢rencec锄bereduced，buti“sonly0ne妯1dof印p姚atecomputation．Moreoveritisverydif!Eicultt0con血mthedivideddi丘Ierence缸ervmrightly．Automaticdifferentiation(AD)isametIlodWllichco珈【putesmededⅥltiveexaCtly趾def五ciemly．AD

7、11assigllificantadv锄tagesoverMoomer印proaches．Thefirstchapteroftllepaper幻灯oiIucesthelar呈rescaJesparseunconSt阳iIledopt证1izationandmesolutiondevelopmentprocess．Thenref．ert0tlleproblemsof也eexiStsolutions趾