普林斯頓研究「最小值」：平方和的破局，二次和三次優化問題的極限

• 2021 年 11 月 25 日
• AI

編譯 | 吳彤

編輯 | 維克多

優化問題的同義詞是找到解決方案，有無數學者想探求在最短時間內，找到最好的解。但最新研究指出，一些二次優化問題，例如變數對可以相互作用的公式，只能「按部就班」找到局部最優解。換句話說「不存在快速計算方法」。

好消息是，另一項研究發現對於三次多項式下的優化問題，存在快速求解的方法。具體而言，可以通過使用平方和檢驗（sum-of-squares test）找到某些多項式的最低點，進而搜索三次函數的局部最優解。

兩項研究時隔兩天，出自於同一研究團隊：普林斯頓大學的Amir Ali Ahmadi和他的前學生Jeffrey Zhang。

Amir Ali Ahmadi和他的前學生Jeffrey Zhang

兩篇「涉事」論文分別是：

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

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

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

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

貢獻：證明了在三次多項式中，某些優化問題容易處理，且給出了尋找三次多項式局部極小值的一個充要條件。

論文鏈接：//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正在嘗試將這一方法升級為一種更普適的演算法來提高實用價值，不僅可以處理二次函數，還有三次函數。這將使程式更加穩定，並提高機器學習任務的性能。

目前，優化問題求解的難點不僅在於目標數比較多的多目標優化，甚至大規模多目標優化，動態多目標優化，偏好眾目標優化，還有計算求解的時效問題，工具的普適問題。在處理實際情況下的優化問題中，進一寸有一寸的歡喜。

編譯來源：

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

雷峰網