最优化点滴谈.ppt

1、最优化点滴谈,戴彧虹 哈尔滨，2009年8月9日,引子,“生命不仅可以用年月计算， 有时事件也是最好的日历。” （狄斯累利）,几项经典工作 几项最新工作 广阔应用前景 一些应用体会,演讲提纲,经典工作之一: DFP拟牛顿法,Davidon(1959) Fletcher-Powell (1963) Nick Trefethen: “one of the 13 classical works in Numerical Analysis”,Newtons Method,Newton (1669), Raphson(1690) Simpson(1740) Arnold: Taylor series w

2、ere Newtons “main mathematical discovery”,UnConstrained Optimization,Newtons Method: Quasi-Newton Method:,Quasi-Newton Method (DFP),Quasi-Newton Method (BFGS),经典工作之二: 共轭梯度法,Hestenes-Stiefel (1952) Nick Trefethen: “one of the 13 classical works in Numerical Analysis”,Basic Descriptions,where,Conjugac

3、y Property,Denote Then we have,Extensions to Nonlinear Functions(Fletcher-Reeves 1964),Problem: min f(x) (1) Perform a line search to obtain the stepsize (2) Consider more efficient conjugate gradient parameter (P-R-P),经典工作之三: 线性规划,线性规划实例 家具公司生产桌子和椅子，用于生产的劳动力共计450个工时，木材4立方米。每张桌子需15个工时，0.2立方米木材，售价80元

4、；每把椅子需10个工时，0.05立方米木材，售价45元。问如何安排最优生产？,1939年 康托洛维奇 生产组织和计划中的数学方法 1951年 美籍荷裔 库普曼斯 生产与配置的活动分析 1975年康托洛维奇与库普曼斯因“最优资源配置理论的贡献”荣获诺贝尔经济学奖,L.V.Kantorovich (1912-1986),1947年 美国数学家 丹兹格 Simplex Method Father of Linear Programming Linear Programming and Extensions 1984年，在美国工作的印度裔数学家卡玛卡提出可以有效求解实际线性规划问题的多项式时间算法-K

5、armarkar算法,G. Dantzig (19142005),经典工作之四: 二次规划,An Example: Portfolio Optimization,n possible investiments Covariances,A portfolio (by putting a fraction x_i of the available funds into investiment i) The expected return The variance of the total portfolio,Markowitz (1952) Portfolio Selection“ The Jou

6、rnal of Finance H.M.Markowitz: Nobel Memorial Prize in Economic Sciences 1990.,Harry M. Markowitz (Borned 1927),最新工作之一: BB梯度法,Barzilai-Borwein (1988),Steepest Descent Method(Cauchy 1847),Zigzags:,Barzilai-Borwein Method,最新工作之二: Powell直接法,M.J.D. Powell (2000) UOBYQA: unconstrained optimization by qua

7、dratic approximation,Nelder-Mead Method(单纯形算法),Himmelblau function: f(x,y) = (x2+y-11)2+(x+y2-7)2,Powell: UOBYQA,At every iteration, decide m points and measure their function values Construct a quadratic approximation Solve the trust region problem,New Methods for Stochastic Approximation,min f(x)+

8、error Some classical methods aim to take a stepsize of 1/k along the noisy gradient direction Basic Ideas of our New methods: (1) Use a quadratic model for f(x); (2) Solve a least squares problem.,广阔应用前景（一）,TD-SCDMA无线资源,广阔应用前景（二）,最优化在现代通信网络中的应用,广阔应用前景（三）, 生物技术中的优化问题,更多,航空航天 交通运输 智能电网 物流管理 金融优化 国防工业 ,一些应用体会,自身定位(优化理论、优化计算、具有重要应用背景的优化问题