米兰·(milan)中国官方网站-普林斯顿研究“最小值”：平方和的破局，二次和三次优化问题的极限

---

多方针优化是各个范畴中遍及存于的问题，每一个方针不成能都同时到达最优，而且有实际运用的时效。各个因素必需各有权重。于困局中，平方及要领可用来寻觅局部最优解。

编译 | 吴彤

编纂| 维克多

生命是一连串的优化问题，放工后寻觅回家的最快线路；去市肆的路上衡量最好性价比，甚至当睡前“玩手机”的摆设，均可以看作优化问题。

优化问题的同义词是找到解决方案，有没有数学者想根究于最短期内，找到最佳的解。但最新研究指出，一些二次优化问题，例如变量对于可以彼此作用的公式，只能“循序渐进”找到局部最优解。换句话说“不存于快速计较要领”。

好动静是，另外一项研究发明对于在三次多项式下的优化问题，存于快速求解的要领。详细而言，可以经由过程利用平方及查验（sum-of-squares test）找到某些多项式的最低点，进而搜刮三次函数的局部最优解。

两项研究时隔两天，出自在统一研究团队：普林斯顿年夜学的Amir Ali Ahmadi及他的前学生Jeffrey Zhang。

Amir Ali Ahmadi及他的前学生Jeffrey Zhang

Amir Ali Ahmadi是普林斯顿年夜学运筹学与金融工程系传授，于插手普林斯顿年夜学以前，曾经是IBM Watson研究中央的Goldstine研究员，其对于优化理论，动力学及节制的计较以和算法及繁杂度有很深的造诣。Jeffrey Zhang是卡内基梅隆年夜学的客座传授，研究范畴包括博弈论、计较繁杂性、多项式优化等等。

两篇“涉事”论文别离是：

论文1：On the complexity of finding a local minimizer of a quadratic function over a polytope

孝敬：判断二次函数于(无界)多胞形（ polyhedron）上是否有局极小值，以和判断四次多项式是否有局部极小值属在NP难。

论文链接：https://arxiv.org/abs/2008.05558

论文2：Complexity aspects of local minima and related notions

孝敬：证实了于三次多项式中，某些优化问题轻易处置惩罚，且给出了寻觅三次多项式局部极小值的一个充要前提。

论文链接：https://arxiv.org/abs/2008.06148

这两篇论文，一前一后，证实了繁杂性计较研究的近况：某种类型的优化问题很轻易解决，而某种类型的问题则一定很难解决。更进一步，他们为从金融到主动体系等各个范畴的优化问题确定了新的界限。

1糊口中的优化问题

假定一家汽车厂只出产两种车型，自制版及奢华版。奢华版的售价高在自制车，但出产成本更高，出产时间也更长。那末两种车型应该各出产几多?

这个问题可以转化为一个用多项式表达的优化求解问题。

起首，这个问题可以分化为三个元素：

有待优化的可量化变量，好比必需出产的汽车数目。

一些约束前提，好比预算及出产能力。

一个叫做方针函数的工具，方针函数的功效是给定决议计划变量，输出解决方案（优化值）。

汽车例子仅仅是一个简朴的优化问题，变量之间没有彼此作用，优化值可以经由过程求解线性函数获得。但实际中的问题往往很是繁杂。

例如，怎样选择最好航空枢纽。枢纽航班波强度及密度的经济性与机场装备举措措施、机型、航班布局等等有关，只有于这几个方面取患上最好共同的环境下，枢纽中转才能真正阐扬作用。

枢纽航空公司于构造航班的时辰，但愿航班波的强度及密度越年夜越好，如许就能够提高单元时间内的中转效率，与此带来的单元时间内航班量过年夜，中转人数过量的岑岭处置惩罚量，给机场及航空公司带来了巨年夜的运营压力及成本压力。也就是说，航空公司于枢纽机场的处置惩罚能力靠近峰值后，会呈现快速阑珊，致使操作成本快速提高及办事质量急剧降落。

固然，还有有许多问题可能比这更繁杂。变量之间的三阶交互作用需要用到更繁杂的函数。每一一步函数繁杂性都要为更广泛的问题建模，可是这类繁杂性是有价钱的，它可能计较不出最优解。

2退而求其次，找出最好“妨碍”

现代优化理论成长在第二次世界年夜战时期（1939年至1945），其时一名名叫 George Dantzig的科学家设计了一个寻觅线性优化问题解的步伐，被运用到美国国防部采购飞机及海外输送物质的战时实践上。

于接下来的几十年里，研究职员追随George的带领，开发了更快的算法，为日趋繁杂的实际问题找到最好解决方案。

但于20世纪80年月，这些前进碰到了一个不成超越的障碍。研究职员发明，解决优化问题的快速算法不成能存于。他们认为，这些问题从底子上来讲太繁杂了。

假如没法得到最优解决方案，还有能怎么办? 类似解，或者者“局部”最优解。

局部最优解可能其实不代表最好成果，但它们比任何近似解都要好。它们是做出决议计划的“充足好”的方式，好比每一辆车要出产几多辆，不克不及经由过程对于某些变量的微小调解来改良，只有年夜范围的重组才能致使绝对于最佳的成果，但对于在年夜问题，这类计较过在密集。

