袁亚湘-优化方法,从瞎子爬山谈起

优化方法—从瞎子爬山谈起中科院数学与系统科学研究院袁亚湘[e-mail]~yyx人人网：袁亚湘引子：瞎子爬山爬山与优化爬山－－－海拔“最”高最优化－－－求“最”好的OperationsResearch--ScienceofBetter瞎子与计算机瞎子－－－知道脚底下情况，但看不见周围的东西计算机－－－给一个点x，可计算：f(x),∂f(x),……但对于x附近的其他y,不知道f(y)瞎子爬山vs优化方法瞎子和计算机谁快?瞎子和计算机谁聪明?瞎子会如何“看”“瞎子爬山法”呢?优化方法的特征基于极小(minf(x))基于KKT条件()迭代迭代－计算的基本千里之行始于足下－－－老子几个经典优化方法黄金分割法最速下降法共轭梯度法牛顿法与拟牛顿法高斯牛顿法与信赖域方法单纯形法与内点法交替方向法黄金分割法黄金分割法华罗庚（1910－1985）华罗庚在农村推广优选法华罗庚在大庆油田讲优选法华罗庚在矿山推广优选法华罗庚在工厂、车间Maxf(x)[a,b]上的连续函数f(x)是单峰的（只有一个最大值点）,求解maxf(x)任取acdb,如果f(c)f(d),则我们只需在[c,b]上求maxf(x)如何选取c,d?最优的c,d1）max[b-c,d-a]达到最小c≈d=(a+b)/2!2)Repeattheprocedure?Oncec=1/3,d=2/3Twicec=2/5,d=3/5?菲波那契级数（兔子繁殖问题）一般的c,dF0=1,F1=1,Fk+1=Fk+Fk-1Generalcasec=Fk-1/Fk+1d=Fk/Fk+1Fibonacci(1170-1250)达.芬奇与黄金分割黄金分割法：给出[0，1]：X=0.382Y=0.618新区间：[0,0.618]or[0.382,1]LeonardodaVince(1452-1519)Euclid(约325BC—265BC)extremeandmeanratio最速下降法最速下降法αk使f(x＋αd)达到最小（精确搜索）A.Cauchy,ComptesRendusdeL’AcadmiadesSciences25(1847)536-538Cauchy（1789－1859）最速下降法收敛速度假定f(x)是二次凸函数收敛速度：最好+最好=最好???方向(最速下降)（bestdk)步长(精确搜索)(bestαk)xk+1=xk+αkdk是否最好????最速下降法应用于f(x,y)=100x2+y2最速下降法的启示最好方向+最好步长≠最好的方法推论：班上最好的女生不应该嫁给班上最好的男生！Barzilai&BorweinMethod方向(最速下降－最好方向)步长(上一次的精确搜索步长)最好的d+上一步最好的α最好J.M.Borwein(1951-BB方法应用于f(x,y)=100x2+y2BB方法的启示最好方向+上一次最好步长＝最好推论：班上最好的女生应该嫁给高年级最好的男生！共轭梯度法共轭梯度法αk使f(x＋αd)达到最小（精确搜索）如何选取dk?共轭梯度法前后两次的方向d相互共轭共轭梯度法基本思想考虑f(x)=(1/2)xTAx–bTx共轭方向d1,d2,…,dn一个n维问题转化为n个一维问题共轭梯度法的实现著名的β选取:Hestenes(1906-1991)Stiefel(1909-1978)新的共轭梯度法Dai-Yuan(1999)MoremethodsbyHager-Zhang,etc..牛顿法与拟牛顿法相似（近似）－－计算的技巧－－复杂问题简单化牛顿法：切线代替曲线Newton(1643-1727)牛顿法求f(x)=0的根牛顿法性质迭代公式：优缺点：1)优点：速度快（二次收敛）2)缺点:计算量大（需要计算二阶导数）拟牛顿法牛顿:拟牛顿:如何选取B？如何“拟”牛顿？拟牛顿方程：Davidon(1959),FletcherandPowell(1963):Fletcher(1939-)Powell(1936-)N.Trefethen:Whoinventedthegreatnumericalalgorithms?依葫芦画瓢–都行吗？（∞的故事）limx0+5/x=5Question:limx0+5/x=?becauselimx0+8/x=8高斯牛顿法与信赖域法非线性最小二乘问题最小二乘问题超定方程组求解数值模拟，曲线拟合反问题高斯－牛顿法xk+1=xk+dk,如何求dk？A(x)是F(x)的JACOBI阵J.C.F.Gauss(1777-1855)I.Newton(1642-1727)Levenberg-Marquardt方法当A坏条件时高斯－牛顿步很可能不好。Levenberg(1944),Marquardt(1963)提出：L-M步的最优性设dk是Levenberg-Marquardt步:则它也是如下问题的解信赖域方法信赖域方法基本思想1)局部区域2)逼近模型3)调节模型和区域孙悟空的信赖域单纯形法与内点法线性规划:单纯形法LinearProgramming(LP)Problem:mincTxAx=bx≥0单纯形方法逐步调整N得到解G.Dantzig(1914-2005)单纯形方法的计算列表法c0Ab---------------------------------------------x=(xBxN)顶点：(xB0)0cN－fIANbxBxN线性规划的另两个奠基者LeonidKantorovichJohnvonNeumann(1912-1986)(1903-1957)小人物大人物Hotelling(1885-1973)：“Butweallknowtheworldisnonlinear.”VonNeumann(1903-1957):“Mr.Chairman,MrChairman,ifthespeakerdoesn’tmind,Iwouldliketoreplyforhim.Thespeakertitledhistalk`linearprogramming’andcarefullystatedhisaxioms.Ifyouhaveanapplicationthatsatisfiestheaxioms,welluseit.Ifitdoesnot,thendon’t.”线性规划：内点法InteriorPointMethod(Karmarkar,1984)xk0内点N.Karmarkar(1957-)November19,1984内点法与罚函数mincTxs.t.Ax=bx=0Log-barrierfunction:mincTx-∑log(xi)s.t.Ax=bKKTNewton’sStep内点法和平面几何内点法与SDPSemi-DefiniteProgramming(SDP)minC,Xs.t.A,X=bX=0C,X=TraceCTXwhenX=xxTC,X=xTCx交替方向法交替方向方法minf(x)x=(x1,…,xn)固定xj(j≠i),对xi进行优化例子：Gauss-Seidel方法求解Ax=b交替方向方法--L1优化min||x||1s.t.Ax=b罚函数方法：交替方向方法--L1优化对于:min||Ay-b||2可以用梯度法下降；对于min||x||1|x+i|=|xi|-δ(shrinkageoperator)Nowthissupremewisdom,unitedtogoodnessthatisnolessinfinite,cannotbuthavechosenthebest.Forasalesserevilisakindofgood,evensoalessergoodisakindofevilifitstandsinthewayofagreatergood;andthewouldbesomethingtocorrectintheactionsofGodifitwerepossibletothebetter.Asinmathematics,whenthereisnomaximumnorminimum,inshortnothingdistinguished,everythingisdoneequally,orwhenthatisnotnothingatallisdone:soitmaybesaidlikewiseinrespectofperfectwisdom,whichisnolessorderlythanmathematics,thatiftherewerenotthebest(optimum)amongallpossibleworlds,Godwouldnothaveproducedany.----------Leibniz(1646-1716)祝福大家优化自己的一生!