优化方法及其应用北交大.ppt
优化方法及其应用优化方法及其应用提纲提纲l引子：引子：优化是什么？优化是什么？l几个简单优化方法介绍几个简单优化方法介绍l若干优化问题举例若干优化问题举例 1)生产、运输、调度问题生产、运输、调度问题（线性规划）（线性规划）2)压缩感知、压缩感知、Netflix问题问题（稀疏优化，（稀疏优化，L1）3)分类问题、机器学习（二次规划）分类问题、机器学习（二次规划）4)蛋白质折叠蛋白质折叠、无线定位问题（半定规划）、无线定位问题（半定规划）5)传染病模型（微分方程约束的优化）传染病模型（微分方程约束的优化）什么是优化？什么是优化？最优化最优化 在所有可能中挑选最好的在所有可能中挑选最好的任何存在决策的问题都是优化问题！任何存在决策的问题都是优化问题！The Science of Better (INFORMS )田忌赛马田忌赛马 齐威王齐威王 田忌田忌 齐威王齐威王 田忌田忌上上 A B A F中中 C D C F E D 3 :0 1 :2中国邮递员问题旅行商问题旅行商问题（1317313173点）点）点）点）优化问题到处可见优化问题到处可见l力学：（最小重量，最大载重，结构最优）l材料科学；（最小能量）l金融：（最大利润，最小风险）l生命科学：（DNA 序列,蛋白质折叠）l信息科学：（Data Mining,图像处理）l地学：（反问题 误差最小）l交通：（最大效益，时刻表，恢复运行）优化问题的数学形式 非线性规划（优化）问题非线性规划（优化）问题 minimize f(x)subject to ci(x)=0,i=1,2,me ci(x)0,i=me+1,m几个简单优化方法几个简单优化方法华罗庚（19101985）华罗庚在农村推广优选法华罗庚在大庆油田讲优选法华罗庚在矿山推广优选法华罗庚在工厂、车间黄金分割法黄金分割法0,1 上求上求 f(x)的极大值的极大值la,b 上的连续函数 f(x)是单峰的（只有 一个最大值点）,求解 max f(x)l 任取 acdb,如果 f(c)f(d),则 我们只需在 c,b 上求 max f(x)如何 选取 c,d?最优的 c,d1）maxb-c,d-a 达到最小 c d=(a+b)/2!2)除了c,d 之外还可以求若干次函数值?一次 c=1/3,d=2/3 两次 c=2/5,d=3/5?最优的 c,d一般情况：c=Fk-1/Fk+1 d=Fk/Fk+1 F0=1,F1=1,Fk+1=Fk+Fk-1 Fibonacci(1170-1250)达达.芬奇与黄金分割芬奇与黄金分割l黄金分割法：l给出0，1：l X=0.382l Y=0.618l新区间：l 0,0.618 orl 0.382,1 最速下降法最速下降法lk 使 f(xd)达到最小 （精确搜索）A.Cauchy,Comptes Rendus de LAcadmia des Sciences 25(1847)536-538 Cauchy（17891859）最速下降法收敛速度l 假定 f(x)是二次凸函数l收敛速度：最好 +最好 =最好?l 方向 (最速下降)（best dk)l 步长 (精确搜索)(best k)l xk+1=xk+k dk 是否最好?最速下降法应用于 f(x,y)=100 x2+y2Barzilai&Borwein Methodl 方向方向 (最速下降最速下降 最好方向最好方向)l 步长步长 (上一次的精确搜索步长上一次的精确搜索步长)l 最好的d +上一步上一步最好的 最好J.M.Borwein(1951-J.M.Borwein(1951-BB 方法 应用于 f(x,y)=100 x2+y2 牛顿法牛顿法l牛顿法：牛顿法：l牛顿法的特点：牛顿法的特点：1)优点：速度快（二次收敛）优点：速度快（二次收敛）2)缺点缺点:计算二阶导数计算二阶导数Newton(1643-1727)Newton(1643-1727)拟牛顿法拟牛顿法l牛顿:l拟牛顿:l如何选取 B？如何如何“拟拟”牛顿？牛顿？l拟牛顿方程：lDavidon(1959),Fletcher and Powell(1963):N.Trefethen:Who invented the great numerical algorithms?半定规划（半定规划（SDP）Semi-Definite Programming(SDP)min s.t.=b X 0 =Trace CTX 非凸问题 （松弛）凸问题 when X=xxT xTCx=内点法l(Karmarkar,1984)l xk 0lLog 罚函数方法l牛顿法中心路径 实际问题的优化建模实际问题的优化建模生产问题生产问题有m 种原材料，可生产n 种产品。如何安排生产计划使产值最多？maximize c1 x1+c2 x2+cn xn s.t.a11x1+a12 x2 +a1n xn b1 .am1x1+am2 x2+amn xn bm x1 0,xn 0 调度问题l航空（飞机调度，空乘人员调度）l轨道交通（车次安排，车头调度）l城市交通（红绿灯控制）l突发事件后 时间表的恢复 （例子：“9.11”后美国航空运输恢复）美国电网优化压缩感知压缩感知（Compressive Sensing)尽可能少的存贮，尽可能清晰的图像 求解 A x =b，x Rn A Rmn ,b Rm .m n.要求：x 尽量多的分量为零!D.L.Donoho(IEE Trans IT,2006)压缩感知压缩感知 minimize|x|0 s.t.Ax=b NP-hard!non-convex,discontinuous minimize|x|1 s.t.Ax=b convex problem,continuous压缩感知压缩感知 L1 优化优化Netflix 百万美元奖百万美元奖电影评价电影打分Netflix 问题问题从1998年10月到2005年12月 搜集数据 （请客户给电影打分）l480,189 用户l17,770 电影l100,480,507 分数（1到5）问题：如何填补没有打分的数据？矩阵完整化矩阵完整化(Matrix Completion)给出矩阵 A 中的一些元素：Aij (i,j)in S)求 A 的其他元素 (例子：DVD出租）数学问题：minimize Rank(X)s.t.Xij=Aij (i.j)in S松弛问题松弛问题 min|X|*s.t.Xij=Aij (i.j)in S where|X|*is the nuclear norm 分类问题（机器学习）分类问题（机器学习）支撑向量机（支撑向量机（VSM）蛋白质结构问题蛋白质结构问题已知 若干原子（分子）之间的距离，如何确定它们在空间的位置？蛋白质结构问题（距离几何）蛋白质结构问题（距离几何）设 S 是一集合，给出dij ,(i,j)S 求解 xi 使得：|xi xj|2=dij ,(i,j)S 无线网络定位问题无线网络定位问题Ad-hoc wireless sensor network.已知若干ak 的位置，如何利用部分距离 dij 和zik 确定所有未知点xi在空间的位置？设 S1 ,S2 是两集合，求解|xi xj|2=dij ,(i,j)S1|xi ak|2 =zik,(i,k)S2 传感定位问题传感定位问题 优化建模优化建模优化模型：（Biswas&Ye,2004)SDP（凸）松弛 x TB x -二次函数（非凸）l取 X=x xTT 则有 xTBx =-Convex on X 其中 =trace(ATB)Uncertainty Constraints Uncertainty constraints:Pr(ci(x,u)1-Bertsimas,D.,Brown,D.,and Caramanis,C.Theory and Applications of Robust Optimization SIAM Review,53(2011),pp.464-501传染病研究传染病研究在时间t1 t2,t n 得到测量数据 y1,y2,yn(d 维向量）希望找到 解 x(t):1)x(ti)近似 yi2)x(t)满足某一模型 dij 和zik 确定所有未知点xi在空间的位置？微分方程约束的优化问题向量 是优化变量Leonhard Euler(1707-1783)Leonhard Euler(1707-1783)由于宇宙组成是最完美也是由于宇宙组成是最完美也是最聪明造物主之产物，宇宙最聪明造物主之产物，宇宙间万物无不遵循某种最大或间万物无不遵循某种最大或最小准则最小准则 欧拉欧拉 Fr,da das Gewebe des Universums am vollkommensten und die Arbeit eines klgsten ist Schpfers,nichts an findet im Universum statt,in dem irgendeine Richtlinie des Maximums oder des Minimums nicht erscheint 结束语结束语优化优化 无处不在无处不在 永无止境永无止境祝愿大家 优化人生！
