优化方法及其应用北交大.pptxVIP

优化方法及其应用中国科学院数学与系统科学研究院袁亚湘/~yyx人人网：袁亚湘

提纲引子：优化是什么？几个简单优化方法介绍若干优化问题举例1)生产、运输、调度问题（线性规划）2)压缩感知、Netflix问题（稀疏优化，L1）3)分类问题、机器学习（二次规划）4)蛋白质折叠、无线定位问题（半定规划）5)传染病模型（微分方程约束的优化）

什么是优化？

最优化

在所有可能中挑选最好的任何存在决策的问题都是优化问题！TheScienceofBetter(INFORMS)

田忌赛马”1齐威王田忌齐威王田忌2上ABAF3中CDCB4下EFED5:01:2

中国邮递员问题

旅行商问题

（13173点）

力学：（最小重量，最大载重，结构最优）01材料科学；（最小能量）02金融：（最大利润，最小风险）03生命科学：（DNA序列,蛋白质折叠）04信息科学：（DataMining,图像处理）05地学：（反问题－－误差最小）06交通：（最大效益，时刻表，恢复运行）07优化问题到处可见

3241非线性规划（优化）问题ci(x)≥0,i=me+1,…,mminimizef(x)subjecttoci(x)=0,i=1,2,…,me优化问题的数学形式

几个简单优化方法

华罗庚（1910－1985）

华罗庚在农村推广优选法

华罗庚在大庆油田讲优选法

华罗庚在矿山推广优选法

华罗庚在工厂、车间

黄金分割法

一个最大值点）,求解maxf(x)[a,b]上的连续函数f(x)是单峰的（只有我们只需在[c,b]上求maxf(x)如何选取c,d?任取acdb,如果f(c)f(d),则[0,1]上求f(x)的极大值

?c≈d=(a+b)/2!max[b-c,d-a]达到最小一次?c=1/3,d=2/3两次?c=2/5,d=3/5?除了c,d之外还可以求若干次函数值?最优的c,d

一般情况：最优的c,d1c=Fk-1/Fk+1d=Fk/Fk+12F0=1,F1=1,3Fk+1=Fk+Fk-14Fibonacci(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）

最速下降法收敛速度假定f(x)是二次凸函数收敛速度：

最好+最好=最好???方向(最速下降)（bestdk)步长(精确有哪些信誉好的足球投注网站)(bestαk)xk+1=xk+αkdk是否最好????

最速下降法应用于f(x,y)=100x2+y2

BarzilaiBorweinMethod方向(最速下降－最好方向)步长(上一次的精确有哪些信誉好的足球投注网站步长)最好的d+上一步最好的α?最好J.M.Borwein(1951-

BB方法应用于f(x,y)=100x2+y2

牛顿法牛顿法：牛顿法的特点：优点：速度快（二次收敛）缺点:计算二阶导数Newton(1643-1727)

拟牛顿法牛顿:拟牛顿:如何选取B？

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

N.Trefethen:Whoinventedthegreatnumericalalgorithms?

whenX=xxT?xTCx=C,X非凸问题（松弛）?