最优化理论与算法起因和发展.pptx

最优化理论与算法起因和发展
2
最优化的发展历程
费马:1638
皮耶·德·费马（Pierre de Fermat）是一个17世纪的法国律师，也是一位业余数学家。之所以称业余，是由于皮耶·德·费马具有律师的全职工作。费马最后定理在中国****惯称为费马大定理，西方数学界原名“最后”的意思是：其它猜想都证实了，这是最后一个。著名的数学史学家贝尔（E. T. Bell）在20世纪初所撰写的著作中，称皮耶·德·费马为”业余数学家之王“。贝尔深信，费马比皮耶·德·费马同时代的大多数专业数学家更有成就。
3
最优化的发展历程
牛顿,1670
他在1687年发表的论文《自然定律》里，对万有引力和三大运动定律进行了描述。提出牛顿运动定律，发明了反射望远镜和发展出微积分学。提出了“牛顿法”以趋近函数的零点和金本位制度
4
最优化的发展历程
欧拉,1755
Min f(x1 x2 ··· xn )
 f(x)=0
莱昂哈德·欧拉，瑞士数学家、自然科学家。1707年4月15日出生于瑞士的巴塞尔，1783年9月18日于俄国圣彼得堡去世。16岁获得硕士学位。欧拉是18世纪数学界最杰出的人物之一，他不但为数学界作出贡献，更把整个数学推至物理的领域。他是数学史上最多产的数学家，平均每年写出八百多页的论文，还写了大量的力学、分析学、几何学、变分法等的课本，《无穷小分析引论》、《微分学原理》、《积分学原理》等都成为数学界中的经典著作。欧拉对数学的研究如此之广泛，因此在许多数学的分支中也可经常见到以他的名字命名的重要常数、公式和定理。[1]  此外欧拉还涉及建筑学、弹道学、航海学等领域。
5
欧拉，拉格朗日：无穷维问题，变分学
柯西：最早应用最速下降法
拉格朗日，1797
Min f(x1 x2 ··· xn)
. gk (x1 x2 ··· xn )=0, k=1,2,…,m
-6-
线性规划发展的历史
法国数学家 (Joseph Fourier)和 －普森分别于1832和1911年独立地提出线性规划的想法，但未引起注意。
(Kantorovich)在《生产组织与计划中的数学方法》一书中提出线性规划问题，也未引起重视。
7
1930年代，康托诺维奇：线性规划
1940年代，丹齐格Dantzig：单纯形方法，
：对策论
1950年代，Bellman：动态规划，最优性原理；
KKT条件；
1960年代：Zoutendijk,Rosen,Carroll,，Duffin，Zener等几何规划，Gomory，整数规划,Dantzig等随机规划
60-70年代：Cook等复杂性理论，组合优化迅速发展
电子计算机----------最优化
2006/08
-8-
线性规划发展的历史
利奥尼德·康托洛维奇(, 1912—1986) ，苏联数学家，,1934年成为该校最年轻的数学教授,—1960年任列宁格勒科学院数学所研究室主任,1958年当选为苏联科学院通讯院士,并于1964年成为苏联科学院院士.
-9-
线性规划发展的历史
1960—1971年任苏联科学院西伯利亚分院数学所副所长,1971—1976年任苏联 ,,他建立和发展了线性规划方法,并运用于经济分析,对现代经济应用数学的重要分支——,由定性研究和一般的定量分析推进到现实计量阶段, 的主要著作包括:《生产组织和计划中的数学方法》(1939年),《经 济资源的最优利用》(1959年),《经济最优决策》(1972年,合著),《最优规划文集》(1976年)、推广和发展资源最优利用理论方面所做出的杰出贡献，与美籍荷兰经济学家库恰林·库普曼斯(, 1910—1985)一起分享1975年度诺贝尔经济学奖.
2006/08
第 1 章 线性规划---
-10-
乔治·伯纳德·丹齐格（