《袁亚湘研究员学术报告之瞎子爬山与最优化方法》由会员分享，可在线阅读，更多相关《袁亚湘研究员学术报告之瞎子爬山与最优化方法（61页珍藏版）》请在金锄头文库上搜索。
1、从瞎子爬山到 最优化方法中科院数学与系统科学研究院 袁亚湘 http:/ 海拔“最”高l最优化 求“最”好的lOperations Research - Science of Better瞎子与计算机l瞎子 知道脚底下情况，但看不见周围的东西l计算机 给一个点x，可计算： f(x), f(x), 但对于x 附近的其他y, 不知道 f(y)瞎子爬山 vs 优化方法l瞎子和计算机谁快?l瞎子和计算机谁聪明?l瞎子会如何“看” “瞎子爬山法”呢?最速下降法lk 使 f(xd ) 达到最小（精确搜索）华罗庚： 瞎子爬山法华罗庚（19101985）最好 + 最好 = 最好 ?l 方向 (最速下降) （b
2、est dk)l 步长 (精确搜索) (best k )l xk+1 = xk + k dk 是否最好 ?最速下降法应用于 f(x,y)=100x2+ y2Barzilai & Borwein Methodl 方向 (最速下降 最好方向)l 步长 (上一次的精确搜索步长)l 最好的d + 上一步最好的 最好BB 方法 应用于 f(x,y)=100x2+ y2信赖域方法非线性最小二乘问题最小二乘问题l 超定方程组求解l 数值模拟，曲线拟 合l反问题高斯牛顿法l xk+1 = xk + dk , 如何求 dk ？lA(x) 是 F(x) 的 JACOBI 阵J. C. F. Gauss (1777
3、-1855)I. Newton(1642- 1727) L-M步的最优性l设 dk 是 Levenberg-Marquardt 步:则它也是如下问题的解信赖域方法l信赖域方法基本思想1) 局部区域2) 逼近模型3) 调节模型和区域l孙悟空的信赖域 相似 （近似） 计算的技巧 复杂问题简单化 牛顿法l牛顿法：l牛顿法的特点：1) 优点：速度快（二次收敛）2) 缺点: 计算二阶导数拟牛顿法l牛顿:l拟牛顿:l如何选取 B？如何“拟”牛顿？l拟牛顿方程：lDavidon(1959), Fletcher and Powell (1963):Fletcher & Powell依葫芦画瓢 都行吗？（的故事
4、）limx0+ 5 / x =5Question: limx0+ 5/x = ? because limx0+ 8/x = 8线性规划:单纯形法lLinear Programming (LP) Problem:min cT xA x = bx 0单纯形方法逐步调整N 得到解 G. Dantzig(1914- 2005)线性规划的另两个奠基者Leonid Kantorovich John von Neumann (1912-1986) (1903-1957)小人物 大人物lHotelling(1885-1973) ：“But we all know the world is nonlinear.
5、” l 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.”线性规划：内点法lIn
6、terior Point Method (Karmarkar, 1984)l xk 0 内点 November 19, 1984内点法 与 罚函数min cTx s.t. A x = bx = 0 Log-barrier function: min cTx - log (xi)s.t. A x = bKKT Newtons Step内点法和平面几何非线性优化问题KKT POINTS中国古代马鞍lMatlab plot:x2 y2Lagrange (1736-1813)lPrimalldualLibration of the moon等价 与 等效l在数学上等价，在计算上不一定等效- 冯康（19201993)例子：(B+ I) d = -g , | d | f( xk )|c( xk+sk ) | |c( xk ) |Maratos Effect 的几何表现FLETCHER二阶校正步二阶校正步方法lSQP 步：l二阶校正步：l新点：s = h + v 二阶步 也是 v 步轮子不一样大的车QUESTION： 见过左右两边轮子尺寸不一的车吗？ 如果有，如何设计传动装置？大轮子转两圈， 小轮子转一圈 what happens?Null Space method:xk+1 = xk + vk + hk +v(new)
