优化方法及其应用北交大课件

优化方法及其应用数学与系统科学研究院人人网：袁亚湘提纲引子：优化是什么？几个简单优化方法介绍若干优化问题举例

1)生产、运输、调度问题（线性规划）2)压缩感知、Netflix问题（稀疏优化，L1）

3)分类问题、机器学习（二次规划）

4)蛋白质折叠

、无线定位问题（半定规划）5)传染病模型（微分方程约束的优化）什么是优化？田忌赛马

齐威王田忌齐威王田忌上A>BA>F中C>DC<B下E>FE<D3:01:2中国邮递员问题旅行商问题

（13173点）优化问题的数学形式

非线性规划（优化）问题

minimizef(x)subjecttoci(x)=0,i=1,2,…,me

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

任取a<c<d<b,如果f(c)<f(d),则我们只需在[c,b]上求maxf(x)

如何选取c,d?最优的c,d1）max[b-c,d-a]达到最小

c≈d=(a+b)/2!2)除了c,d之外还可以求若干次函数值?

一次c=1/3,d=2/3

两次c=2/5,d=3/5?

达.芬奇与黄金分割黄金分割法：给出[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)是二次凸函数收敛速度：

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

方向

(最速下降－最好方向)

步长

(上一次的精确搜索步长)

最好的d+上一步最好的α

最好J.M.Borwein(1951-

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

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

N.Trefethen:Whoinventedthegreatnumericalalgorithms?半定规划（SDP）Semi-DefiniteProgramming(SDP)min<C,X>s.t.<A,X>=b

X≥0

<C,X>=TraceCTX

非凸问题（松弛）凸问题whenX=xxT

xTCx=<C,X>内点法(Karmarkar,1984)xk>0Log罚函数方法牛顿法中心路径

实际问题的优化建模生产问题有m种原材料，可生产n种产品。如何安排生产计划使产值最多？

maximizec1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn

≤b1…….am1x1+am2x2+…+amnxn≤bmx1

≥0,…xn≥0

调度问题航空（飞机调度，空乘人员调度）轨道交通（车次安排，车头调度）城市交通（红绿灯控制）突发事件后时间表的恢复（例子：“9.11”后美国航空运输恢复）美国电网优化压缩感知（CompressiveSensing)尽可能少的存贮，尽可能清晰的图像求解

Ax=b，x∈Rn

A∈Rm×n,b∈Rm.m<<n.要求：x尽量多的分量为零!D.L.Donoho(IEETransIT,2006)压缩感知minimize||x||0s.t.Ax=bNP-hard!non-convex,discontinuousminimize||x||1s.t.Ax=bconvexproblem,continuous压缩感知——

L1优化Netflix百万美元奖电影评价电影打分Netflix问题从1998年10月到2005年12月搜集数据（请客户给电影打分）480,189用户17,770电影100,480,507分数（1到5）问题：如何填补没有打分的数据？矩阵完整化(MatrixCompletion)

给出矩阵A中的一些元素：

Aij

((i,j)inS)

求A的其他元素(例子：DVD出租）

数学问题：

minimizeRank(X)s.t.Xij=Aij(i.j)inS松弛问题min||X||*s.t.Xij=Aij(i.j)inS

where||X||*isthenuclearnorm分类问题（机器学习）支撑向量机（VSM）蛋白质结构问题已知若干原子（分子）之间的距离，如何确定它们在空间的位置？蛋白质结构问题（距离几何）

设S是一集合，给出dij,(i,j)∈S

求解xi

使得：

||xi–xj||2=dij,(i,j)∈S无线网络定位问题Ad-hocwirelesssensornetwork.已知若干ak的位置，如何利用部分距离

dij和zik

确定所有未知点xi在空间的位置？设S1,

S2是两集合，求解

||xi–xj||2=dij,(i,j)∈S1||xi–ak||2=zik,(i,k)∈S2传感定位问题－优化建模优化模型：（Biswas&Ye,2004)SDP（凸）松弛xTBx---二次函数（非凸）取X=xxTT则有xTBx=<B,X>---ConvexonX

其中<A,B>=trace(ATB)UncertaintyConstraintsUncertaintyconstraints:Pr(ci(x,u)<0)>1-εBertsimas,D.,Brown,D.,andCaramanis,C.TheoryandApplicationsofRobustOptimizationSIAMReview,53(2011),pp.464-501传染病研究在时间t1t2,…tn

得到测量数据

y1,y2,…yn(d维向量）希望找到解x(t):x(ti)近似yix(t)满足某一模型

dij和zik

确定所有未知点xi在空间的位置？

微分方程约束的优化问题向量β是优化变量LeonhardEuler(1707-1783)

由于宇宙组成是最完美也是最聪明造物主之产物，宇宙间万物无不遵循某种最大或最小准则

———欧拉

Für,dadasGewebedesUnive