袁亚湘研究员学术报告之瞎子爬山与最优化方法.ppt
从瞎子爬山到 最优化方法,中科院数学与系统科学研究院 袁亚湘 yyxlsec.cc.ac.cn http:/lsec.cc.ac.cn/yyx,爬山与优化,爬山 海拔“最”高 最优化 求“最”好的 Operations Research - Science of Better,瞎子与计算机,瞎子 知道脚底下情况， 但看不见周围的东西 计算机 给一个点x，可计算： f(x), f(x), 但对于x 附近的其他y, 不知道 f(y),瞎子爬山 vs 优化方法,瞎子和计算机谁快? 瞎子和计算机谁聪明? 瞎子会如何“看” “瞎子爬山法”呢?,最速下降法,k 使 f(xd ) 达到最小 （精确搜索） 华罗庚： 瞎子爬山法,华罗庚（19101985）,最好 + 最好 = 最好 ?,方向 (最速下降) （best dk) 步长 (精确搜索) (best k ) xk+1 = xk + k dk 是否最好 ?,最速下降法应用于 f(x,y)=100x2+ y2,Barzilai & Borwein Method,方向 (最速下降 最好方向) 步长 (上一次的精确搜索步长) 最好的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), Fletcher and Powell (1963):,Fletcher & Powell,依葫芦画瓢 都行吗？（的故事）,limx0+ 5 / x =,5,Question: limx0+ 5/x = ?,because limx0+ 8/x =,8,线性规划:单纯形法,Linear Programming (LP) Problem: min cT x A x = b x 0,单纯形方法,逐步调整N 得到解 G. Dantzig(1914-2005),线性规划的另两个奠基者,Leonid Kantorovich John von Neumann (1912-1986) (1903-1957),小人物 大人物 Hotelling(1885-1973) ： “But we all know the world is nonlinear.” Von Neumann(1903-1957): “Mr. Chairman, Mr Chairman, if the speaker doesnt mind, I would like to reply for him. The speaker titled his talk linear programming and carefully stated his axioms. If you have an application that satisfies the axioms, well use it. If it does not, then dont.”,线性规划：内点法,Interior Point Method (Karmarkar, 1984) xk 0 内点,November 19, 1984,内点法 与 罚函数,min cTx s.t. A x = b x = 0 Log-barrier function: min cTx - log (xi) s.t. A x = b KKT Newtons Step,内点法和平面几何,非线性优化问题,KKT POINTS,中国古代马鞍,Matlab plot: x2 y2,Lagrange (1736-1813),Primal dual,Libration of the moon,等价 与 等效,在数学上等价，在计算上不一定等效 - 冯康（19201993) 例子： (B+ I) d = -g , | d | = | d() | = 1/ | d() | = 1/ ,Leonhard Euler (1707-1783),由于宇宙组成是最完美也是最聪明造物主之产物，宇宙间万物都遵循某种最大或最小准则 欧拉 Für, da das Gewebe des Universums am vollkommensten und die Arbeit eines klügsten ist Schöpfers, nichts an findet im Universum statt, in dem irgendeine Richtlinie des Maximums oder des Minimums nicht erscheint,优化问题,任何存在/需要决策的问题都是优化问题 力学： （最小重量，最大载重，结构最优） 材料科学； （最小能量） 金融： （最大利润，最小风险） 生命科学： （DNA 序列, 蛋白质折叠） 信息科学： （Data Mining, 图像处理） 地学： （反问题 误差最小） 交通： （最大效益，时刻表，恢复运行）,图像存储问题,尽可能少的存贮，尽可能清晰的图像 求解 A x = b ， x Rn A Rm×n , b Rm . m n . 要求： x 尽量多的分量为零! D.L. Donoho (IEE Trans IT, 2006),哪个范数？,minimize | x | s.t. Ax = b |x|1 比 | x |2 好的多！ Compressive Sensing: | . |0,蛋白质结构问题,已知 若干原子（分子）之间的距离，如何确定它们在空间的位置？ 设 S 是一集合，求解 | xi xj |2 = dij , (i , j ) S,Sensor Localization,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,Sensor Localization,优化模型：（ Biswas & Ye, 2004),为什么要优化?,优化问题越来越多 优化问题越来越重要 优化问题越来越难 1) 大规模 2) 非线性 3) 多极值,前途是光明的，道路是曲折的 世上无难事，只要肯登登攀！ 毛泽东(1893-1976),祝福大家,优化自己的一生 !,Leonardo da Vince (1452-1519),达.芬奇与黄金分割,黄金分割法： 给出0， 1： X=0.382 Y=0.618 新区间： 0, 0.618 or 0.382, 1,全局优化,数学上不可解 随机方法（在概率意义下收敛） 广告词： 没有最好，只有更好！,迭代法 长期问题周期化,千里之行始于足下 老子,SQP Step,Maratos Effect,Sequential Programming Method fast convergence iteration |xk+sk x*| = o ( | xk x*|) Merit function does not accept new point f(xk+sk ) f( xk ) |c( xk+sk ) | |c( xk ) |,Maratos Effect 的几何表现,FLETCHER二阶校正步,二阶校正步方法,SQP 步： 二阶校正步： 新点： s = h + v 二阶步 也是 v 步,轮子不一样大的车,QUESTION： 见过左右 两边轮子尺寸不一的车吗？ 如果有，如何设计传动装置？ 大轮子转两圈， 小轮子转一圈 what happens? Null Space method: xk+1 = xk + vk + hk +v(new),
