最优化点滴谈

《最优化点滴谈》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、最优化点滴谈戴彧虹哈尔滨，2009年8月9日引子“生命不仅可以用年月计算，有时事件也是最好的日历。”（狄斯累利）几项经典工作几项最新工作广阔应用前景一些应用体会演讲提纲经典工作之一:DFP拟牛顿法Davidon(1959)Fletcher-Powell(1963)NickTrefethen:“oneofthe13classicalworksinNumericalAnalysis”Newton’sMethodNewton(1669),Raphson(1690)Simpson(1740)Arnol’d:TaylorserieswereNewton’s“mainmathematicaldiscov

2、ery”UnConstrainedOptimizationNewton’sMethod:Quasi-NewtonMethod:Quasi-NewtonMethod(DFP)Quasi-NewtonMethod(BFGS)经典工作之二:共轭梯度法Hestenes-Stiefel(1952)NickTrefethen:“oneofthe13classicalworksinNumericalAnalysis”BasicDescriptionswhereConjugacyPropertyDenoteThenwehaveExtensionstoNonlinearFunctions(Fletcher-

3、Reeves1964)Problem:minf(x)(1)Performalinesearchtoobtainthestepsize(2)Considermoreefficientconjugategradientparameter(P-R-P)经典工作之三:线性规划[线性规划实例]家具公司生产桌子和椅子，用于生产的劳动力共计450个工时，木材4立方米。每张桌子需15个工时，0.2立方米木材，售价80元；每把椅子需10个工时，0.05立方米木材，售价45元。问如何安排最优生产？1939年康托洛维奇《生产组织和计划中的数学方法》1951年美籍荷裔库普曼斯《生产与配置的活动分析》1975年康托洛

4、维奇与库普曼斯因“最优资源配置理论的贡献”荣获诺贝尔经济学奖L.V.Kantorovich(1912-1986)1947年美国数学家丹兹格SimplexMethodFatherofLinearProgrammingLinearProgrammingandExtensions1984年，在美国工作的印度裔数学家卡玛卡提出可以有效求解实际线性规划问题的多项式时间算法---Karmarkar算法G.Dantzig(1914–2005)经典工作之四:二次规划AnExample:PortfolioOptimizationnpossibleinvestimentsCovariancesAportfoli

5、o(byputtingafractionx_ioftheavailablefundsintoinvestimenti)TheexpectedreturnThevarianceofthetotalportfolioMarkowitz(1952)"PortfolioSelection“TheJournalofFinanceH.M.Markowitz:NobelMemorialPrizeinEconomicSciences1990.HarryM.Markowitz(Borned1927)最新工作之一:BB梯度法Barzilai-Borwein(1988)SteepestDescentMethod

6、(Cauchy1847)Zigzags:Barzilai-BorweinMethod最新工作之二:Powell直接法M.J.D.Powell(2000)"UOBYQA:unconstrainedoptimizationbyquadraticapproximation"Nelder-MeadMethod(单纯形算法)Himmelblaufunction:f(x,y)=(x^2+y-11)^2+(x+y^2-7)^2Powell:UOBYQAAteveryiteration,decidempointsandmeasuretheirfunctionvaluesConstructaquadrati

7、capproximationSolvethetrustregionproblemNewMethodsforStochasticApproximationminf(x)+errorSomeclassicalmethodsaimtotakeastepsizeof1/kalongthenoisygradientdirectionBasicIdeasofourNewmethods:(1)Useaquadraticm