极小极大问题束方法算法

《极小极大问题束方法算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、辽宁师范大学硕士学位论文摘要极小极大问题是一类重要的不可微优化问题，它不仅在工程设计、电子电路规划、对策论等诸多领域中有着广泛的应用，而且还和非线性方程组、多目标规划、非线性规划等数学问题有着紧密的联系．目前，求解该问题的方法有线搜索法、SQP方法、信赖域算法、有效集方法等．例如，C．Charalambous和A．RCorm提出了线搜索法，W．Murray和L．Ovemn提出了投影拉格朗日方法，A．Vardi提出了有效集信赖域算法等．这些方法的理论条件较强，适用范围小．而束方法是目前被公认为解决非光滑优化问题的最有效、最有前景的方法之一，已经被成功应用到众多实践领域．因此本文考虑应用束方法求

2、解极小极大问题．应用束方法求解非光滑优化问题的通常做法是：使用由次梯度产生的线性化函数形成的对目标函数的一个凸分片线性近似模型，然后每次迭代都是通过解二次规划得到搜索方向．同时利用次梯度选择和集技术限制束存储次梯度的数量．因此本文分为为三个部分．第一部分简述束方法的历史背景与研究现状，提出了应用束方法思想求解问题的一般步骤和算法．第二部分提出了极小极大问题，利用束方法的思想求解极小极大问题．给出了下降准则，次梯度集合的构造方法及算法的迭代程序，证明了利用聚合次梯度，可以有效减少迭代过程所储存的次梯度的信息量．第三部分证明了收敛定理．从理论上证明了这是一种更具有一般性，更实际，更有效率的一种算

3、法．关键词：非光滑：束方法：极小极：大问题：次梯度：收敛性极小极大问题t臁方法算法ABundleMethodForMinimaxProblemAbstractTheminimaxproblemiSoneofanimportantnon—differentiableoptimizationproblems，itdoesnotonlyhasbroaderapplicationsinengineeringdesigningelectronicmicrocircuitsprogramming、gametheoryandSOon，butalsohasverycloserelationshipwithn

4、onlinearequations、multipleobjective]programming、nonlinearprogramming．Atpresent，therearesomemethods，e．g．1inesearchmethod，SQPmethod，trustregionmethodandtheactive—setmethod，forsolvingminimaxproblems．Forexample．C．CharalambousandA．R．Cormgavethelinesearchmethod．W．MurryandL．Overtonpresentedtheprojectionla

5、grangemethod．A．Vardipresentedthetrustregionmethodwiththeactive-set．Thesemethodshavestrongertheoryconditionsandnarrowerapplications．Butnow，bundlemethodiSrecognizedoneofthemosteffectiveandpromisingmethodsforsolvingnonsmoothoptimizationproblems，andithasbeensuccessfullyappliedtomanypracticefields．There

6、fore，inthe：paper，weconsidertoapplythebundlemethodtosolveminimaxproblem．Applicationofbundlemethodtosolvetheproblemiscommonpractice：Byusingsubgradiemisgeneratedbyalinearfunctionformoftheobjectivefunctionofaconvexslicelinearapproximationmodel．Applicationbundlemethodtosolvetheproblemusuallywayisusingli

7、nearfunctionfromthesubgradient．Theneachiterationisbymesolutionofquadraticprogramminggetthesearchdirection．Atthesametime，usingsubgradientchoiceandbundletechnologyrestrictstoragetimesthenumberofgradient．There