Day 14 : 非線性規劃問題求解演算法 (1/2)

第 11 屆 iThome 鐵人賽

DAY 14

AI & Data

連接數學與現實世界的橋樑 -- 數學建模系列第 14 篇

11th鐵人賽最陡下降法共軛梯度法

spidyjames

2019-09-15 17:27:18

2489 瀏覽

分享至

在前面我們提到了關於非線性規劃問題求解的基本演算法步驟(如下圖)，接著介紹了在這演算法中的兩個元素，搜尋方向( $\bar d$ )及步長( $\bar {\alpha}$ )，以及兩者的求法。現在有了這些工具，可以帶入一些常見的演算法了，如最陡下降法、共軛梯度法、牛頓法、類牛頓法、DFP法以及BFGS法。

最陡下降法(steepest descent method)

又稱梯度法(gradient method)，使用梯度決定搜尋方向 $\bar d$ ，並令 $\bar d = - \bar C$ ，其中 $- \bar C = - \nabla f$ , $-\bar C^{(k)} = - \nabla f(\bar X^{(k)})$
梯度法的正交性
連續的兩個最陡下降方向或梯度方向將相互正交 $\Rightarrow$ $\bar C^{(k)} \cdot \bar C^{(k+1)} = 0$
梯度法之步驟:

給定 $\bar X^{(0)}$ ，令 $k = 0$ ，選取收斂參數 $\epsilon > 0$
計算梯度 $\bar C^{(k)} = \nabla f(\bar X^{(k)})$ (可用有限差分法來求導數)
計算梯度大小 $|| \bar C^{(k)} ||$ ，如 $|| \bar C^{(k)} || < \epsilon$ ，則停止迭代程序，且 $\bar X^{\ast} = \bar X^{(k)}$ 即為最小點，否則繼續下一步
令目前變數 $\bar X^{(k)}$ 之搜尋方向 $\bar d^{(k)} = - \bar C^{(k)}$
計算步長 $\alpha_k$ 使函數 $f(\bar X^{(k)} + \alpha_k \bar d^{(k)})$ (為 $\alpha$ 的函數)有最小值(可用先前提過的任何一維搜尋法來決定) $\alpha_k$
更新變數為 $\bar X^{(k+1)} = \bar X({(k)}) + \alpha_k \bar d^{(k)}$ ，令 $k = k + 1$ ，回到步驟2

共軛梯度法(conjugate gradient method)

優勢:可加快收斂速度

共軛梯度法之步驟:

給定 $\bar X^{(0)}$ ，令 $k = 0$ ，選定 $\epsilon > 0$ ，計算 $\bar d^{(0)} = - \bar C^{(0)} = - \nabla f(\bar X^{(0)})$
檢驗收斂與否，如 $|| \bar C^{(0)} || < \epsilon$ ，則停止，否則跳到步驟5
計算 $\bar C^{(k)} = \nabla f(\bar X^{(k)})$
計算 $|| \bar C^{(k)} ||$ ，如 $|| \bar C^{(k)} || < \epsilon$ ，則停止，否則繼續
計算新的共軛梯度方向 $\bar d^{(k)} = - \bar C^{(k)} + \beta_k \bar d^{(k-1)}$ , $https://chart.googleapis.com/chart?cht=tx&chl=%5Cbeta_k%20%3D%20(%5Cfrac%7B%7C%7C%5Cbar%20C%5E%7B(k)%7D%7C%7C%7D%7B%7C%7C%5Cbar%20C%5E%7B(k-1)%7D%7C%7C%7D)%5E2$
計算步長 $\alpha_k$ ，使得 $f(\bar X^{(k)} + \alpha_k \bar d^{(k)})$ 為最小
更新變數為 $\bar X^{(k+1)} = \bar X^{(k)} + \alpha_k \bar d^{(k)}$ ，令 $k = k + 1$ ，回到步驟2