优化方法及其应用北交大

《优化方法及其应用北交大》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、优化方法及其应用中国科学院数学与系统科学研究院袁亚湘yyx@lsec.cc.ac.cnhttp://lsec.cc.ac.cn/~yyx人人网：袁亚湘提纲引子：优化是什么？几个简单优化方法介绍若干优化问题举例1)生产、运输、调度问题（线性规划）2)压缩感知、Netflix问题（稀疏优化，L1）3)分类问题、机器学习　（二次规划）4)蛋白质折叠、无线定位问题（半定规划）5)传染病模型（微分方程约束的优化）什么是优化？最优化在所有可能中挑选最好的任何存在决策的问题都是优化问题！TheScienceofBetter(

2、INFORMS)田忌赛马齐威王田忌齐威王田忌上A>BA>F中C>DCFE

3、0,i=me+1,…,m几个简单优化方法华罗庚（1910－1985）华罗庚在农村推广优选法华罗庚在大庆油田讲优选法华罗庚在矿山推广优选法华罗庚在工厂、车间黄金分割法[0,1]上求f(x)的极大值[a,b]上的连续函数f(x)是单峰的（只有一个最大值点）,求解maxf(x)任取a

4、次c=2/5,d=3/5?最优的c,d一般情况：c=Fk-1/Fk+1d=Fk/Fk+1F0=1,F1=1,Fk+1=Fk+Fk-1Fibonacci(1170-1250)达.芬奇与黄金分割黄金分割法：给出[0，1]：X=0.382Y=0.618新区间：[0,0.618]or[0.382,1]最速下降法αk使f(x＋αd)达到最小（精确搜索）A.Cauchy,ComptesRendusdeL’AcadmiadesSciences25(1847)536-538Cauchy（1789－1859）最速下降法收敛速度

5、假定f(x)是二次凸函数收敛速度：最好+最好=最好???方向(最速下降)（bestdk)步长(精确搜索)(bestαk)xk+1=xk+αkdk是否最好????最速下降法应用于f(x,y)=100x2+y2Barzilai&BorweinMethod方向(最速下降－最好方向)步长(上一次的精确搜索步长)最好的d+上一步最好的α最好J.M.Borwein(1951-BB方法应用于f(x,y)=100x2+y2牛顿法牛顿法：牛顿法的特点：1)优点：速度快（二次收敛）2)缺点:计算二阶导数Newton(1643-1

6、727)拟牛顿法牛顿:拟牛顿:如何选取B？如何“拟”牛顿？拟牛顿方程：Davidon(1959),FletcherandPowell(1963):N.Trefethen:Whoinventedthegreatnumericalalgorithms?半定规划（SDP）Semi-DefiniteProgramming(SDP)mins.t.=bX≥0=TraceCTX非凸问题（松弛）凸问题whenX=xxTxTCx=内点法(Karmarkar,1984)xk>0Log罚

7、函数方法牛顿法中心路径实际问题的优化建模生产问题有m种原材料，可生产n种产品。如何安排生产计划使产值最多？maximizec1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn≤b1…….am1x1+am2x2+…+amnxn≤bmx1≥0,…xn≥0调度问题航空（飞机调度，空乘人员调度）轨道交通（车次安排，车头调度）城市交通（红绿灯控制）突发事件后时间表的恢复（例子：“9.11”后美国航空运输恢复）美国电网优化压缩感知（CompressiveSensing)尽可能少的存贮，尽可能清晰的

8、图像求解Ax=b，x∈RnA∈Rm×n,b∈Rm.m<

9、

10、x

11、

12、0s.t.Ax=bNP-hard!non-convex,discontinuousminimize

13、

14、x

15、

16、1s.t.Ax=bconvexproblem,continuous压缩感知——L1优化Netflix百万