鉴在这一切，自20世纪90年月初以来，研究职员一直试图确定：是否存于一种快速找到局部最优解的要领。

3二次方程的坏动静

当研究职员想要确定一个问题于计较上是否难以解决时，他们凡是会将其等同在一些已经知繁杂性的问题。好比假如知道A问题很难解决，可以证实，解决问题B将为解决A提供一种要领。

于Amir Ali Ahmadi及Jeffrey Zhang的第一篇论文中，他们将二次优化的挑战与所谓的最年夜不变集问题举行了匹配。固然，最年夜不变集问题是一个闻名的而且可证实的难题。

“不变集”（stable set）是指图表中两个节点没有直接相连的任何节点列表。最年夜不变集问题要即找到图表中最年夜范围的不变集。纵然你只想知道是否存于一个给定巨细的不变集，但要确定这个谜底，计较相称繁杂。

去年6月，Ahmadi及Zhang将最年夜不变集问题从头界说为搜刮局部最优解的非凡环境。他们提出了一种将不变集问题暗示为二次优化问题的要领。在是，寻觅一个具备必然范围的不变集就酿成了寻觅这个优化问题的局部最优解的问题。

可是他们知道，依然没有一种很快速的计较要领来找到这些不变集，这象征着，对于在二次函数优化问题，局部最优解及真正最优解同样难以找到。

“直觉上，局部最优解应该更易，但出乎意料的是，他们二人证实两种解都很难。”荷兰国度数学及计较机科学研究所（CWI）的Monique Laurent说。

4三次方程的好动静

Ahmadi及Zhang解除了总能找到某些二次优化问题局部最优解的有用算法的存于。与此同时，他们想知道：于不包罗约束前提的简化前提下可以或许解决三次优化问题么?

三次多项式于很多现实要领中都很主要。它们为思索变量之间的三阶彼此作用提供了一个数学框架。增长一种瓜葛使患上瓜葛的清楚度提高，从而极年夜地改善呆板进修机能，好比于文本挖掘中，各人但愿算法能从年夜数据集中提取意义。

例如，你向计较机输入一段文本，并要求它确定这段文本的内容。计较机留意到“苹果”这个词常常呈现，可是没有更多的信息，致使“苹果”这个词语仍有歧义。

多是生果，也多是公司，或者者其他。

但若“苹果”及“橘子”同时呈现，计较时机越发确定这是生果。但还有是有可能堕落，由于橘子也多是一家公司。以是这时候候引入第三个词语，如“瓜”，即引入了立体瓜葛，可能会越发确信文本评论辩论的是农产物。

可是，清楚度的增长也带来了繁杂性。

从2019年头，Zhang就最先摸索解决这个问题的差别要领，但被卡住了，直到Ahmadi建议他测验考试一种叫做平方及的技能，Ahmadi之前曾经用这类技能解决其他优化问题。

5破局

“平方及”指的是一些多项式可以暗示为其他多项式的平方及。例如：

平方及展现了最初输入的多项式的属性。由于实数的平方不成能为负，以是假如将一个多项式暗示为平方及，证实它老是输出一个非负值。这是一种快速的查验要领。然而，这类要领于有约束的二次优化问题中不起作用，这就是为何Ahmadi及Zhang不克不及于他们的二次方程中使用它。

可是对于在没有约束的三次优化问题，平方及成为寻觅局部最优最小解时的主要要领。假如将多项式函数的图形描绘成一条浮动于横轴上方的曲线，它的最低点是对于应在变量的特定摆列。

这类算法可以快速轮回遍历一系列输入，重复测试多项式是否为平方及。此时，算法会将曲线向下拖动，无穷趋近在横轴。此时，另外一种算法可以快速注解低点的坐标。

此时，Zhang及Ahmadi才将优化问题向前推进了一小步，他们的冲破于在发明可以经由过程平方及查验找到某些多项式的最低点，从而寻觅三次函数的局部最优解。

于像如许的三次多项式的图中，一端老是指向负无限。以是三次方程不成能到处为正，可以用平方及查验。可是Ahmadi及Zhang想出了一种要领，只存眷曲线向上的那部门。

Zhang说：“对于在三次函数求解的问题，咱们老是可以把函数拖到咱们想要的位置，解决了三次函数局部最优解的主要理论问题。”

此刻，Ahmadi及Zhang正于测验考试将这一要领进级为一种更普适的算法来提高实用价值，不仅可以处置惩罚二次函数，还有有三次函数。这将使步伐越发不变，并提高呆板进修使命的机能。

今朝，优化问题求解的难点不仅于在方针数比力多的多方针优化，甚至年夜范围多方针优化，动态多方针优化，偏好众方针优化，还有有计较求解的时效问题，东西的普适问题。于处置惩罚现实环境下的优化问题中，进一寸有一寸的欢乐。

编译来历：

https://www.quantamagazine.org/surprising-limits-discovered-in-quest-for-optimal-solutions-20211101/

雷峰网(公家号：雷峰网)

雷峰网版权文章，未经授权禁止转载。详情见转载须知。

-米兰·(milan)中国官方网站