近期,大巖資本成立七周年慶在深圳成功舉辦。周年慶上量化投資基金經(jīng)理黃鉑博士結(jié)合生活實踐中的案例為大家深入淺出闡釋了最優(yōu)化算法的前世今生。

從實際生活中最基礎(chǔ)的應(yīng)用切入,黃鉑博士將抽象的算法概念生動化,解釋了什么叫最優(yōu)化問題、凸優(yōu)化及算法分類、機(jī)器學(xué)習(xí)與人工智能應(yīng)用。

黃博士的分享內(nèi)容較長,我們將分上、中、下三篇連載推出,本文為中篇。

凸優(yōu)化問題中的最優(yōu)值

凸優(yōu)化的關(guān)鍵字在“凸”,我們要定義什么樣的東西是凸的呢?看上圖,藍(lán)色區(qū)域代表優(yōu)化問題里變量可以取值的空間,當(dāng)取值空間是凸的時候,這是凸優(yōu)化的一個必要條件。那么什么樣的集合是凸的集合?我們在集合里任意選兩點(diǎn)X、Y,我們將這兩點(diǎn)連成線,從X到Y(jié)的這條線上所有的點(diǎn)都必須在集合里,只有這樣的集合才叫做凸的集合。相反,如果有任意一個點(diǎn)在集合之外,那就不是凸的集合。而對于一個凸優(yōu)化的問題而言,它所有的變量取值必須來自于凸的集合。

所以說,對于所有的離散優(yōu)化而言,它都不是凸優(yōu)化的,因為它的取值其實不是一個空間,而是一個洞一個洞的,它是很多洞的集合。所以,通常求解這類問題時很困難,很多時候我們求解的都是一個局部最優(yōu)值。在實際生活中,我們求解的都是局部優(yōu)化的問題,而這類問題在所有問題中所占比例是非常非常低的。

如果把整個集合看作一個優(yōu)化問題的集合,那么相對來講,比較小的一部分是屬于連續(xù)優(yōu)化的問題,其他更大的區(qū)域?qū)儆陔x散優(yōu)化的問題,而在連續(xù)優(yōu)化的空間里只有很小的一部分屬于凸優(yōu)化的問題。所以說,在最優(yōu)化的領(lǐng)域里,我們真正解決的只是實際問題中的冰山一角。

凸優(yōu)化問題的經(jīng)典算法

對于凸優(yōu)化的問題,黃鉑博士給大家介紹幾個最經(jīng)典的算法。

第一個算法,最速下降法。首先,我們看下圖,這是一個等高線,我們可以把它理解為我們的高樓,每一個圈代表一層,最中心是最高的位置,我們最終目標(biāo)是用最快的方式上到中心位置。那么,最速下降法是怎么做的呢?比如從一樓上二樓可以有多種方法,很明顯我們從垂直方向往上跳,在局部來看是最快的,然后以這樣的方法上到最高層。

最速下降法有哪些特點(diǎn)呢?每一步都做到了最優(yōu)化,但很遺憾的是,對于整個算法而言,它并不是非常好的算法。因為它的收斂速度是線性收斂,線性收斂對于最優(yōu)化算法而言是一種比較慢的算法,但也是凸優(yōu)化里最自然的一個算法,最早被應(yīng)用。

第二個算法,共軛梯度法。與最速下降法相比較看下圖,綠色的線是最速下降法的迭代,從最外層到中心點(diǎn)可能需要五步迭代,但是共軛梯度法可能只需兩步迭代紅色線。

共軛梯度法最大特點(diǎn)是汲取前面的經(jīng)驗再做下一步的動作,比如從四樓上五樓,我們會考慮方向是否最佳,汲取之前跳過的四步經(jīng)驗,再探索新的方向往上跳。從數(shù)學(xué)的角度來講,每一步前進(jìn)的方向和之前所有走過的路徑都是垂直的,因為這樣的性質(zhì),共軛梯度法的收斂速度遠(yuǎn)遠(yuǎn)高于最速下降法。

第三個算法,牛頓法。前面兩種算法,從數(shù)學(xué)的角度講,他們只用到了一階導(dǎo)數(shù)的信息,對于牛頓法而言,它不僅僅用到了局部一階導(dǎo)的信息,還用到了二階導(dǎo)的信息。相比前面兩種算法,牛頓法的每一步,它在決定下一步怎么走時,不僅考慮當(dāng)前的下降速度是否足夠快,還會考慮走完這一步后,下一步坡度是否更陡,下一步是否更難走?？梢?牛頓法所看到的區(qū)間會更遠(yuǎn),收斂速度更快,屬于二階收斂速度。如果最速下降法需要100步的話,牛頓法就只需要10步,但也正因為牛頓法使用了二階導(dǎo)的信息,所以它需要更多的運(yùn)算量。

第四個算法,擬牛頓法。1970年,Broyden、Fletcher、Goldfarb、Shanno四人幾乎同一時間發(fā)表了論文,對于傳統(tǒng)的牛頓法進(jìn)行了非常好的改進(jìn),這個算法叫擬牛頓法,它的收斂速度與牛頓法相似,但是它不再需要計算二階導(dǎo)數(shù),所以每一步的迭代速度大大增加。它是通過當(dāng)前一階導(dǎo)數(shù)的信息去近似二階導(dǎo)數(shù)的信息,因此整個運(yùn)算速度大幅度增加。由于這個算法是四個人幾乎同一時間發(fā)現(xiàn)的,所以也叫BFGS算法。下圖中的照片是他們四個人聚在普林斯頓時拍的,很幸運(yùn)的是,Goldfarb是我博士時期的導(dǎo)師。

實際生活中,被應(yīng)用最廣的兩種算法,一個是BFGS,另一個就是共軛梯度法。這兩種算法經(jīng)常會出現(xiàn)在很多的程序包里或者開源代碼里,如果使用在大規(guī)模的優(yōu)化問題或者成千上萬個變量的問題中,也會有非常好的效果。