多目標(biāo)優(yōu)化是各個(gè)領(lǐng)域中普遍存在的問題，每個(gè)目標(biāo)不可能都同時(shí)達(dá)到最優(yōu)，并且有現(xiàn)實(shí)應(yīng)用的時(shí)效。各個(gè)因素必須各有權(quán)重。在困局中，平方和方法可用來尋找局部最優(yōu)解。

編譯 | 吳彤

編輯 | 維克多

生命是一連串的優(yōu)化問題，下班后尋找回家的最快路線；去商店的路上權(quán)衡最佳性價(jià)比，甚至當(dāng)睡前“玩手機(jī)”的安排，都可以看做優(yōu)化問題。

優(yōu)化問題的同義詞是找到解決方案，有無數(shù)學(xué)者想探求在最短時(shí)間內(nèi)，找到最好的解。但最新研究指出，一些二次優(yōu)化問題，例如變量對(duì)可以相互作用的公式，只能“按部就班”找到局部最優(yōu)解。換句話說“不存在快速計(jì)算方法”。

好消息是，另一項(xiàng)研究發(fā)現(xiàn)對(duì)于三次多項(xiàng)式下的優(yōu)化問題，存在快速求解的方法。具體而言，可以通過使用平方和檢驗(yàn)（sum-of-squares test）找到某些多項(xiàng)式的最低點(diǎn)，進(jìn)而搜索三次函數(shù)的局部最優(yōu)解。

兩項(xiàng)研究時(shí)隔兩天，出自于同一研究團(tuán)隊(duì)：普林斯頓大學(xué)的Amir Ali Ahmadi和他的前學(xué)生Jeffrey Zhang。

Amir Ali Ahmadi和他的前學(xué)生Jeffrey Zhang

Amir Ali Ahmadi是普林斯頓大學(xué)運(yùn)籌學(xué)與金融工程系教授，在加入普林斯頓大學(xué)之前，曾是IBM Watson研究中心的Goldstine研究員，其對(duì)優(yōu)化理論，動(dòng)力學(xué)和控制的計(jì)算以及算法和復(fù)雜度有很深的造詣。Jeffrey Zhang是卡內(nèi)基梅隆大學(xué)的客座教授，研究領(lǐng)域包括博弈論、計(jì)算復(fù)雜性、多項(xiàng)式優(yōu)化等等。

兩篇“涉事”論文分別是：

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

貢獻(xiàn)：判定二次函數(shù)在(無界)多胞形（ polyhedron）上是否有局極小值，以及判定四次多項(xiàng)式是否有局部極小值屬于NP難。

論文鏈接：https://arxiv.org/abs/2008.05558

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

貢獻(xiàn)：證明了在三次多項(xiàng)式中，某些優(yōu)化問題容易處理，且給出了尋找三次多項(xiàng)式局部極小值的一個(gè)充要條件。

論文鏈接：https://arxiv.org/abs/2008.06148

這兩篇論文，一前一后，證明了復(fù)雜性計(jì)算研究的現(xiàn)狀：某種類型的優(yōu)化問題很容易解決，而某種類型的問題則必然很難解決。更進(jìn)一步，他們?yōu)閺慕鹑诘阶詣?dòng)系統(tǒng)等各個(gè)領(lǐng)域的優(yōu)化問題確定了新的邊界。

1

生活中的優(yōu)化問題

假設(shè)一家汽車廠只生產(chǎn)兩種車型，便宜版和豪華版。豪華版的售價(jià)高于便宜車，但生產(chǎn)成本更高，生產(chǎn)時(shí)間也更長(zhǎng)。那么兩種車型應(yīng)該各生產(chǎn)多少?

這個(gè)問題可以轉(zhuǎn)化為一個(gè)用多項(xiàng)式表達(dá)的優(yōu)化求解問題。

首先，這個(gè)問題可以分解為三個(gè)元素：

• 有待優(yōu)化的可量化變量，比如必須生產(chǎn)的汽車數(shù)量。

• 一些約束條件，比如預(yù)算和生產(chǎn)能力。

• 一個(gè)叫做目標(biāo)函數(shù)的東西，目標(biāo)函數(shù)的功能是給定決策變量，輸出解決方案（優(yōu)化值）。

汽車?yán)觾H僅是一個(gè)簡(jiǎn)單的優(yōu)化問題，變量之間沒有相互作用，優(yōu)化值可以通過求解線性函數(shù)得到。但現(xiàn)實(shí)中的問題往往非常復(fù)雜。

例如，如何選擇最佳航空樞紐。樞紐航班波強(qiáng)度和密度的經(jīng)濟(jì)性與機(jī)場(chǎng)設(shè)備設(shè)施、機(jī)型、航班結(jié)構(gòu)等等有關(guān)，只有在這幾個(gè)方面取得最佳配合的情況下，樞紐中轉(zhuǎn)才能真正發(fā)揮作用。

