|
一种简单而广泛使用的数学技术最终可以应用于无限复杂的问题。
研究人员每天都在寻找最优解。他们可能想知道在哪里建立一个主要航空枢纽。或者确定如何在投资组合中最大化回报同时最小化风险。或者开发能够区分交通信号灯和停车标志的自动驾驶汽车。 从数学上讲，这些问题可以转化为寻找函数的最小值。但在所有这些情况下，函数都过于复杂，无法直接评估。取而代之的是，研究人员必须得到近似的最小值。 事实证明，实现这一目标的最佳方法之一是使用艾萨克·牛顿（Isaac Newton，1643 - 1727）300多年前开发的一种算法。该算法相当简单。有点像蒙着眼睛在陌生的地形中寻找最低点。当你迈开双脚时，你唯一需要的信息就是你是在上坡还是下坡，以及坡度是上升还是下降。利用这些信息，你可以相对快速地得到最小值的近似值。 尽管牛顿法非常强大——几个世纪后，它仍然是解决当今物流、金融、计算机视觉甚至纯数学问题的关键——但它也有一个明显的缺点。它并不适用于所有函数。因此，数学家们一直在研究这项技术，想出不同的方法来扩大其应用范围，同时又不牺牲效率。 去年夏天，三位研究人员公布了牛顿法的最新改进 https:///abs/2311.06374 。普林斯顿大学的Amir Ali Ahmadi和他的前学生Abraar Chaudhry（现就职于佐治亚理工学院）和Jeffrey Zhang（现就职于耶鲁大学）扩展了牛顿法，使其能够有效地处理迄今为止最广泛的函数类。 “牛顿法在最优化中有1000种不同的应用，”Ahmadi说道。“我们的算法有可能取代它。”
1680年代，艾萨克·牛顿发明了一种寻找最优解的算法。三个世纪后，数学家们仍在使用和完善他的方法。 图源：Godfrey Kneller/公共领域
数学函数将输入转换为输出。通常，一个函数最重要的特征是其最小（输入）值——产生最小可能输出的输入组合。 但找到最小值很难。函数可能有几十个变量的高次幂，无法进行公式分析；它们的解的图像形成高维景观，无法从鸟瞰视角探索。牛津大学的Coralia Cartis说，在这些高维景观中，“我们想找到一个山谷。有些是局部山谷；有些是最低点。你试图找到这些东西，问题是：有什么信息可以指导你找到它们？” 1680年代，牛顿认识到，即使你处理的是非常复杂的函数，你仍然总能获得至少两条信息来帮助你找到它的最深谷。首先，你可以计算函数所谓的一阶导数，即斜率：函数在给定点的陡度（坡度）。其次，你可以计算斜率本身的变化率（函数的二阶导数）。
Amir Ali Ahmadi（阿米尔·阿里·艾哈迈迪）发现，无论何时何地，最优化问题都随处可见。 图源：Mathematisches Forschungsinstitut Oberwolfach奥伯沃尔法赫数学研究所档案 假设你正在尝试寻找某个复杂函数的最小值点。首先，选择函数上你认为可能接近真实最小值的一点。计算该点处函数的一阶和二阶导数。这些导数可用于构造一个特殊的二次方程——如果你的函数位于二维平面中，则为抛物线（parabola）；如果你的函数是高维的，则是称为抛物面（paraboloid）的杯状形状。这个二次方程称为泰勒逼近（Taylor approximation，也称泰勒近似），与你选择的点处的函数大致相似。 现在计算二次方程的最小值点，而不是原始方程的最小值点——使用众所周知的公式，你可以轻松地做到这一点。（这是因为二次方程很简单；当方程变得更复杂时，计算最小值就变得困难了。）你会得到一个点。然后把这个点的坐标插回到你的原始函数中，你会得到一个函数上的新点，希望这个新点更接近它的真实最小值。然后重新开始整个过程。 牛顿证明，如果你不断重复这个过程，你最终会找到原始更复杂函数的最小值。这种方法并不总是有效，特别是当你从离真实最小值太远的点开始的时候。但在大多数情况下，它是有效的。而且它有一些理想的性质。 寻找最优解 在1680年代，艾萨克·牛顿发明了一种求函数最小值的方法它的最优解。几个世纪后，数学家们仍然在使用他的算法。
图源：Mark Belan/Quanta Magazine 原始来源：https:///abs/2305.07512 其他迭代方法，如梯度下降（gradient descent，当今机器学习模型中使用的算法）以线性速率收敛到真实最小值。牛顿法收敛速度要快得多：以“二次”速率。换句话说，它可以在比梯度下降更少的迭代次数中识别最小值。 牛顿法的每次迭代比梯度下降的迭代更耗费计算资源，这就是为什么研究人员在某些应用中更喜欢使用梯度下降，比如训练神经网络。但牛顿法仍然非常高效，使其在各种情况下都很有用。 如果牛顿不只是在每个点取一阶和二阶导数，而是取三阶和四阶导数，他本可以更快地编写出收敛到真实最小值的方法。这将使他得到更复杂的泰勒近似值，指数大于2。 但他的策略的关键是将一个复杂的函数转换成一个更简单的函数。这些更复杂的泰勒方程超出了牛顿的数学处理能力。
Jeffrey Zhang和他的合著者以正确的方式调整函数，从而拓宽了强大优化技术的范围。 图源：Jeffrey Zhang “牛顿对二次多项式进行了求解。他这样做是因为没有人知道如何最小化高阶多项式，”Ahmadi说。 在此后的几个世纪里，数学家们一直致力于扩展他的方法，探索从更复杂的函数泰勒近似中能榨出多少信息。 例如，在19世纪，俄罗斯数学家帕夫努蒂·切比雪夫（Pafnuty Chebyshev，1821 - 1894）提出了牛顿法的一个版本，用三次方程（指数为3）来逼近函数。但是当原始函数涉及多个变量时，他的算法不起作用。 更近的一次是在2021年，尤里·涅斯捷罗夫（Yurii Nesterov，现就职于布达佩斯考文纽斯大学）展示了如何用三次方程有效地近似任意数量变量的函数 https://link./article/10.1007/s10107-019-01449-1 。 但他的方法无法扩展到使用四次方程、五次方程等来近似函数，否则会降低其效率。尽管如此，这一证明仍然是该领域的一个重大突破。 现在，Ahmadi、Chaudhry和Zhang将Nesterov的结果又推进了一步。他们的算法适用于任意数量的变量和任意数量的导数。此外，它在所有这些情况下仍然有效——这是迄今不可能实现的。 但首先，他们必须找到一种方法来让难题变得更容易。
目前还没有一种快速、通用的方法来寻找高次函数的最小值点。这一直是牛顿法的主要限制。但有些类型的函数具有易于最小化的特征。在这项新研究中，Ahmadi、Chaudhry和Zhang证明总是可以找到具有这些特征的近似方程。然后他们展示了如何调整这些方程高效运用牛顿法。 什么性质使得方程式易于最小化？有两点： 首先，方程式应该是碗状的，或“凸的”（convex）。它只有一个谷值，而不是许多谷值——这意味着当你试图最小化它时，你不必担心将任意谷值误认为最低谷值。
Abraar Chaudhry和两位同事最近找到了一种方法来改进已有数百年历史的寻找函数最小值点的方法。 图源：Camille Carpenter Henriquez 第二个性质是方程可以写成平方和。例如，5x²+16x+13 可以写成 (x+2)²+(2x+3)²。近年来，数学家已经开发出最小化具有任意大指数的方程的技术，只要它们既是凸函数又是平方和。 然而，这些技术在牛顿法中用处不大。大多数情况下，你使用的泰勒近似不会具有这些良好的性质。 但是Ahmadi、Chaudhry和Zhang想出了如何使用一种名为半定规划（semidefinite programming）的技术来对泰勒近似进行足够的调整，使其既成为平方和又成为凸函数，但又不至于使其脱离它应该近似的原始函数。 他们实际上是在泰勒展开式中添加了一个修正因子，将其变成了具有两种所需性质的方程。“我们可以稍微改变泰勒展开式，使其更容易最小化。考虑泰勒展开式，但稍作修改，”艾Ahmadi说。 他和他的同事随后证明，使用这个修改版的泰勒展开式——涉及任意多个导数——他们的算法仍然会收敛到原始函数的真实最小值。 此外，收敛速度会随着所用导数的数量而变化：正如使用两个导数允许牛顿法以二次速率接近真实最小值一样，使用三个导数使研究人员能够以立方速率接近它，依此类推。 Ahmadi、Chaudhry和Zhang创建了一个更强大的牛顿法版本，与以前的技术相比，它可以用更少的迭代次数达到函数的真实最小值。 与牛顿法的原始版本一样，这种新算法的每次迭代在计算上仍然比梯度下降等方法更昂贵。因此，目前，这项新工作不会改变自动驾驶汽车、机器学习算法或空中交通管制系统的运作方式。在这些情况下，最好的选择仍然是梯度下降。 宾夕法尼亚大学的Jason Altschuler表示：“最优化领域的许多想法需要花费数年时间才能完全付诸实践。但这似乎是一个全新的视角。” 如果随着时间的推移，运行牛顿法所需的底层计算技术变得更加高效——使得每次迭代的计算成本更低——那么Ahmadi、Chaudhry和Zhang开发的算法最终可以在包括机器学习在内的各种应用中超越梯度下降。 “从理论上讲，我们目前的算法确实更快，”Ahmadi说。他补充说，他希望10到20年后，该算法在实践中也能保持更快。
https://www./three-hundred-years-later-a-tool-from-isaac-newton-gets-an-update-20250324/ https:///abs/2311.06374 https:///abs/2305.07512 https://link./article/10.1007/s10107-019-01449-1
【第7波】10本zzllrr小乐推荐精读的国内外优秀数学科普书籍【平价优选】【推荐日期2025-3-14】 【第6波】10本zzllrr小乐推荐精读的国内外优秀数学科普书籍【平价优选】【推荐日期2025-1-27】 【第5波】10本zzllrr小乐推荐精读的国内外优秀数学科普书籍【平价优选】【推荐日期2025-1-1】
2025年ICBS国际基础科学大会基础科学终身成就奖揭晓（数学、物理、信息科学与工程） 动漫迷们是如何偶然发现数学证明的——译自Scientific American科学美国人 数学符号野蛮且有争议的历史——译自Scientific American科学美国人 挂谷猜想专题系列——“百年一遇”的数学证明解决了三维挂谷猜想——译自Quanta Magazine量子杂志 【第7波】10本zzllrr小乐推荐精读的国内外优秀数学科普书籍【平价优选】【推荐日期2025-3-14】 数学家们无法停止思考的9个未解之谜——科学美国人数学未解难题集锦 数学天才英年早逝多年后，她的思想焕发新生——译自量子杂志Quanta Magazine 2025年IDM3.14国际数学日海报出炉，设计基于彭罗斯密铺，今年数学日主题——数学，艺术和创造力 AI算法的进步可能会刺激计算方面的支出增加，而不是减少——译自Epoch AI 挂谷猜想专题系列——怎样移动针头的简单数学——译自Quanta Magazine量子杂志 挂谷猜想专题系列——针尖上的猜想之塔——译自Quanta Magazine量子杂志 挂谷猜想专题系列——新证明穿针引线到一个粘性几何问题上——译自Quanta Magazine量子杂志 挂谷猜想专题系列——新数系将几何问题指向实数解——译自Quanta Magazine量子杂志 【第6波】10本zzllrr小乐推荐精读的国内外优秀数学科普书籍【平价优选】【推荐日期2025-1-27】 “扩展”图同步的新数学证明——译自Quanta Magazine量子杂志 欣赏模形式，数学的“第五种基本运算”——译自Quanta Magazine量子杂志 实数值代数几何的邀请——译自AMS Notices美国数学会通告2025-2 推动现代数学发展的简单方程——椭圆曲线——《量子杂志》每周数学随笔 对话2024年罗素奖得主Susan Landau苏珊·兰道——译自AMS Notices美国数学会通告2025-2 2025AMS莫尔研究论文奖作者之一Seán Keel肖恩·基尔关于该获奖论文的背后介绍 计算机科学家如何重新构想数学证明——《量子杂志》每周数学随笔 采访2024Crafoord奖得主克莱尔·瓦赞Claire Voisin——数学作为私人空间从猜想的揭开到世界认可 请尽情触摸你无法抗拒抓住的数学——译自EMS Magazine 2024年SASTRA拉马努金奖10000美元授予亚历山大·邓恩（Alexander Dunn） 【第5波】10本zzllrr小乐推荐精读的国内外优秀数学科普书籍【平价优选】【推荐日期2025-1-1】 · 开放 · 友好 · 多元 · 普适 · 守拙 · 让数学 更加 易学易练 易教易研 易赏易玩 易见易得 易传易及 欢迎评论、点赞、在看、在听 收藏、分享、转载、投稿 |
|
|
