深圳2020年7月16日 /美通社/ -- 近期，大巖資本成立七周年慶在深圳成功舉辦。周年慶上量化投資基金經(jīng)理黃鉑博士結(jié)合生活實(shí)踐中的案例為大家深入淺出闡釋了最優(yōu)化算法的前世今生。
從實(shí)際生活中最基礎(chǔ)的應(yīng)用切入，黃鉑博士將抽象的算法概念生動(dòng)化，解釋了什么叫最優(yōu)化問(wèn)題、凸優(yōu)化及算法分類、機(jī)器學(xué)習(xí)與人工智能應(yīng)用。
黃博士的分享內(nèi)容較長(zhǎng)，我們將分上、中、下三篇連載推出，本文為中篇。
凸優(yōu)化問(wèn)題中的最優(yōu)值
凸優(yōu)化的關(guān)鍵字在“凸”，我們要定義什么樣的東西是凸的呢？看上圖，藍(lán)色區(qū)域代表優(yōu)化問(wèn)題里變量可以取值的空間，當(dāng)取值空間是凸的時(shí)候，這是凸優(yōu)化的一個(gè)必要條件。那么什么樣的集合是凸的集合？我們?cè)诩侠锶我膺x兩點(diǎn)X、Y，我們將這兩點(diǎn)連成線，從X到Y(jié)的這條線上所有的點(diǎn)都必須在集合里，只有這樣的集合才叫做凸的集合。相反，如果有任意一個(gè)點(diǎn)在集合之外，那就不是凸的集合。而對(duì)于一個(gè)凸優(yōu)化的問(wèn)題而言，它所有的變量取值必須來(lái)自于凸的集合。
所以說(shuō)，對(duì)于所有的離散優(yōu)化而言，它都不是凸優(yōu)化的，因?yàn)樗娜≈灯鋵?shí)不是一個(gè)空間，而是一個(gè)洞一個(gè)洞的，它是很多洞的集合。所以，通常求解這類問(wèn)題時(shí)很困難，很多時(shí)候我們求解的都是一個(gè)局部最優(yōu)值。在實(shí)際生活中，我們求解的都是局部?jī)?yōu)化的問(wèn)題，而這類問(wèn)題在所有問(wèn)題中所占比例是非常非常低的。
如果把整個(gè)集合看作一個(gè)優(yōu)化問(wèn)題的集合，那么相對(duì)來(lái)講，比較小的一部分是屬于連續(xù)優(yōu)化的問(wèn)題，其他更大的區(qū)域?qū)儆陔x散優(yōu)化的問(wèn)題，而在連續(xù)優(yōu)化的空間里只有很小的一部分屬于凸優(yōu)化的問(wèn)題。所以說(shuō)，在最優(yōu)化的領(lǐng)域里，我們真正解決的只是實(shí)際問(wèn)題中的冰山一角。
凸優(yōu)化問(wèn)題的經(jīng)典算法
對(duì)于凸優(yōu)化的問(wèn)題，黃鉑博士給大家介紹幾個(gè)最經(jīng)典的算法。
第一個(gè)算法，最速下降法。首先，我們看下圖，這是一個(gè)等高線，我們可以把它理解為我們的高樓，每一個(gè)圈代表一層，最中心是最高的位置，我們最終目標(biāo)是用最快的方式上到中心位置。那么，最速下降法是怎么做的呢？比如從一樓上二樓可以有多種方法，很明顯我們從垂直方向往上跳，在局部來(lái)看是最快的，然后以這樣的方法上到最高層。
最速下降法有哪些特點(diǎn)呢？每一步都做到了最優(yōu)化，但很遺憾的是，對(duì)于整個(gè)算法而言，它并不是非常好的算法。因?yàn)樗氖諗克俣仁蔷€性收斂，線性收斂對(duì)于最優(yōu)化算法而言是一種比較慢的算法，但也是凸優(yōu)化里最自然的一個(gè)算法，最早被應(yīng)用。
第二個(gè)算法，共軛梯度法。與最速下降法相比較（看下圖），綠色的線是最速下降法的迭代，從最外層到中心點(diǎn)可能需要五步迭代，但是共軛梯度法可能只需兩步迭代（紅色線）。
共軛梯度法最大特點(diǎn)是汲取前面的經(jīng)驗(yàn)再做下一步的動(dòng)作，比如從四樓上五樓，我們會(huì)考慮方向是否最佳，汲取之前跳過(guò)的四步經(jīng)驗(yàn)，再探索新的方向往上跳。從數(shù)學(xué)的角度來(lái)講，每一步前進(jìn)的方向和之前所有走過(guò)的路徑都是垂直的，因?yàn)檫@樣的性質(zhì)，共軛梯度法的收斂速度遠(yuǎn)遠(yuǎn)高于最速下降法。
第三個(gè)算法，牛頓法。前面兩種算法，從數(shù)學(xué)的角度講，他們只用到了一階導(dǎo)數(shù)的信息，對(duì)于牛頓法而言，它不僅僅用到了局部一階導(dǎo)的信息，還用到了二階導(dǎo)的信息。相比前面兩種算法，牛頓法的每一步，它在決定下一步怎么走時(shí)，不僅考慮當(dāng)前的下降速度是否足夠快，還會(huì)考慮走完這一步后，下一步坡度是否更陡，下一步是否更難走。可見(jiàn)，牛頓法所看到的區(qū)間會(huì)更遠(yuǎn)，收斂速度更快，屬于二階收斂速度。如果最速下降法需要100步的話，牛頓法就只需要10步，但也正因?yàn)榕ｎD法使用了二階導(dǎo)的信息，所以它需要更多的運(yùn)算量。
第四個(gè)算法，擬牛頓法。1970年，Broyden、Fletcher、Goldfarb、Shanno四人幾乎同一時(shí)間發(fā)表了論文，對(duì)于傳統(tǒng)的牛頓法進(jìn)行了非常好的改進(jìn)，這個(gè)算法叫擬牛頓法，它的收斂速度與牛頓法相似，但是它不再需要計(jì)算二階導(dǎo)數(shù)，所以每一步的迭代速度大大增加。它是通過(guò)當(dāng)前一階導(dǎo)數(shù)的信息去近似二階導(dǎo)數(shù)的信息，因此整個(gè)運(yùn)算速度大幅度增加。由于這個(gè)算法是四個(gè)人幾乎同一時(shí)間發(fā)現(xiàn)的，所以也叫BFGS算法。下圖中的照片是他們四個(gè)人聚在普林斯頓時(shí)拍的，很幸運(yùn)的是，Goldfarb是我博士時(shí)期的導(dǎo)師。
實(shí)際生活中，被應(yīng)用最廣的兩種算法，一個(gè)是BFGS，另一個(gè)就是共軛梯度法。這兩種算法經(jīng)常會(huì)出現(xiàn)在很多的程序包里或者開(kāi)源代碼里，如果使用在大規(guī)模的優(yōu)化問(wèn)題或者成千上萬(wàn)個(gè)變量的問(wèn)題中，也會(huì)有非常好的效果。（待續(xù)下篇）
