1.1　优化算法的历史

我们首先讨论一下优化的历史[1]。毕达哥拉斯定理的提出者毕达哥拉斯（公元前569—公元前475，萨摩斯人）声称“数学之理亦是万物之理（万物皆数）”[2]，并提出了数学可以模拟世界的观点。柏拉图（公元前427—公元前347）和亚里士多德（公元前384—公元前322）将推理用于社会优化[3]。他们考虑了最佳的人类生活方式，包括个人生活方式和国家运作方式的优化。亚里士多德的逻辑学是一种早期的正式推理流程，它可以被看作一种算法。

数学抽象的优化也可以追溯到几千年前。欧几里得（公元前325—公元前265，亚历山大人）解决了几何学中的早期优化问题，包括如何找到从一个点到圆周的最短和最长的线。他还表明，正方形是具有固定周长的面积最大的矩形[4]。古希腊数学家芝诺多罗斯（公元前200—公元前140）研究了迪多的问题，如图1.1所示。

还有人证明大自然似乎同样进行着最优化。海伦（10—75，亚历山大人）表明，光通过两点之间最短的路径传播。帕普斯（290—350，亚历山大人）对优化做出了许多贡献，他认为蜂窝中重复的六边形是用于储存蜂蜜的最佳正多边形，它的六边形结构使用最少的材料在平面上创建细胞晶格[5]。

优化研究的核心是对代数学的运用，代数是对数学符号运算规则的研究。代数的创立归功于波斯数学家阿尔·花剌子模（790—850），其著有专著The Compendious Book on Calculation by Completion and Balancing（移项和集项的科学）。代数具有使用印度-阿拉伯数字的优点，包括在基本符号中使用零。al'jabr这个词在波斯语中是恢复的意思，也是西方单词algebra（代数）的来源。术语算法（algorithm）来自algoritmi，即阿尔·花剌子模名字的拉丁语翻译和发音。

优化问题通常在坐标系定义的空间中进行搜索。我们通常使用勒内·笛卡儿（1596—1650）发明的坐标系，他使用两个数字来描述二维平面上的点。他将代数中的解析方程与几何学的表达和视觉联系起来[6]，还提出了找到任何已知方程曲线切线的方法，切线可用于确定函数的极小值和极大值。皮埃尔·德·费马（1601—1665）开始求解导数为零的位置，以确定潜在的最优点。

微积分的概念，或对连续变化的研究，在我们对于优化的讨论中发挥了重要作用。现代微积分源于戈特弗里德·威廉·莱布尼茨（1646—1716）和艾萨克·牛顿爵士（1642—1727）的研究成果。微分和积分都利用无穷级数的收敛概念来得到明确定义的极限。

20世纪中叶，电子计算机兴起，激发了人们对数值优化算法的兴趣。计算的简易化使得优化可以被应用于各种领域中更大的问题。线性规划的引入是优化领域的重大突破之一，线性规划是有关线性目标函数和线性约束的优化问题。列昂尼德·坎托罗维奇（1912—1986）提出了线性规划的表达方式和它的求解算法[7]，该算法被应用于第二次世界大战期间的最佳资源分配问题。乔治·丹齐格（1914—2005）提出了单纯形法，它代表了有效解决线性规划问题的重大进步[8]。理查德·贝尔曼（1920—1984）提出了动态规划的概念，这是一种常用的方法，它将复杂问题分解为更简单的问题来优化，以此解决复杂问题[9]。动态规划已被广泛用于最佳控制。本书将概述为数字计算机开发的许多关键算法，这些算法已被用于各种工程设计中的优化问题。

计算领域数十年来的大规模进步已经引领了革新的物理工程设计以及人工智能系统设计。这些系统的智能已经在国际象棋和围棋等游戏中得到了证明。IBM的Deep Blue在1996年通过评估数百万个状态来优化行为，进而击败了世界象棋冠军加里·卡斯帕罗夫。2011年，IBM的Watson在智力问答节目中对阵前获胜者Brad Futter和Ken Jennings。Watson通过对2亿条结构化和非结构化数据的可能性进行优化分析，并得出结论，赢得了100万美元的一等奖奖金。在那次比赛之后，该系统又发展了协助进行医疗保健决策和天气预报的功能。2017年，Google的AlphaGo击败了世界排名第一的围棋手柯洁。该系统使用拥有数百万个参数的神经网络，这些参数通过自身模拟对战并使用来自人类对局的数据进行优化。深度神经网络的优化正在推动人工智能的一场重大革命，这场革命可能会持续下去[10]。

[1] 这个讨论并不全面，X.-S. Yang提供了更详细的历史，参见：

“A Brief History of Optimization，”Engineering Optimization. Wiley，2010，pp. 1-13.

[2] Aristotle，Metaphysics，trans. by W. D. Ross. 350 BCE，Book I，Part 5.

[3] S. Kiranyaz，T. Ince，and M. Gabbouj，Multidimensional Particle Swarm Optimization for Machine Learning and Pattern Recognition. Springer，2014，Section 2.1.

[4] Book Ⅲ and VI of Euclid，The Elements，trans. by D. E. Joyce. 300 BCE.

[5] T. C. Hales，“The Honeycomb Conjecture，”Discrete & Computational Geometry，vol.25，pp. 1-22，2001.

[6] R. Descartes，“La Géométrie，”Discours de la Méthode. 1637.

[7] L. V.Kantorovich，“A New Method of Solving Some Classes of Extremal Problems，”Proceedings of the USSR Academy of Sciences，vol.28，1940.

[8] 单纯形法将在第11章中讨论。

[9] R. Bellman，“On the Theory of Dynamic Programming，”Proceedings of the National Academy of Sciences of the United States of America，vol.38，no.8，pp. 716-719，1952.

[10] I. Goodfellow，Y. Bengio，and A. Courville，Deep Learning. MIT Press，2016.