最优化理论发展简史 - 群英璀璨，全知道就服你！

1古代

希腊数学家解决了一些与其几何研究有关的优化问题。

• 公元前 300 年，欧几里得（Euclid）考虑了点与直线之间的最段距离，并证明了在给定的总边长下，正方形在矩形中面积最大。
• 公元前 200 年，芝诺多罗斯（Zenodorus）研究 Dido 问题（即等周问题），证明了部分结论。
• 公元前 100 年，Heron 证明从镜子反射时光在路径上的两点之间传播的长度最短。

217 和 18 世纪

在发明变化微积分之前，仅研究了一些单独的优化问题。

• 1615 年，开普勒（Kepler）提出了酒桶的最佳尺寸。当他后来找新对象的时候，他还提出了秘书问题的早期版本（动态规划的经典应用）。
• 1638 年，伽利略（Galilei）试图弄清楚吊链的形状，但他失败了。
• 1636 年，费马（Fermat）发现在极值点处，函数导数为零。
• 1657 年，费马提出光的传播总是使在某两点间时间最短。

1660-1670 年代，牛顿（Newton）和莱布尼兹（Leibniz）分别独立创立了微积分，后来成为变分法（Calculus of Variations，简称 CoV）的基础。

• 1687 年，牛顿研究了最小阻力的物体。
• 1696 年，约翰（Johann）和雅各布·伯努利（Jacob Bernoulli）研究了最速降线问题，由此引出了一门新学科 - 变分法。
• 1740 年，欧拉（Euler）出版了研究变分学一般理论的著作。
• 1746 年，莫佩尔蒂（Maupertuis）提出了最小作用量原理来解释物理现象。
• 1754 年，拉格朗日（Lagrange）在 19 岁时提出了他在变分学上的第一个发现。1760 年，他提出了极小曲面问题。1936 年，道格拉斯（Douglas）因解决该问题而获得菲尔兹奖；1974 年，庞贝里（Bombieri）因在这一课题上的工作而获得菲尔兹奖。
• 1784 年，蒙日（Monge）研究了一个组合优化问题，即最优传输问题。
• 1788 年，拉格朗日正式发表拉格朗日乘子法，用于求解带约束条件的优化问题。
  

319 世纪

维尔斯特拉斯（Weierstrass），斯坦纳（Steiner），汉密尔顿（Hamilton）和 雅可比（Jacobi）进一步发展了变分法。

数学家提出了第一个优化算法，而最优化逐渐走向实际应用，并成为经济学理论的组成部分。

• 1806 年勒让德（Legendre）提出了最小二乘法，高斯（Gauss）声称自己更早之前就已经发现了这种方法但没有及时发表。
• 1826 年傅立叶提出线性规划以解决力学和概率论中出现的问题。
• 1847 年，柯西（Cauchy）提出了梯度法。
• 1857 年，吉布斯（Gibbs）提出化学平衡就是能量最小。

1870 年代，经济学的边际主义革命，例如 Walras 和 Cournot 的著作将经济学家的重心转移到效用最大化的个体上，最优化成为经济学理论的组成部分。

420 世纪

Bolza，Caratheodory 和 Bliss 进一步发展了变分法。

• 1902年，法卡斯（Farkas）提出了他的著名引理，该引理可用于证明 Karush-Kuhn-Tucker 定理。
• 提出凸性概念: 詹森（Jensen）于 1905 年引入凸函数，这一思想已经出现在哈达玛（Hadamard，1883 年），霍尔德（Hölder，1889 年）和奥斯托尔（O.Stolz，1893 年）。闵可夫斯基（Minkowski）于 1911 年取得他关于凸集的第一项成果。
• 1917 年汉考克（Hancock）出版了第一本关于优化的书，《极小值和极大值理论》。
• 1917 年生物数学家汤普森（Thompson）撰写了《成长与形式》一书，其中他运用优化方法来分析生物体的形式。
• 1925 年莫尔斯（Morse）提出他的理论，推广了变分法。
• 1928 年拉姆齐（Ramsey）在其关于最佳经济增长的研究中运用了变分法。
• 1931 年，Viner 提出了 Viner-Wong 包络定理。
• 1932 年，Menger 提出了旅行商问题的一般表述。
• 1939 年，坎托罗维奇（Kantorovich）提出了线性规划模型及其求解算法。1975 年，坎托罗维奇和 Koopmans 因对线性规划问题的贡献而获得诺贝尔经济学奖。

第二次世界大战后，优化与运筹学同时发展。冯·诺依曼（J. Von Neumann）是运筹学发展背后的重要人物。随着电子计算机的发展，算法研究的领域不断扩大。

• 1944 年，冯·诺伊曼（von Neuman）和莫根斯坦（Morgenstern）通过使用动态规划的思想解决了顺序决策问题。
• 1947 年，Dantzig 在美国空军工作，提出了解决线性规划问题的单纯形方法，冯·诺依曼建立了线性规划问题的对偶理论。
• 1949 年，第一届关于优化的国际数学规划研讨会在芝加哥举行，会上发表论文 34 篇。

1950 年代

• 1951 年，H.W. Kuhn 和 A.W. Tucker 提出了非线性问题的最优性条件。F. John（1948 年）以及 W. Karush（1939 年）已经提出了类似条件。
• 1951 年，马科维茨提出了基于二次优化的投资组合理论。1990 年，马科维茨获得诺贝尔经济学奖。
• 1954 年，L.R. Ford 和 D.R. Fulkerson 对网络问题的研究是组合优化研究的一个起点。
• 发展了求解无界问题的算法，例如拟牛顿法和共轭梯度法。拟牛顿法于 50 年代由美国 Argonne 国家实验室的物理学家 W. C. Davidon 所提出来。

美苏太空竞赛进一步推动了最佳控制理论的研究。最优控制理论开始独立于变分法而发展。

• 1954 年，IEEE 控制系统协会成立。
• 1956 年，庞特里亚金（Pontryagin）的研究小组提出了最大值原理。
• 1957 年，贝尔曼（Bellman）提出了最优性原理。

1960 年代

• 1960 年，约坦狄克（Zoutendijk）提出了可行方向法来概括非线性程序的单纯形法。罗森（Rosen）、沃尔夫（Wolfe）和鲍威尔（Powell）提出了类似算法。
• 1963 年，Wilson 首次提出序列二次规划法。Han 在 1975 年以及 Powell 在 1977 年重新提出了类似方法。