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

从瞎子爬山到

最优化方法中科院数学与系统科学研究院爬山与优化爬山－－－海拔“最”高最优化－－－求“最”好的OperationsResearch--ScienceofBetter瞎子与计算机瞎子－－－知道脚底下情况，但看不见周围的东西计算机－－－给一个点x，可计算：f(x),∂f(x),……但对于x附近的其他y,不知道f(y)瞎子爬山vs优化方法瞎子和计算机谁快?瞎子和计算机谁聪明?瞎子会如何“看”“瞎子爬山法”呢?最速下降法αk使f(x＋αd)达到最小（精确搜索）华罗庚：瞎子爬山法华罗庚（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-1727)L-M步的最优性设dk是Levenberg-Marquardt步:则它也是如下问题的解信赖域方法信赖域方法基本思想1)局部区域2)逼近模型3)调节模型和区域孙悟空的信赖域相似（近似）－－计算的技巧－－复杂问题简单化

牛顿法牛顿法：牛顿法的特点：1)优点：速度快（二次收敛）2)缺点:计算二阶导数拟牛顿法牛顿:拟牛顿:如何选取B？

如何“拟”牛顿？拟牛顿方程：Davidon(1959),FletcherandPowell(1963):

Fletcher&Powell依葫芦画瓢–都行吗？（∞的故事）limx0+

5/x=5Question:limx0+5/x=?

becauselimx0+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,Iwouldliketoreplyforhim.Thespeakertitledhistalk`linearprogramming’andcarefullystatedhisaxioms.Ifyouhaveanapplicationthatsatisfiestheaxioms,welluseit.Ifitdoesnot,thendon’t.”线性规划：内点法InteriorPointMethod(Karmarkar,1984)xk>0内点

November19,1984内点法与罚函数mincTxs.t.Ax=b

x>=0

Log-barrierfunction:mincTx-∑log(xi)s.t.Ax=bKKTNewton’sStep内点法和平面几何非线性优化问题KKTPOINTS中国古代马鞍Matlabplot:x^2–y^2Lagrange(1736-1813)PrimaldualLibrationofthemoon等价与等效在数学上等价，在计算上不一定等效-----------冯康（1920—1993)

例子：(B+λI)d=-g,||d||<=Δ||d(λ)||=Δ1/||d(λ)||=1/ΔLeonhardEuler(1707-1783)

由于宇宙组成是最完美也是最聪明造物主之产物，宇宙间万物都遵循某种最大或最小准则———欧拉Für,dadasGewebedesUniversumsamvollkommenstenunddieArbeiteinesklügstenistSchöpfers,nichtsanfindetimUniversumstatt,indemirgendeineRichtliniedesMaximumsoderdesMinimumsnichterscheint

优化问题任何存在/需要决策的问题都是优化问题力学：（最小重量，最大载重，结构最优）材料科学；（最小能量）金融：（最大利润，最小风险）生命科学：（DNA序列,蛋白质折叠）信息科学：（DataMining,图像处理）地学：（反问题－－误差最小）交通：（最大效益，时刻表，恢复运行）图像存储问题尽可能少的存贮，尽可能清晰的图像求解Ax=b，x∈Rn

A∈Rm×n,b∈Rm.m<<n.要求：x尽量多的分量为零!D.L.Donoho(IEETransIT,2006)哪个范数？minimize||x||s.t.Ax=b||x||1比||x||2好的多！CompressiveSensing:||.||0蛋白质结构问题已知若干原子（分子）之间的距离，如何确定它们在空间的位置？设S是一集合，求解||xi–xj||2=dij,(i,j)∈SSensorLocalizationAd-hocwirelesssensornetwork.已知若干ak的位置，如何利用部分距离dij和zik确定所有未知点xi在空间的位置？设S1,

S2是两集合，求解||xi–xj||2=dij,(i,j)∈S1||xi–ak||2=zik,(i,k)∈S2SensorLocalization优化模型：（Biswas&Ye,2004)为什么要优化?优化问题越来越多优化问题越来越重要优化问题越来越难1)大规模2)非线性3)多极值前途是光明的，道路是曲折的世上无难事，只要肯登登攀！毛泽东(1893-1976)祝福大家优化自己的一生!LeonardodaVince

(1452-1519)达.芬奇与黄金分割黄金分割法：给出[0，1]：X=0.382Y=0.618新区间：[0,0.618]or[0.382,1]全局优化数学上不可解随机方法（在概率意义下收敛）广告词：没有最好，只有更好！迭代法－－长期问题周期化千里之行始于足下－－－老子SQPStepMaratosEffectSequentialProgrammingMethodfastconvergenceiteration||xk+sk–x*||=o(||xk–x*||)Meritfunctiondoesnotacceptnewpointf(xk+sk)>f(xk)||c(xk+sk)||>||c(xk)||MaratosEffect的几何表现FLETCHER二阶校正步二阶校正步方法SQP步：二阶校正步：新点：