深圳2020年7月16日 /美通社/ -- 近期，大巖資本成立七周年慶在深圳成功舉辦。周年慶上量化投資基金經理黃鉑博士結合生活實踐中的案例為大家深入淺出闡釋了最優化算法的前世今生。
從實際生活中最基礎的應用切入，黃鉑博士將抽象的算法概念生動化，解釋了什麼叫最優化問題、凸優化及算法分類、機器學習與人工智慧應用。
黃博士的分享內容較長，我們將分上、中、下三篇連載推出，本文為中篇。
凸優化問題中的最優值
凸優化的關鍵字在「凸」，我們要定義什麼樣的東西是凸的呢？看上圖，藍色區域代表優化問題裡變量可以取值的空間，當取值空間是凸的時候，這是凸優化的一個必要條件。那麼什麼樣的集合是凸的集合？我們在集合裡任意選兩點X、Y，我們將這兩點連成線，從X到Y的這條線上所有的點都必須在集合裡，只有這樣的集合才叫做凸的集合。相反，如果有任意一個點在集合之外，那就不是凸的集合。而對於一個凸優化的問題而言，它所有的變量取值必須來自於凸的集合。
所以說，對於所有的離散優化而言，它都不是凸優化的，因為它的取值其實不是一個空間，而是一個洞一個洞的，它是很多洞的集合。所以，通常求解這類問題時很困難，很多時候我們求解的都是一個局部最優值。在實際生活中，我們求解的都是局部優化的問題，而這類問題在所有問題中所佔比例是非常非常低的。
如果把整個集合看作一個優化問題的集合，那麼相對來講，比較小的一部分是屬於連續優化的問題，其他更大的區域屬於離散優化的問題，而在連續優化的空間裡只有很小的一部分屬於凸優化的問題。所以說，在最優化的領域裡，我們真正解決的只是實際問題中的冰山一角。
凸優化問題的經典算法
對於凸優化的問題，黃鉑博士給大家介紹幾個最經典的算法。
第一個算法，最速下降法。首先，我們看下圖，這是一個等高線，我們可以把它理解為我們的高樓，每一個圈代表一層，最中心是最高的位置，我們最終目標是用最快的方式上到中心位置。那麼，最速下降法是怎麼做的呢？比如從一樓上二樓可以有多種方法，很明顯我們從垂直方向往上跳，在局部來看是最快的，然後以這樣的方法上到最高層。
最速下降法有哪些特點呢？每一步都做到了最優化，但很遺憾的是，對於整個算法而言，它並不是非常好的算法。因為它的收斂速度是線性收斂，線性收斂對於最優化算法而言是一種比較慢的算法，但也是凸優化裡最自然的一個算法，最早被應用。
第二個算法，共軛梯度法。與最速下降法相比較（看下圖），綠色的線是最速下降法的迭代，從最外層到中心點可能需要五步迭代，但是共軛梯度法可能只需兩步迭代（紅色線）。
共軛梯度法最大特點是汲取前面的經驗再做下一步的動作，比如從四樓上五樓，我們會考慮方向是否最佳，汲取之前跳過的四步經驗，再探索新的方向往上跳。從數學的角度來講，每一步前進的方向和之前所有走過的路徑都是垂直的，因為這樣的性質，共軛梯度法的收斂速度遠遠高於最速下降法。
第三個算法，牛頓法。前面兩種算法，從數學的角度講，他們只用到了一階導數的信息，對於牛頓法而言，它不僅僅用到了局部一階導的信息，還用到了二階導的信息。相比前面兩種算法，牛頓法的每一步，它在決定下一步怎麼走時，不僅考慮當前的下降速度是否足夠快，還會考慮走完這一步後，下一步坡度是否更陡，下一步是否更難走。可見，牛頓法所看到的區間會更遠，收斂速度更快，屬於二階收斂速度。如果最速下降法需要100步的話，牛頓法就只需要10步，但也正因為牛頓法使用了二階導的信息，所以它需要更多的運算量。
第四個算法，擬牛頓法。1970年，Broyden、Fletcher、Goldfarb、Shanno四人幾乎同一時間發表了論文，對於傳統的牛頓法進行了非常好的改進，這個算法叫擬牛頓法，它的收斂速度與牛頓法相似，但是它不再需要計算二階導數，所以每一步的迭代速度大大增加。它是通過當前一階導數的信息去近似二階導數的信息，因此整個運算速度大幅度增加。由於這個算法是四個人幾乎同一時間發現的，所以也叫BFGS算法。下圖中的照片是他們四個人聚在普林斯頓時拍的，很幸運的是，Goldfarb是我博士時期的導師。
實際生活中，被應用最廣的兩種算法，一個是BFGS，另一個就是共軛梯度法。這兩種算法經常會出現在很多的程序包裡或者開原始碼裡，如果使用在大規模的優化問題或者成千上萬個變量的問題中，也會有非常好的效果。（待續下篇）