优化简史

字数统计: 1k字 | 阅读时长: 3分

2023-05-26

摘要: 优化事件编年史

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

古希腊

古希腊解决了一些与几何有关的优化问题。

时间	人物	事件
公元前300	欧几里得	点与直线的最短距离

在微积分前夕，数学家零散地研究了一些优化问题。

1660 ~ 1670，牛顿和莱布尼茨分别独立创立微积分，后来成为变分法的基础。

之后魏尔斯特拉斯、斯坦纳、汉密尔顿、雅可比进一步发展了变分法。

1870 年代，经济学研究中心转移到效用最大化的个体上，最优化成为经济学理论的组成部分。

时间	人物	事件
1902	法卡斯 (Farkas)	提出Farkas引理，该引理可用于证明 Karush-Kuhn-Tucker 定理。
1905	詹森 (Jensen)	引入凸函数以及詹森不等式
1911	闵可夫斯基	遗作由希尔伯特整理后出版，其中包括凸集的理论
1917	汉考克 (Hancock)	出版第一本关于优化的书《极小值与极大值理论》
1925	莫尔斯 (Morse)	推广极小极大原理，提出莫尔斯不等式
1928	拉姆齐 (Ramsey)	在关于最佳经济增长的研究中运用变分法
1931	瓦伊纳 (Viner)	提出包络定理
1932	L.Menger	提出旅行商问题一般表述
1934	哈代	出版《不等式》，其中有专门章节介绍凸函数及其应用
1939	坎托罗维奇	提出线性规划模型及其求解算法

二战后，冯诺依曼主导运筹学发展，计算机出现后，算法研究的领域逐渐扩大。

时间	人物	事件
1944	冯诺依曼、摩根斯坦 (Morgenstern)	通过动态规划思想解决顺序决策问题
1947	丹齐格	提出单纯性方法
1947	冯诺依曼	提出线性规划问题的对偶理论
1951	Kuhn、Tucker	提出非线性问题的最优性条件，1939 年 Karush 提出类似的条件
1951	马科维茨	提出基于二次优化的投资组合理论
1954	Ford、Fulkerson	对网络问题的研究是组合优化研究的一个起点
1959	戴维登 (Davidon)	提出拟牛顿法
1952	Hesteness	提出求解线性方程组的共轭梯度法
1954	庞特里亚金 (Pontryagin)	提出最大值原理
1957	贝尔曼	提出最优性原理
1960	约坦狄克 (Zoutendijk)	提出可行方向法来概括非线性规划的单纯形法
1964	Fletcher	提出求解非线性优化的共轭梯度法
1963	Wilson	首次提出序列二次规划法