文档介绍：2017-2-22 最优化理论 TP SHUAI TP SHUAI 1最优化理论与算法?帅天平?北京邮电大学数学系 2017-2-22 最优化理论 TP SHUAI TP SHUAI 2提纲 1. 线性规划对偶定理 2. 非线性规划 K-K-T 定理 3. 组合最优化算法设计技巧使用教材: 最优化理论与算法陈宝林参考书: 数学规划黄红选, 韩继业清华大学出版社 2017-2-22 最优化理论 TP SHUAI TP SHUAI 3其他参考书目 Nonlinear Programming - Theory and Algorithms Mokhtar S. Bazaraa, C. M. Shetty John Wiley & Sons, Inc. 1979 (2nd Edit, 1993 , 3nd Edit ,2006) Linear and Nonlinear Programming David G. Luenberger Addison-Wesley pany, 2nd Edition, 1984/2003.. Convex Analysis R. T. Rockafellar Princeton Landmarks in Mathematics and Physics, 1996. Optimization and Nonsmooth Analysis Frank H. Clarke SIAM, 1990. 2017-2-22 最优化理论 TP SHUAI TP SHUAI 4 ? Linear Programming work Flows M. S. Bazaraa, J. J. Jarvis, John Wiley & Sons, Inc., 1977. 运筹学基础手册徐光辉、刘彦佩、程侃科学出版社, 1999 组合最优化算法和复杂性 Combinatorial Optimization 蔡茂诚、刘振宏 Algorithms plexity 清华大学出版社, 1988 Printice-Hall Inc.,1982/1998 其他参考书目 2017-2-22 最优化理论 TP SHUAI TP SHUAI 51,绪论---- 学科概述?最优化是从所有可能的方案中选择最合理?的一种方案,以达到最佳目标的科学. ?达到最佳目标的方案是最优方案,寻找最优?方案的方法---- 最优化方法(算法) ?这种方法的数学理论即为最优化理论. ?. 运筹学的“三个代表”模型理论算法最优化首先是一种理念,其次才是一种方法. 2017-2-22 最优化理论 TP SHUAI TP SHUAI 6 绪论---运筹学( Operations Research - OR )运筹学方法随机过程方法统计学方法最优化/数学规划方法?连续优化:线性规划、非线性规划、非光滑优化、全局优化、变分法、二次规划、分式规划等?离散优化:组合优化、网络优化、整数规划等?几何规划?动态规划?不确定规划:随机规划、模糊规划等?多目标规划?对策论等?统计决策理论?马氏过程?排队论?更新理论?仿真方法?可靠性理论等?回归分析?群分析?模式识别?实验设计?因子分析等 2017-2-22 最优化理论 TP SHUAI TP SHUAI 7 优化树 2017-2-22 最优化理论 TP SHUAI TP SHUAI 8 最优化的发展历程费马:1638; 牛顿,1670 min f (x) x: df(x) 0 dx ?数欧拉,1755 Min f(x1 x2 ··· xn ) ? f(x)=0 2017-2-22 最优化理论 TP SHUAI TP SHUAI 9?欧拉,拉格朗日:无穷维问题,变分学?柯西:最早应用最速下降法拉格朗日, 1797 Min f(x1 x2 ··· xn) . gk (x1 x2 ··· xn )=0, k=1,2, …,m 2017-2-22 最优化理论 TP SHUAI TP SHUAI 10 ?1930 年代,康托诺维奇:线性规划?1940 年代, Dantzig :单纯形方法, ?冯诺依曼:对策论?1950 年代, Bellman :动态规划,最优性原理; ? KKT 条件; ?1960 年代: Zoutendijk,Rosen,Carroll,etc. 非线性规划算法, Duffin , Zener 等几何规划, Gomory ,整数规划,Dantzig 等随机规划? 6-70 年代: Cook 等复杂性理论,组合优化迅速发展?电子计算机---