樞紐航空公司在組織航班的時(shí)候，希望航班波的強(qiáng)度和密度越大越好，這樣就可以提高單位時(shí)間內(nèi)的中轉(zhuǎn)效率，與此帶來的單位時(shí)間內(nèi)航班量過大，中轉(zhuǎn)人數(shù)過多的高峰處理量，給機(jī)場(chǎng)和航空公司帶來了巨大的運(yùn)營壓力和成本壓力。也就是說，航空公司在樞紐機(jī)場(chǎng)的處理能力接近峰值后，會(huì)出現(xiàn)快速衰退，導(dǎo)致操作成本快速提高和服務(wù)質(zhì)量急劇下降。

當(dāng)然，還有很多問題可能比這更復(fù)雜。變量之間的三階交互作用需要用到更復(fù)雜的函數(shù)。每一步函數(shù)復(fù)雜性都要為更廣泛的問題建模，但是這種復(fù)雜性是有代價(jià)的，它可能計(jì)算不出最優(yōu)解。

2

退而求其次，找出最佳“故障”

現(xiàn)代優(yōu)化理論發(fā)展于第二次世界大戰(zhàn)期間（1939年至1945），當(dāng)時(shí)一位名叫 George Dantzig的科學(xué)家設(shè)計(jì)了一個(gè)尋找線性優(yōu)化問題解的程序，被應(yīng)用到美國國防部采購飛機(jī)和海外運(yùn)送物資的戰(zhàn)時(shí)實(shí)踐上。

在接下來的幾十年里，研究人員跟隨George的領(lǐng)導(dǎo)，開發(fā)了更快的算法，為日益復(fù)雜的現(xiàn)實(shí)問題找到最佳解決方案。

但在20世紀(jì)80年代，這些進(jìn)步遇到了一個(gè)不可逾越的障礙。研究人員發(fā)現(xiàn)，解決優(yōu)化問題的快速算法不可能存在。他們認(rèn)為，這些問題從根本上來說太復(fù)雜了。

如果無法獲得最優(yōu)解決方案，還能怎么辦? 近似解，或者“局部”最優(yōu)解。

局部最優(yōu)解可能并不代表最佳結(jié)果，但它們比任何類似解都要好。它們是做出決策的“足夠好”的方式，比如每輛車要生產(chǎn)多少輛，不能通過對(duì)某些變量的微小調(diào)整來改進(jìn)，只有大規(guī)模的重組才能導(dǎo)致絕對(duì)最好的結(jié)果，但對(duì)于大問題，這種計(jì)算過于密集。

鑒于這一切，自20世紀(jì)90年代初以來，研究人員一直試圖確定：是否存在一種快速找到局部最優(yōu)解的方法。

3

二次方程的壞消息

當(dāng)研究人員想要確定一個(gè)問題在計(jì)算上是否難以解決時(shí)，他們通常會(huì)將其等同于一些已知復(fù)雜性的問題。比如如果知道A問題很難解決，可以證明，解決問題B將為解決A提供一種方法。

在Amir Ali Ahmadi和Jeffrey Zhang的第一篇論文中，他們將二次優(yōu)化的挑戰(zhàn)與所謂的最大穩(wěn)定集問題進(jìn)行了匹配。當(dāng)然，最大穩(wěn)定集問題是一個(gè)著名的并且可證明的難題。

“穩(wěn)定集”（stable set）是指圖表中兩個(gè)節(jié)點(diǎn)沒有直接相連的任何節(jié)點(diǎn)列表。最大穩(wěn)定集問題要即找到圖表中最大規(guī)模的穩(wěn)定集。即使你只想知道是否存在一個(gè)給定大小的穩(wěn)定集，但要確定這個(gè)答案，計(jì)算相當(dāng)復(fù)雜。

去年6月，Ahmadi和Zhang將最大穩(wěn)定集問題重新定義為搜索局部最優(yōu)解的特殊情況。他們提出了一種將穩(wěn)定集問題表示為二次優(yōu)化問題的方法。于是，尋找一個(gè)具有一定規(guī)模的穩(wěn)定集就變成了尋找這個(gè)優(yōu)化問題的局部最優(yōu)解的問題。

但是他們知道，依然沒有一種很快速的計(jì)算方法來找到這些穩(wěn)定集，這意味著，對(duì)于二次函數(shù)優(yōu)化問題，局部最優(yōu)解和真正最優(yōu)解一樣難以找到。

“直覺上，局部最優(yōu)解應(yīng)該更容易，但出乎意料的是，他們二人證明兩種解都很難。”荷蘭國家數(shù)學(xué)和計(jì)算機(jī)科學(xué)研究所（CWI）的Monique Laurent說。

4

三次方程的好消息

