東營(yíng)網(wǎng)站制作公司杭州網(wǎng)站
朕四季常服, 不過(guò)八套. — 大明王朝1566 道長(zhǎng)
🏰代碼及環(huán)境配置：請(qǐng)參考 環(huán)境配置和代碼運(yùn)行!
上一節(jié)我們介紹了數(shù)值優(yōu)化的基本概念, 讓大家對(duì)最優(yōu)化問(wèn)題有了基本的理解.
那么對(duì)于一個(gè)具體的問(wèn)題, 我們應(yīng)該如何求解呢? 這一節(jié)我們將介紹幾個(gè)基本的求解方法, 為了簡(jiǎn)化問(wèn)題, 我們會(huì)基于無(wú)約束凸優(yōu)化問(wèn)題來(lái)做解釋. 因?yàn)闊o(wú)約束凸優(yōu)化問(wèn)題, 梯度為0的點(diǎn)(極值點(diǎn)), 就是全局最優(yōu)解.
最優(yōu)化問(wèn)題的求解是一個(gè)迭代的過(guò)程, 從初始點(diǎn)(初始解) x 0 x_0 x0?開(kāi)始, 通過(guò)迭代方法(梯度下降法, 牛頓法等)逐步更新 x i x_i xi?, 直至逼近最優(yōu)解 x ? x^* x?.
上圖形象的展示了這個(gè)迭代的過(guò)程, 從初始解start點(diǎn)開(kāi)始, 逐步迭代至最優(yōu)解. 在這個(gè)1維問(wèn)題上, 迭代方向只有左和右(-, +), 我們?nèi)绾未_定迭代的方向和步長(zhǎng)呢? 或者更高維度的問(wèn)題里, 如何確定每個(gè)維度的方向和步長(zhǎng)呢?
接下來(lái)我們介紹幾個(gè)基礎(chǔ)的最優(yōu)化求解方法
5.2.1 梯度下降法(Gradient Descent)
梯度是指函數(shù)在某一點(diǎn)上沿著各個(gè)方向的偏導(dǎo)數(shù), 梯度代表著當(dāng)前點(diǎn)函數(shù)值增加最快的方向. 定義如下:
? f ( x 1 , x 2 , . . . x n ) = ( ? f ? x 1 , ? f ? x 2 , . . . ? f ? x n ) \nabla f(x_1,x_2,...x_n)=\left(\frac{\partial f}{\partial x_1}, \frac{\partial f}{\partial x_2},... \frac{\partial f}{\partial x_n} \right) ?f(x1?,x2?,...xn?)=(?x1??f?,?x2??f?,...?xn??f?)
梯度下降法是最常采用的方法之一, 它會(huì)沿著梯度下降(相反)的方向逐步調(diào)整決策變量. 它的更新公式如下:
x k + 1 = x k ? α k ? f ( x k ) .? x^{k+1}=x^k-\alpha_k \nabla f\left(x^k\right) \text {. } xk+1=xk?αk??f(xk).?
其中 x k x^k xk是第k次迭代x的值, α k \alpha_k αk?是第k次迭代的步長(zhǎng).
這張動(dòng)圖可以清晰的展示梯度下降法更新的過(guò)程, 每次迭代, 都沿著梯度方向, 更新迭代點(diǎn).
(1) 梯度下降法的優(yōu)點(diǎn)
- 實(shí)現(xiàn)簡(jiǎn)單：梯度下降法只需要計(jì)算函數(shù)的梯度（一階導(dǎo)數(shù)），實(shí)現(xiàn)簡(jiǎn)單，計(jì)算量相對(duì)較小。
- 廣泛適用：對(duì)于大多數(shù)連續(xù)可導(dǎo)的凸函數(shù)，梯度下降法都能找到局部最小值。當(dāng)目標(biāo)函數(shù)是凸函數(shù)時(shí)，梯度下降法的解是全局解。
- 參數(shù)更新方向合理：梯度下降法基于梯度信息選擇參數(shù)更新方向，這是函數(shù)在當(dāng)前位置的最快下降方向。
(2) 梯度下降法的缺點(diǎn)
- 收斂速度慢：梯度下降法是一階收斂算法，在接近最小值點(diǎn)時(shí)，梯度值會(huì)變得很小，導(dǎo)致收斂速度變慢。此外，直線搜索時(shí)可能會(huì)產(chǎn)生“之字形”下降路徑，進(jìn)一步降低收斂速度。
- 對(duì)初始值敏感：不同的初始值可能導(dǎo)致算法收斂到不同的局部最小值。
- 需要手動(dòng)調(diào)整學(xué)習(xí)率：學(xué)習(xí)率的選擇對(duì)算法的收斂速度和效果有很大影響。學(xué)習(xí)率過(guò)大可能導(dǎo)致算法發(fā)散，學(xué)習(xí)率過(guò)小則收斂速度過(guò)慢。
- 可能陷入局部極值點(diǎn)：如果目標(biāo)函數(shù)不是凸函數(shù)而是含有多個(gè)極小值點(diǎn)的函數(shù)，梯度下降法可能會(huì)陷入局部極小點(diǎn)而無(wú)法繼續(xù)下降。
5.2.2 牛頓法(Newton Method)
梯度下降法是一種一階導(dǎo)數(shù)迭代的方法, 收斂速度較慢. 如果利用二階導(dǎo)數(shù), 是不是能夠更快的逼近極值點(diǎn)呢?
牛頓法就是二階導(dǎo)數(shù)迭代的代表, 它綜合了一階和二階信息, 能夠快速收斂. 更新公式如下:
x k + 1 = x k ? ? 2 f ( x k ) ? 1 ? f ( x k ) x^{k+1}=x^k-\nabla^2 f\left(x^k\right)^{-1} \nabla f\left(x^k\right) xk+1=xk??2f(xk)?1?f(xk)
其中 ? 2 \nabla^2 ?2是指函數(shù)的Hessian矩陣, 是一個(gè)由函數(shù)的二階偏導(dǎo)數(shù)構(gòu)成的矩陣,定義如下:
? 2 f ( x 1 , x 2 , . . . x n ) = [ ? 2 f ? x 1 2 ? 2 f ? x 1 ? x 2 ? ? 2 f ? x 1 ? x n ? 2 f ? x 2 ? x 1 ? 2 f ? x 2 2 ? ? 2 f ? x 2 ? x n ? ? ? ? ? 2 f ? x n ? x 1 ? 2 f ? x n ? x 2 ? ? 2 f ? x n 2 ] \nabla^2 f(x_1,x_2,...x_n)=\left[\begin{array}{cccc}\frac{\partial^2 f}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1 \partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_1 \partial x_n} \\\frac{\partial^2 f}{\partial x_2 \partial x_1} & \frac{\partial^2 f}{\partial x_2^2} & \cdots & \frac{\partial^2 f}{\partial x_2 \partial x_n} \\\vdots & \vdots & \ddots & \vdots \\\frac{\partial^2 f}{\partial x_n \partial x_1} & \frac{\partial^2 f}{\partial x_n \partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_n^2}\end{array}\right] ?2f(x1?,x2?,...xn?)= ??x12??2f??x2??x1??2f???xn??x1??2f???x1??x2??2f??x22??2f???xn??x2??2f????????x1??xn??2f??x2??xn??2f???xn2??2f?? ?
? 2 f ( x k ) ? 1 \nabla^2 f\left(x^k\right)^{-1} ?2f(xk)?1是Hessian矩陣的逆矩陣, 可以看出牛頓法的計(jì)算量很大.
這張圖展示了梯度下降法(綠)和牛頓法(紅)的對(duì)比, 可以看到牛頓法要高效的多.
(1) 牛頓法的優(yōu)點(diǎn)
- 收斂速度快：牛頓法利用了函數(shù)的二階導(dǎo)數(shù)信息（Hessian矩陣），能夠在接近最小值點(diǎn)時(shí)快速收斂。特別是對(duì)于正定二次函數(shù)，牛頓法的一步迭代即可達(dá)到最優(yōu)解。
- 對(duì)初始值不敏感：相對(duì)于梯度下降法，牛頓法對(duì)初始值的依賴性較小，更有可能找到全局最優(yōu)解。
- 全局視野：牛頓法在選擇下降方向時(shí)，不僅考慮當(dāng)前位置的梯度，還考慮未來(lái)位置梯度的變化趨勢(shì)，因此具有更強(qiáng)的全局視野。
(2) 牛頓法的缺點(diǎn)
- 計(jì)算量大：牛頓法需要計(jì)算函數(shù)的二階導(dǎo)數(shù)（Hessian矩陣）及其逆矩陣，計(jì)算量相對(duì)較大
- 對(duì)Hessian矩陣要求高：Hessian矩陣必須正定，否則算法可能無(wú)法收斂。此外，當(dāng)Hessian矩陣接近奇異時(shí)，算法可能會(huì)變得不穩(wěn)定。
- 函數(shù)要求苛刻：牛頓法要求目標(biāo)函數(shù)二階連續(xù)可微，且Hessian矩陣可逆.
因?yàn)榕ｎD法的計(jì)算量較大, 為了克服這個(gè)問(wèn)題, 擬牛頓法應(yīng)運(yùn)而生. 擬牛頓法不直接去計(jì)算Hessian矩陣, 而是通過(guò) 近似Hessian矩陣的逆矩陣 來(lái)達(dá)到類似牛頓法的效果. 常見(jiàn)的擬牛頓法有BFGS等.
下一節(jié)我們將使用梯度下降法和牛頓法, 解決Rosenbrock Function, 讓大家更直觀的看到兩種方法的區(qū)別.
參考鏈接
- 劉浩洋. 最優(yōu)化: 建模, 算法與理論. 高等教育出版社, 2020.
🏎?自動(dòng)駕駛小白說(shuō)官網(wǎng)：https://www.helloxiaobai.cn