超越優化中的黑盒問題
譯者注
該文翻譯自SIAM NEWS上的文章Looking Beyond the Black Box in Optimization (只用於學術交流，嚴禁任何形式的商業轉載)。作者Paul Davis是伍斯特理工學院的一名數學榮休教授。該文寫於2016年10月3日，譯者才疏學淺，不到之處，多請見諒！
按：本文最初發佈於我的個人網站random walk，[附英文原文]。
優化相關內容可以閱讀專欄 隨機矩陣不隨機 共同組織者 @廖振宇博士和@凌澤南博士的文章
凌澤南：關於深度學習中地貌問題的不完整的回顧（一）
更多討論請關注專欄，後面會有進一步討論。
很多原因導致了優化問題的困難。但是對目標函數（objective function）的評估這樣一個問題的挑戰是否經常發生呢？計算一個數字有多難呢？
嗯，也許不「難」，但肯定很費時，計算上也非常昂貴。也許這些被最小化的量只能通過一些陳舊的遺留代碼塊來計算。或者它的評估可能要求代碼封裝在可能有專賣權的黑盒中。或者它可能需要使用複雜的、長時間運行的模擬，或許甚至對每個場景都進行一個完整的實驗。隨著全世界對最優需求的增長，所有這些真實的可能性也隨之出現了。
在2016年SIAM年會的一個受邀演講中，來自阿貢國家實驗室的Stefan Wild處理了這類優化問題。他強調挑戰的出現，是由於評估目標函數的計算成本壓倒了找到一個最優點的所有其他方面，而不是因為目標函數缺少導數。
例如，Wild和來自康奈爾大學的Christine Shoemaker已經描述了尋找最優抽水策略以減少地下水的有害廢物污染的問題：在一定範圍的抽水速率下運行的一系列水槽，可以注入純凈水或者抽除並處理受污染的水。比如說，15個水槽連續作業超過30年，將污染水集中在符合美國環境保護署標準的含水層，最低抽水成本是多少呢？評估一個簡單的場景就需要一個非常耗時的（45分鐘以上）地下水流模擬。
該模擬代碼太複雜以至於不能進行演算法微分，這涉及到處理代碼以產生新的能夠評估目標函數的特定導數的代碼。數值微分和遺傳演算法都會遇到同樣的計算成本瓶頸：單個函數評估所需的時間（也就是一次完整的地下水模擬）遠遠超出了所有其他方面的計算。
從哲學上講，Wild的方法是「充分利用小（make the most of little）」來使用選定點處的目標函數值，以確定下一個最小化步驟中的一個有效方向。他的設置是一個基於模型的置信區域，這是一個緊緻區域，在這個區域上目標函數可以通過二次（quadratic）近似來很好地建模。置信區域將隨著最小化步驟移動而增長或縮小。
為了最大限度利用（make the most）昂貴的目標函數評估，Wild選擇插值點，以使目標的二次模型中的近似誤差服從類Taylor約束。也就是說，函數近似中的誤差是由插值點間距測量的平方以及使用它的一次冪近似導數而產生的誤差所限的。這種模型被稱為完全線性的。並行考慮可以指導插值基函數的選擇。
由於他的陳述中還給出了各種相關方法的快速比較，所以Wild幾乎沒有時間來詳細說明完全線性模型所能提供的高效性。例如，擬合獨特的n變數二次型（在受污染的地下水例子中，n＝15個不同的抽運率+…）需要對目標進行(n+1)(n+2)/2次評估。完全線性模型的值依賴於較少的插值點，然而其梯度仍然指向較便宜的操作點方向。
相比於過高的目標函數評估成本，實現完全線性模型而滿足在插值點上的幾何條件的開銷以及建立目標模型的努力都是小變化。
在「使用較少的黑盒函數評估的情況下儘可能追求更低的最小值」時，Wild主張「在使用完全線性模型置信區域方法前應該充分利用儘可能多已知的結構」。例如，最小二乘問題就是最小化平方殘差和，其中一些可能是比較昂貴的計算。目標函數的梯度包括每個殘差和它們各自梯度的乘積。Wild使用相應二次型模型中的梯度來近似每個殘差項的梯度。對於最小絕對值問題，Wild指出，因為我們「知道奇點位置，所以我們可以使用遠離麻煩點的基於模型的近似」。
這些高效策略的價值何在呢？Wild說「我們越來越能夠優化幾乎所有的東西」。
進一步閱讀：
Wild, S.M., & Shoemaker, C. (2013). Global Convergence of Radial Basis Function Trust-Region Algorithms for Derivative-Free Optimization. SIAM Review, 55(2), 349-371.
推薦閱讀：