Ahmadi和Zhang排除了總能找到某些二次優(yōu)化問題局部最優(yōu)解的有效算法的存在。與此同時(shí)，他們想知道：在不包含約束條件的簡(jiǎn)化條件下能夠解決三次優(yōu)化問題么?

三次多項(xiàng)式在許多實(shí)際方法中都很重要。它們?yōu)樗伎甲兞恐g的三階相互作用提供了一個(gè)數(shù)學(xué)框架。增加一種關(guān)系使得關(guān)系的清晰度提高，從而極大地改善機(jī)器學(xué)習(xí)性能，比如在文本挖掘中，大家希望算法能從大數(shù)據(jù)集中提取意義。

例如，你向計(jì)算機(jī)輸入一段文本，并要求它確定這段文本的內(nèi)容。計(jì)算機(jī)注意到“蘋果”這個(gè)詞經(jīng)常出現(xiàn)，但是沒有更多的信息，導(dǎo)致“蘋果”這個(gè)詞語仍有歧義。

可能是水果，也可能是公司，或者其他。

但如果“蘋果”和“橘子”同時(shí)出現(xiàn)，計(jì)算機(jī)會(huì)更加確定這是水果。但還是有可能出錯(cuò)，因?yàn)殚僮右部赡苁且患夜?。所以這時(shí)候引入第三個(gè)詞語，如“瓜”，即引入了立體關(guān)系，可能會(huì)更加確信文本談?wù)摰氖寝r(nóng)產(chǎn)品。

但是，清晰度的增加也帶來了復(fù)雜性。

從2019年初，Zhang就開始探索解決這個(gè)問題的不同方法，但被卡住了，直到Ahmadi建議他嘗試一種叫做平方和的技術(shù)，Ahmadi以前曾用這種技術(shù)解決其他優(yōu)化問題。

5

破局

“平方和”指的是一些多項(xiàng)式可以表示為其他多項(xiàng)式的平方和。例如：

平方和揭示了最初輸入的多項(xiàng)式的屬性。因?yàn)閷?shí)數(shù)的平方不可能為負(fù)，所以如果將一個(gè)多項(xiàng)式表示為平方和，證明它總是輸出一個(gè)非負(fù)值。這是一種快速的檢驗(yàn)方法。然而，這種方法在有約束的二次優(yōu)化問題中不起作用，這就是為什么Ahmadi和Zhang不能在他們的二次方程中利用它。

但是對(duì)于沒有約束的三次優(yōu)化問題，平方和成為尋找局部最優(yōu)最小解時(shí)的重要方法。如果將多項(xiàng)式函數(shù)的圖形描繪成一條浮動(dòng)在橫軸上方的曲線，它的最低點(diǎn)是對(duì)應(yīng)于變量的特定排列。

這種算法可以快速循環(huán)遍歷一系列輸入，反復(fù)測(cè)試多項(xiàng)式是否為平方和。此時(shí)，算法會(huì)將曲線向下拖動(dòng)，無限趨近于橫軸。此時(shí)，另一種算法可以快速表明低點(diǎn)的坐標(biāo)。

此時(shí)，Zhang和Ahmadi才將優(yōu)化問題向前推進(jìn)了一小步，他們的突破在于發(fā)現(xiàn)可以通過平方和檢驗(yàn)找到某些多項(xiàng)式的最低點(diǎn)，從而尋找三次函數(shù)的局部最優(yōu)解。

在像這樣的三次多項(xiàng)式的圖中，一端總是指向負(fù)無窮。所以三次方程不可能處處為正，可以用平方和檢驗(yàn)。但是Ahmadi和Zhang想出了一種方法，只關(guān)注曲線向上的那部分。

Zhang說：“對(duì)于三次函數(shù)求解的問題，我們總是可以把函數(shù)拖到我們想要的位置，解決了三次函數(shù)局部最優(yōu)解的重要理論問題?！?/span>

現(xiàn)在，Ahmadi和Zhang正在嘗試將這一方法升級(jí)為一種更普適的算法來提高實(shí)用價(jià)值，不僅可以處理二次函數(shù)，還有三次函數(shù)。這將使程序更加穩(wěn)定，并提高機(jī)器學(xué)習(xí)任務(wù)的性能。

目前，優(yōu)化問題求解的難點(diǎn)不僅在于目標(biāo)數(shù)比較多的多目標(biāo)優(yōu)化，甚至大規(guī)模多目標(biāo)優(yōu)化，動(dòng)態(tài)多目標(biāo)優(yōu)化，偏好眾目標(biāo)優(yōu)化，還有計(jì)算求解的時(shí)效問題，工具的普適問題。在處理實(shí)際情況下的優(yōu)化問題中，進(jìn)一寸有一寸的歡喜。

編譯來源：

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

雷峰網(wǎng)(公眾號(hào)：雷峰網(wǎng))

雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。