深圳2020年7月15日 /美通社/ -- 近期，大巖資本成立七周年慶在深圳成功舉辦。周年慶上量化投資基金經(jīng)理黃鉑博士結(jié)合生活實(shí)踐中的案例，深入淺出闡釋了最優(yōu)化算法的前世今生。
從實(shí)際生活中最基礎(chǔ)的應(yīng)用切入，黃鉑博士將抽象的算法概念生動(dòng)化，解釋了什么叫最優(yōu)化問(wèn)題、凸優(yōu)化及算法分類(lèi)、機(jī)器學(xué)習(xí)與人工智能應(yīng)用。
黃博士的分享內(nèi)容較長(zhǎng)，我們將分上、中、下三篇連載推出，本文為上篇。
最優(yōu)化問(wèn)題及基礎(chǔ)應(yīng)用
人生不如意之事十之八九，想達(dá)到我們想要達(dá)到的目標(biāo)時(shí)，通常都有各種各樣的限制。那么所謂最優(yōu)化問(wèn)題，就是指用最優(yōu)的方式去平衡理想與現(xiàn)實(shí)之間的關(guān)系。以簡(jiǎn)單的郵差送信問(wèn)題為例，郵差從A出發(fā)，送信到BCD，最后回到A。郵差每天必須經(jīng)過(guò)BCD，而且每個(gè)點(diǎn)每天只能經(jīng)過(guò)一次，在這樣的約束條件下，他的目標(biāo)函數(shù)是盡可能以最短的時(shí)間完成送信。這個(gè)問(wèn)題非常簡(jiǎn)單，只要把所有的路徑枚舉出來(lái)，然后取最短時(shí)間的方式即可。
根據(jù)前面的例子，我們嚴(yán)格的將目標(biāo)函數(shù)分為兩大類(lèi)。第一類(lèi)是最大化，包括最大化盈利，最大化效率。另一類(lèi)是最小化，包括最小化費(fèi)用、時(shí)間和錯(cuò)誤率。在金融行業(yè)，我們可以最大化預(yù)測(cè)股價(jià)的正確率，也可以最小化費(fèi)用、最小化時(shí)間和錯(cuò)誤率。當(dāng)然，我們可以同時(shí)最大化盈利，最小化費(fèi)用和時(shí)間。所以通常在很多的優(yōu)化問(wèn)題中，這兩種任務(wù)可以組合起來(lái)出現(xiàn)在同一個(gè)問(wèn)題框架下，這就是對(duì)于目標(biāo)函數(shù)的定義。
最優(yōu)化問(wèn)題的兩大類(lèi)：連續(xù)優(yōu)化與離散優(yōu)化
關(guān)于約束條件，理想很美好，現(xiàn)實(shí)很骨感，在現(xiàn)實(shí)生活中，我們會(huì)遇到比如預(yù)算有限、時(shí)間有限、外部強(qiáng)制性條件等各種各樣的問(wèn)題，與目標(biāo)函數(shù)一樣，這些限制條件不是單一存在的，也可能同時(shí)存在同一個(gè)問(wèn)題里，對(duì)于某一個(gè)優(yōu)化問(wèn)題來(lái)講，限制條件越復(fù)雜，求解就越困難。基于此，我們簡(jiǎn)單根據(jù)它的約束條件以及目標(biāo)函數(shù)變量類(lèi)型將最優(yōu)化問(wèn)題分成兩大類(lèi)，連續(xù)優(yōu)化和離散優(yōu)化。
連續(xù)優(yōu)化正如圖上所畫(huà)，線中間沒(méi)有斷點(diǎn)，而離散優(yōu)化的變量取值，是一個(gè)不連續(xù)的記錄，就如同一開(kāi)始講的郵差送信問(wèn)題。兩類(lèi)相較而言，離散優(yōu)化會(huì)更難解決，因?yàn)殡x散優(yōu)化多了一條限制條件 -- 不連續(xù)的集合。很多時(shí)候，我們要求我們的變量是一個(gè)整數(shù)，或者來(lái)自一個(gè)給定的區(qū)間，所以說(shuō)離散優(yōu)化會(huì)比連續(xù)優(yōu)化更難解，而兩種算法也會(huì)有非常大的不一樣。
從學(xué)術(shù)角度而言，連續(xù)優(yōu)化與離散優(yōu)化對(duì)應(yīng)的是兩個(gè)比較獨(dú)立的學(xué)科，離散優(yōu)化可能更多的應(yīng)用于統(tǒng)計(jì)、大數(shù)據(jù)相關(guān)的場(chǎng)景，連續(xù)優(yōu)化則會(huì)跟計(jì)算機(jī)密碼學(xué)相關(guān)，更多的與我們現(xiàn)實(shí)生活中的運(yùn)籌優(yōu)化應(yīng)用相關(guān)。
從目標(biāo)函數(shù)出發(fā)，它的最優(yōu)值也分為兩類(lèi)，局部最優(yōu)和全局最優(yōu)。我們看圖中黃色的點(diǎn)，在局部區(qū)域內(nèi)是最低的，我們管這個(gè)值叫做局部最優(yōu)值，但是當(dāng)我們看整個(gè)圖時(shí)，紅色的點(diǎn)才是最低的，所以這個(gè)點(diǎn)我們叫全局最優(yōu)值。通常來(lái)說(shuō)，取局部最優(yōu)值是相較容易的，因?yàn)榛旧夏阒恍枰此R近一小部分的信息就可以準(zhǔn)確判斷是否局部最優(yōu)，而在現(xiàn)實(shí)應(yīng)用中，其實(shí)僅僅知道局部最優(yōu)值就足以解決很多問(wèn)題。而更難的問(wèn)題在于全局最優(yōu)值，因?yàn)榍疤崾悄阈枰吹秸麄€(gè)畫(huà)面。
所以，對(duì)于這一類(lèi)問(wèn)題，我們目前沒(méi)有一個(gè)特別好的解決方法?，F(xiàn)實(shí)生活中，我們會(huì)有比較多的方法去求局部最優(yōu)值，而往往我們找到的幾乎跟實(shí)際上的全局最優(yōu)值不一樣。但有一個(gè)問(wèn)題是例外，這類(lèi)問(wèn)題它具有比較好的性質(zhì)，只要找到局部最優(yōu)值，它就肯定是全局最優(yōu)值，這類(lèi)問(wèn)題就叫凸優(yōu)化。（未完待續(xù)）
