iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 14
0
AI & Data

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

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

在前面我們提到了關於非線性規劃問題求解的基本演算法步驟(如下圖),接著介紹了在這演算法中的兩個元素,搜尋方向(https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20d)及步長(https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20%7B%5Calpha%7D),以及兩者的求法。現在有了這些工具,可以帶入一些常見的演算法了,如最陡下降法、共軛梯度法、牛頓法、類牛頓法、DFP法以及BFGS法。
https://ithelp.ithome.com.tw/upload/images/20190915/20119600FAwdcyi5DD.jpg

最陡下降法(steepest descent method)

又稱梯度法(gradient method),使用梯度決定搜尋方向https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20d,並令https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20d%20%3D%20-%20%5Cbar%20C,其中https://chart.googleapis.com/chart?cht=tx&chl=-%20%5Cbar%20C%20%3D%20-%20%5Cnabla%20f, https://chart.googleapis.com/chart?cht=tx&chl=-%5Cbar%20C%5E%7B(k)%7D%20%3D%20-%20%5Cnabla%20f(%5Cbar%20X%5E%7B(k)%7D)
梯度法的正交性
連續的兩個最陡下降方向或梯度方向將相互正交 https://chart.googleapis.com/chart?cht=tx&chl=%5CRightarrow https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20C%5E%7B(k)%7D%20%5Ccdot%20%5Cbar%20C%5E%7B(k%2B1)%7D%20%3D%200
梯度法之步驟:

  1. 給定https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20X%5E%7B(0)%7D,令https://chart.googleapis.com/chart?cht=tx&chl=k%20%3D%200,選取收斂參數https://chart.googleapis.com/chart?cht=tx&chl=%5Cepsilon%20%3E%200
  2. 計算梯度https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20C%5E%7B(k)%7D%20%3D%20%5Cnabla%20f(%5Cbar%20X%5E%7B(k)%7D)(可用有限差分法來求導數)
  3. 計算梯度大小https://chart.googleapis.com/chart?cht=tx&chl=%7C%7C%20%5Cbar%20C%5E%7B(k)%7D%20%7C%7C,如https://chart.googleapis.com/chart?cht=tx&chl=%7C%7C%20%5Cbar%20C%5E%7B(k)%7D%20%7C%7C%20%3C%20%5Cepsilon,則停止迭代程序,且https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20X%5E%7B%5Cast%7D%20%3D%20%5Cbar%20X%5E%7B(k)%7D即為最小點,否則繼續下一步
  4. 令目前變數https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20X%5E%7B(k)%7D之搜尋方向https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20d%5E%7B(k)%7D%20%3D%20-%20%5Cbar%20C%5E%7B(k)%7D
  5. 計算步長https://chart.googleapis.com/chart?cht=tx&chl=%5Calpha_k使函數https://chart.googleapis.com/chart?cht=tx&chl=f(%5Cbar%20X%5E%7B(k)%7D%20%2B%20%5Calpha_k%20%5Cbar%20d%5E%7B(k)%7D)(為https://chart.googleapis.com/chart?cht=tx&chl=%5Calpha的函數)有最小值(可用先前提過的任何一維搜尋法來決定)https://chart.googleapis.com/chart?cht=tx&chl=%5Calpha_k
  6. 更新變數為https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20X%5E%7B(k%2B1)%7D%20%3D%20%5Cbar%20X(%7B(k)%7D)%20%2B%20%5Calpha_k%20%5Cbar%20d%5E%7B(k)%7D,令https://chart.googleapis.com/chart?cht=tx&chl=k%20%3D%20k%20%2B%201,回到步驟2

共軛梯度法(conjugate gradient method)

優勢:可加快收斂速度
https://ithelp.ithome.com.tw/upload/images/20190915/201196001yDO6kiYpU.jpg
共軛梯度法之步驟:

  1. 給定https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20X%5E%7B(0)%7D,令https://chart.googleapis.com/chart?cht=tx&chl=k%20%3D%200,選定https://chart.googleapis.com/chart?cht=tx&chl=%5Cepsilon%20%3E%200,計算https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20d%5E%7B(0)%7D%20%3D%20-%20%5Cbar%20C%5E%7B(0)%7D%20%3D%20-%20%5Cnabla%20f(%5Cbar%20X%5E%7B(0)%7D)
  2. 檢驗收斂與否,如https://chart.googleapis.com/chart?cht=tx&chl=%7C%7C%20%5Cbar%20C%5E%7B(0)%7D%20%7C%7C%20%3C%20%5Cepsilon,則停止,否則跳到步驟5
  3. 計算https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20C%5E%7B(k)%7D%20%3D%20%5Cnabla%20f(%5Cbar%20X%5E%7B(k)%7D)
  4. 計算https://chart.googleapis.com/chart?cht=tx&chl=%7C%7C%20%5Cbar%20C%5E%7B(k)%7D%20%7C%7C,如https://chart.googleapis.com/chart?cht=tx&chl=%7C%7C%20%5Cbar%20C%5E%7B(k)%7D%20%7C%7C%20%3C%20%5Cepsilon,則停止,否則繼續
  5. 計算新的共軛梯度方向https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20d%5E%7B(k)%7D%20%3D%20-%20%5Cbar%20C%5E%7B(k)%7D%20%2B%20%5Cbeta_k%20%5Cbar%20d%5E%7B(k-1)%7D, 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
  6. 計算步長https://chart.googleapis.com/chart?cht=tx&chl=%5Calpha_k,使得https://chart.googleapis.com/chart?cht=tx&chl=f(%5Cbar%20X%5E%7B(k)%7D%20%2B%20%5Calpha_k%20%5Cbar%20d%5E%7B(k)%7D)為最小
  7. 更新變數為https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20X%5E%7B(k%2B1)%7D%20%3D%20%5Cbar%20X%5E%7B(k)%7D%20%2B%20%5Calpha_k%20%5Cbar%20d%5E%7B(k)%7D,令https://chart.googleapis.com/chart?cht=tx&chl=k%20%3D%20k%20%2B%201,回到步驟2

上一篇
Day 13 : 一維搜尋法(line search)
下一篇
Day 15 : 非線性規劃問題求解演算法 (2/2)
系列文
連接數學與現實世界的橋樑 -- 數學建模30

尚未有邦友留言

立即登入留言