袁亚湘研究员学术报告之瞎子爬山与最优化方法

《袁亚湘研究员学术报告之瞎子爬山与最优化方法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、从瞎子爬山到最优化方法中科院数学与系统科学研究院袁亚湘yyx@lsec.cc.ac.cnhttp://lsec.cc.ac.cn/~yyx爬山与优化爬山　－－－　　海拔“最”高最优化－－－求“最”好的OperationsResearch--ScienceofBetter瞎子与计算机瞎子　－－－　知道脚底下情况，但看不见周围的东西计算机－－－给一个点x，可计算：f(x),∂f(x),……但对于x附近的其他y,不知道f(y)瞎子爬山vs优化方法瞎子和计算机谁快?瞎子和计算机谁聪明?瞎子会如何“看”“瞎子爬山法”呢?最速下降法αk使f(x＋αd)达到最小（精确搜索）华罗庚：瞎子爬山法华罗庚（

2、1910－1985）最好+最好=最好???方向(最速下降)（bestdk)步长(精确搜索)(bestαk)xk+1=xk+αkdk是否最好????最速下降法应用于f(x,y)=100x2+y2Barzilai&BorweinMethod方向(最速下降－最好方向)步长(上一次的精确搜索步长)最好的d+上一步最好的α最好BB方法应用于f(x,y)=100x2+y2信赖域方法非线性最小二乘问题最小二乘问题超定方程组求解数值模拟，曲线拟合反问题高斯－牛顿法xk+1=xk+dk,如何求dk？A(x)是F(x)的JACOBI阵J.C.F.Gauss(1777-1855)I.Newton(1642

3、-1727)L-M步的最优性设dk是Levenberg-Marquardt步:则它也是如下问题的解信赖域方法信赖域方法基本思想1)局部区域2)逼近模型3)调节模型和区域孙悟空的信赖域相似（近似）－－计算的技巧－－复杂问题简单化牛顿法牛顿法：牛顿法的特点：1)优点：速度快（二次收敛）2)缺点:计算二阶导数拟牛顿法牛顿:拟牛顿:如何选取B？如何“拟”牛顿？拟牛顿方程：Davidon(1959),FletcherandPowell(1963):Fletcher&Powell依葫芦画瓢–都行吗？（∞的故事）limx0+5/x=5Question:limx0+5/x=?becauselimx

4、0+8/x=8线性规划:单纯形法LinearProgramming(LP)Problem:mincTxAx=bx≥0单纯形方法逐步调整N得到解G.Dantzig(1914-2005)线性规划的另两个奠基者LeonidKantorovichJohnvonNeumann(1912-1986)(1903-1957)小人物大人物Hotelling(1885-1973)：“Butweallknowtheworldisnonlinear.”VonNeumann(1903-1957):“Mr.Chairman,MrChairman,ifthespeakerdoesn’tmind,Iwould

5、liketoreplyforhim.Thespeakertitledhistalk`linearprogramming’andcarefullystatedhisaxioms.Ifyouhaveanapplicationthatsatisfiestheaxioms,welluseit.Ifitdoesnot,thendon’t.”线性规划：内点法InteriorPointMethod(Karmarkar,1984)xk>0内点November19,1984内点法与罚函数mincTxs.t.Ax=bx>=0Log-barrierfunction:mincTx-∑log(xi)s.t.

6、Ax=bKKTNewton’sStep内点法和平面几何非线性优化问题KKTPOINTS中国古代马鞍Matlabplot:x^2–y^2Lagrange(1736-1813)PrimaldualLibrationofthemoon等价与等效在数学上等价，在计算上不一定等效-----------冯康（1920—1993)例子：(B+λI)d=-g,

7、

8、d

9、

10、<=Δ

11、

12、d(λ)

13、

14、=Δ1/

15、

16、d(λ)

17、

18、=1/ΔLeonhardEuler(1707-1783)由于宇宙组成是最完美也是最聪明造物主之产物，宇宙间万物都遵循某种最大或最小准则———欧拉Für,dadasGewebedesUn

19、iversumsamvollkommenstenunddieArbeiteinesklügstenistSchöpfers,nichtsanfindetimUniversumstatt,indemirgendeineRichtliniedesMaximumsoderdesMinimumsnichterscheint优化问题任何存在/需要决策的问题都是优化问题力学：（最小重量，最大载重，结构最优）材料科学；（最小能量）金融：（最大利润，最小风险）