iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 15
0
AI & Data

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

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

今天我們繼續來介紹非線性規劃問題的求解方法,

牛頓法(Newton method)

特色:使用目標函數的二階導數來決定搜尋方向
演算法步驟:

  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),如https://chart.googleapis.com/chart?cht=tx&chl=%7C%7C%20%5Cbar%20C%5E%7B(k)%7D%20%7C%7C%20%3C%20%5Cepsilon,則停止迭代程序,否則繼續
  3. 計算https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20H%5E%7B(k)%7D(%5Cbar%20X%5E%7B(k)%7D)%20,亦即計算目前變數https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20X%5E%7B(k)%7D之Hessian matrix
  4. 計算搜尋方向https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20d%5E%7B(k)%7D%20%3D%20-%5B%5Cbar%20H%5E%7B(k)%7D%5D%5E%7B-1%7D%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)為最小
  6. 更新變數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

牛頓法的缺點

  1. 要計算到2階導數
  2. 需確認反矩陣存在

梯度法、共軛梯度法與牛頓法的比較
https://ithelp.ithome.com.tw/upload/images/20190916/20119600sMEtgyjWMi.jpg

準牛頓法(Quasi-Newton method)

將以一階導數的計算來近似或代替Hessian matrix,或其反矩陣的計算,使得準牛頓法兼具梯度法與牛頓法的優點。
在此我們介紹兩種準牛頓法,DFP法與BFGS法。

DFP法(Daviden-Fletcher-Powell)

建議搜尋方向https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20d%5E%7B(k)%7D如下:
https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20d%5E%7B(k)%7D%20%3D%20-%5Cbar%20A%5E%7B(k)%7D%20%5Cbar%20C%5E%7B(k)%7D
(1)當https://chart.googleapis.com/chart?cht=tx&chl=k%20%3D%200,可令https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20A%5E%7B(0%20)%7D%20%3D%20%5Cbar%20I(單位矩陣)
(2)當https://chart.googleapis.com/chart?cht=tx&chl=k%20%5Cge%201,每次迭代更新https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20A%5E%7B(k)%7D如下:
https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20A%5E%7B(k%2B1)%7D%20%3D%20%5Cbar%20A%5E%7B(k)%7D%20%2B%20%5Cbar%20B%5E%7B(k)%7D%20%2B%20%5Cbar%20C%5E%7B(k)%7D
其中,
https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20B%5E%7B(k)%7D%20%3D%20%5Cfrac%7B%5Cbar%20s%5E%7B(k)%7D%20%5Cbar%20s%5E%7B(k)%5E%7BT%7D%7D%7D%7B(%5Cbar%20s%5E%7B(k)%7D%20%5Cbar%20y%5E%7B(k)%7D)%7D%7D ; https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20C%5E%7B(k)%7D%20%3D%20%5Cfrac%7B%5Cbar%20z%5E%7B(k)%7D%20%5Cbar%20z%5E%7B(k)%5E%7BT%7D%7D%7D%7B(%5Cbar%20y%5E%7B(k)%7D%20%5Cbar%20z%5E%7B(k)%7D)%7D
https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20s%5E%7B(k)%7D%20%3D%20%5Calpha_k%20%5Cbar%20d%5E%7B(k)%7D ; https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20y%5E%7B(k)%7D%20%3D%20%5Cbar%20c%5E%7B(k%2B1)%7D%20-%20%5Cbar%20c%5E%7B(k)%7D
https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20c%5E%7B(k%2B1)%7D%20%3D%20%5Cnabla%20f(%5Cbar%20x%5E%7B(k%2B1)%7D) ; https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20z%5E%7B(k)%7D%20%3D%20%5Cbar%20A%5E%7B(k)%7D%20%5Cbar%20y%5E%7B(k)%7D

BFGS法(Broyden-Fletcher-Goldford-shanno)

此法經由求解線性方程式https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20H%5E%7B(k)%7D%20%5Cbar%20d%5E%7B(k)%7D%20%3D%20-%20%5Cbar%20c%5E%7B(k)%7D以求得搜尋方向https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20d%5E%7B(k)%7D,其中https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20H%5E%7B(k)%7D的計算式如下:
(1)當https://chart.googleapis.com/chart?cht=tx&chl=k%20%3D%200,可令https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20H%5E%7B(0)%7D%20%3D%20%5Cbar%20I(單位矩陣)
(2)當https://chart.googleapis.com/chart?cht=tx&chl=k%20%5Cge%201, https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20H%5E%7B(k)%7D更新如下,
https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20H%5E%7B(k%2B1)%7D%20%3D%20%5Cbar%20H%5E%7B(k)%7D%20%2B%20%5Cbar%20D%5E%7B(k)%7D%20%2B%20%5Cbar%20E%5E%7B(k)%7D
其中,
https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20D%5E%7B(k)%7D%20%3D%20%5Cfrac%7B%5Cbar%20y%5E%7B(k)%7D%20%5Cbar%20y%5E%7B(k)%5E%7BT%7D%7D%7D%7B%5Cbar%20y%5E%7B(k)%7D%20%5Cbar%20s%5E%7B(k)%7D%7D ; https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20E%5E%7B(k)%7D%20%3D%20%5Cfrac%7B%5Cbar%20c%5E%7B(k)%7D%20%5Cbar%20c%5E%7B(k)%5E%7BT%7D%7D%7D%7B%5Cbar%20c%5E%7B(k)%7D%20%5Cbar%20d%5E%7B(k)%7D%7D
https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20s%5E%7B(k)%7D%20%3D%20%5Calpha_k%20%5Cbar%20d%5E%7B(k)%7D ; https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20y%5E%7B(k)%7D%20%3D%20%5Cbar%20c%5E%7B(k%2B1)%7D%20-%20%5Cbar%20c%5E%7B(k)%7D
https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20c%5E%7B(k%2B1)%7D%20%3D%20%5Cnabla%20f(%5Cbar%20X%5E%7B(k%2B1)%7D)
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)


上一篇
Day 14 : 非線性規劃問題求解演算法 (1/2)
下一篇
Day 16 : 可以表現過程演變的模型 -- 動態模型
系列文
連接數學與現實世界的橋樑 -- 數學建模30

尚未有邦友留言

立即登入留言