0
編譯 | 吳彤
編輯 | 維克多
優(yōu)化問題的同義詞是找到解決方案，有無數(shù)學(xué)者想探求在最短時間內(nèi)，找到最好的解。但最新研究指出，一些二次優(yōu)化問題，例如變量對可以相互作用的公式，只能“按部就班”找到局部最優(yōu)解。換句話說“不存在快速計算方法”。
好消息是，另一項研究發(fā)現(xiàn)對于三次多項式下的優(yōu)化問題，存在快速求解的方法。具體而言，可以通過使用平方和檢驗（sum-of-squares test）找到某些多項式的最低點，進(jìn)而搜索三次函數(shù)的局部最優(yōu)解。
兩項研究時隔兩天，出自于同一研究團(tuán)隊：普林斯頓大學(xué)的Amir Ali Ahmadi和他的前學(xué)生Jeffrey Zhang。
Amir Ali Ahmadi和他的前學(xué)生Jeffrey Zhang
兩篇“涉事”論文分別是：
論文1：On the complexity of finding a local minimizer of a quadratic function over a polytope
貢獻(xiàn)：判定二次函數(shù)在(無界)多胞形（ polyhedron）上是否有局極小值，以及判定四次多項式是否有局部極小值屬于NP難。
論文鏈接：https://arxiv.org/abs/2008.05558
論文2：Complexity aspects of local minima and related notions
貢獻(xiàn)：證明了在三次多項式中，某些優(yōu)化問題容易處理，且給出了尋找三次多項式局部極小值的一個充要條件。
論文鏈接：https://arxiv.org/abs/2008.06148
這兩篇論文，一前一后，證明了復(fù)雜性計算研究的現(xiàn)狀：某種類型的優(yōu)化問題很容易解決，而某種類型的問題則必然很難解決。更進(jìn)一步，他們?yōu)閺慕鹑诘阶詣酉到y(tǒng)等各個領(lǐng)域的優(yōu)化問題確定了新的邊界。
假設(shè)一家汽車廠只生產(chǎn)兩種車型，便宜版和豪華版。豪華版的售價高于便宜車，但生產(chǎn)成本更高，生產(chǎn)時間也更長。那么兩種車型應(yīng)該各生產(chǎn)多少?
這個問題可以轉(zhuǎn)化為一個用多項式表達(dá)的優(yōu)化求解問題。
首先，這個問題可以分解為三個元素：
有待優(yōu)化的可量化變量，比如必須生產(chǎn)的汽車數(shù)量。
一些約束條件，比如預(yù)算和生產(chǎn)能力。
一個叫做目標(biāo)函數(shù)的東西，目標(biāo)函數(shù)的功能是給定決策變量，輸出解決方案（優(yōu)化值）。
汽車?yán)觾H僅是一個簡單的優(yōu)化問題，變量之間沒有相互作用，優(yōu)化值可以通過求解線性函數(shù)得到。但現(xiàn)實中的問題往往非常復(fù)雜。
例如，如何選擇最佳航空樞紐。樞紐航班波強度和密度的經(jīng)濟(jì)性與機場設(shè)備設(shè)施、機型、航班結(jié)構(gòu)等等有關(guān)，只有在這幾個方面取得最佳配合的情況下，樞紐中轉(zhuǎn)才能真正發(fā)揮作用。
樞紐航空公司在組織航班的時候，希望航班波的強度和密度越大越好，這樣就可以提高單位時間內(nèi)的中轉(zhuǎn)效率，與此帶來的單位時間內(nèi)航班量過大，中轉(zhuǎn)人數(shù)過多的高峰處理量，給機場和航空公司帶來了巨大的運營壓力和成本壓力。也就是說，航空公司在樞紐機場的處理能力接近峰值后，會出現(xiàn)快速衰退，導(dǎo)致操作成本快速提高和服務(wù)質(zhì)量急劇下降。
當(dāng)然，還有很多問題可能比這更復(fù)雜。變量之間的三階交互作用需要用到更復(fù)雜的函數(shù)。每一步函數(shù)復(fù)雜性都要為更廣泛的問題建模，但是這種復(fù)雜性是有代價的，它可能計算不出最優(yōu)解。
現(xiàn)代優(yōu)化理論發(fā)展于第二次世界大戰(zhàn)期間（1939年至1945），當(dāng)時一位名叫 George Dantzig的科學(xué)家設(shè)計了一個尋找線性優(yōu)化問題解的程序，被應(yīng)用到美國國防部采購飛機和海外運送物資的戰(zhàn)時實踐上。
在接下來的幾十年里，研究人員跟隨George的領(lǐng)導(dǎo)，開發(fā)了更快的算法，為日益復(fù)雜的現(xiàn)實問題找到最佳解決方案。
但在20世紀(jì)80年代，這些進(jìn)步遇到了一個不可逾越的障礙。研究人員發(fā)現(xiàn)，解決優(yōu)化問題的快速算法不可能存在。他們認(rèn)為，這些問題從根本上來說太復(fù)雜了。
如果無法獲得最優(yōu)解決方案，還能怎么辦? 近似解，或者“局部”最優(yōu)解。
局部最優(yōu)解可能并不代表最佳結(jié)果，但它們比任何類似解都要好。它們是做出決策的“足夠好”的方式，比如每輛車要生產(chǎn)多少輛，不能通過對某些變量的微小調(diào)整來改進(jìn)，只有大規(guī)模的重組才能導(dǎo)致絕對最好的結(jié)果，但對于大問題，這種計算過于密集。
鑒于這一切，自20世紀(jì)90年代初以來，研究人員一直試圖確定：是否存在一種快速找到局部最優(yōu)解的方法。
當(dāng)研究人員想要確定一個問題在計算上是否難以解決時，他們通常會將其等同于一些已知復(fù)雜性的問題。比如如果知道A問題很難解決，可以證明，解決問題B將為解決A提供一種方法。
在Amir Ali Ahmadi和Jeffrey Zhang的第一篇論文中，他們將二次優(yōu)化的挑戰(zhàn)與所謂的最大穩(wěn)定集問題進(jìn)行了匹配。當(dāng)然，最大穩(wěn)定集問題是一個著名的并且可證明的難題。
“穩(wěn)定集”（stable set）是指圖表中兩個節(jié)點沒有直接相連的任何節(jié)點列表。最大穩(wěn)定集問題要即找到圖表中最大規(guī)模的穩(wěn)定集。即使你只想知道是否存在一個給定大小的穩(wěn)定集，但要確定這個答案，計算相當(dāng)復(fù)雜。
去年6月，Ahmadi和Zhang將最大穩(wěn)定集問題重新定義為搜索局部最優(yōu)解的特殊情況。他們提出了一種將穩(wěn)定集問題表示為二次優(yōu)化問題的方法。于是，尋找一個具有一定規(guī)模的穩(wěn)定集就變成了尋找這個優(yōu)化問題的局部最優(yōu)解的問題。
但是他們知道，依然沒有一種很快速的計算方法來找到這些穩(wěn)定集，這意味著，對于二次函數(shù)優(yōu)化問題，局部最優(yōu)解和真正最優(yōu)解一樣難以找到。
“直覺上，局部最優(yōu)解應(yīng)該更容易，但出乎意料的是，他們二人證明兩種解都很難。”荷蘭國家數(shù)學(xué)和計算機科學(xué)研究所（CWI）的Monique Laurent說。
Ahmadi和Zhang排除了總能找到某些二次優(yōu)化問題局部最優(yōu)解的有效算法的存在。與此同時，他們想知道：在不包含約束條件的簡化條件下能夠解決三次優(yōu)化問題么?
三次多項式在許多實際方法中都很重要。它們?yōu)樗伎甲兞恐g的三階相互作用提供了一個數(shù)學(xué)框架。增加一種關(guān)系使得關(guān)系的清晰度提高，從而極大地改善機器學(xué)習(xí)性能，比如在文本挖掘中，大家希望算法能從大數(shù)據(jù)集中提取意義。
例如，你向計算機輸入一段文本，并要求它確定這段文本的內(nèi)容。計算機注意到“蘋果”這個詞經(jīng)常出現(xiàn)，但是沒有更多的信息，導(dǎo)致“蘋果”這個詞語仍有歧義。
可能是水果，也可能是公司，或者其他。
但如果“蘋果”和“橘子”同時出現(xiàn)，計算機會更加確定這是水果。但還是有可能出錯，因為橘子也可能是一家公司。所以這時候引入第三個詞語，如“瓜”，即引入了立體關(guān)系，可能會更加確信文本談?wù)摰氖寝r(nóng)產(chǎn)品。
但是，清晰度的增加也帶來了復(fù)雜性。
從2019年初，Zhang就開始探索解決這個問題的不同方法，但被卡住了，直到Ahmadi建議他嘗試一種叫做平方和的技術(shù)，Ahmadi以前曾用這種技術(shù)解決其他優(yōu)化問題。
“平方和”指的是一些多項式可以表示為其他多項式的平方和。例如：
平方和揭示了最初輸入的多項式的屬性。因為實數(shù)的平方不可能為負(fù)，所以如果將一個多項式表示為平方和，證明它總是輸出一個非負(fù)值。這是一種快速的檢驗方法。然而，這種方法在有約束的二次優(yōu)化問題中不起作用，這就是為什么Ahmadi和Zhang不能在他們的二次方程中利用它。
但是對于沒有約束的三次優(yōu)化問題，平方和成為尋找局部最優(yōu)最小解時的重要方法。如果將多項式函數(shù)的圖形描繪成一條浮動在橫軸上方的曲線，它的最低點是對應(yīng)于變量的特定排列。
這種算法可以快速循環(huán)遍歷一系列輸入，反復(fù)測試多項式是否為平方和。此時，算法會將曲線向下拖動，無限趨近于橫軸。此時，另一種算法可以快速表明低點的坐標(biāo)。
此時，Zhang和Ahmadi才將優(yōu)化問題向前推進(jìn)了一小步，他們的突破在于發(fā)現(xiàn)可以通過平方和檢驗找到某些多項式的最低點，從而尋找三次函數(shù)的局部最優(yōu)解。
在像
這樣的三次多項式的圖中，一端總是指向負(fù)無窮。所以三次方程不可能處處為正，可以用平方和檢驗。但是Ahmadi和Zhang想出了一種方法，只關(guān)注曲線向上的那部分。
Zhang說：“對于三次函數(shù)求解的問題，我們總是可以把函數(shù)拖到我們想要的位置，解決了三次函數(shù)局部最優(yōu)解的重要理論問題。”
現(xiàn)在，Ahmadi和Zhang正在嘗試將這一方法升級為一種更普適的算法來提高實用價值，不僅可以處理二次函數(shù)，還有三次函數(shù)。這將使程序更加穩(wěn)定，并提高機器學(xué)習(xí)任務(wù)的性能。
目前，優(yōu)化問題求解的難點不僅在于目標(biāo)數(shù)比較多的多目標(biāo)優(yōu)化，甚至大規(guī)模多目標(biāo)優(yōu)化，動態(tài)多目標(biāo)優(yōu)化，偏好眾目標(biāo)優(yōu)化，還有計算求解的時效問題，工具的普適問題。在處理實際情況下的優(yōu)化問題中，進(jìn)一寸有一寸的歡喜。
編譯來源：
https://www.quantamagazine.org/surprising-limits-discovered-in-quest-for-optimal-solutions-20211101/
雷峰網(wǎng)(公眾號：雷峰網(wǎng))
