iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 13
0
AI & Data

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

Day 13 : 一維搜尋法(line search)

在求解非線性規劃問題時,我們利用迭代的方式來求解,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,決定方向與步長就變得重要了。方向為朝函數極值的方向,而步長則可透過解析法與數值法求得。今天要來繼續討論昨天提到的Interval reducing method。

等區間搜尋法(Equal interval search)

  1. 給定初始值,https://chart.googleapis.com/chart?cht=tx&chl=a_0, https://chart.googleapis.com/chart?cht=tx&chl=%5Cdelta, https://chart.googleapis.com/chart?cht=tx&chl=%5Cepsilon
  2. 比較相鄰之點的函數值大小,直到 https://chart.googleapis.com/chart?cht=tx&chl=f(a_n)%20%3C%20f(a_%7Bn%2B1%7D)
    https://chart.googleapis.com/chart?cht=tx&chl=%5Calpha_l%20%3D%20a_%7Bn-1%7D%2C%20%5Calpha_u%20%3D%20a_%7Bn%2B1%7D,又https://chart.googleapis.com/chart?cht=tx&chl=a_n%20%3D%20a_0%20%2B%20n%5Cdelta%2C%20n%20%3D%200%2C%201%2C%20%5Cdots
    https://chart.googleapis.com/chart?cht=tx&chl=%5CRightarrow%20I%20%3D%20%5Calpha_u%20-%20%5Calpha_l%20%3D%202%5Cdelta
  3. 縮小區間https://chart.googleapis.com/chart?cht=tx&chl=I,ex:令https://chart.googleapis.com/chart?cht=tx&chl=%5Cdelta'%20%3D%20%5Cfrac%7B%5Cdelta%7D%7B10%7D,再由https://chart.googleapis.com/chart?cht=tx&chl=%20%5Calpha_l開始,重複步驟2,直到https://chart.googleapis.com/chart?cht=tx&chl=I%20%3C%20%5Cepsilonhttps://chart.googleapis.com/chart?cht=tx&chl=%5CRightarrow%20%5Calpha%5E%7B%5Cast%7D%20%3D%20%5Cfrac%7B%5Calpha_l%20%2B%20%5Calpha_u%7D%7B2%7D

黃金分割法(Golden section search)

可視為一種可變區間的搜尋法,此法分兩階段,

  1. 找出單峰函數的區間黃金比(https://chart.googleapis.com/chart?cht=tx&chl=golden%20ratio%20%3D%201.618)
    區間分割方式:
    https://chart.googleapis.com/chart?cht=tx&chl=q%20%3D%200, https://chart.googleapis.com/chart?cht=tx&chl=%5Calpha_0%20%3D%20%5Cdelta%20%2B%20(1.618)%5E%7B0%7D%20%5Cdelta
    https://chart.googleapis.com/chart?cht=tx&chl=q%20%3D%201, https://chart.googleapis.com/chart?cht=tx&chl=%5Calpha_1%20%3D%20%5Calpha_0%20%2B%20(1.618)%5E%7B1%7D%20%5Cdelta
    https://chart.googleapis.com/chart?cht=tx&chl=q%20%3D%202, https://chart.googleapis.com/chart?cht=tx&chl=%5Calpha_2%20%3D%20%5Calpha_1%20%2B%20(1.618)%5E%7B2%7D%20%5Cdelta
    https://chart.googleapis.com/chart?cht=tx&chl=%5Cdots
    https://chart.googleapis.com/chart?cht=tx&chl=%5CRightarrow%20%5Calpha_q%20%3D%20%5Csum_%7Bj%3D0%7D%5E%7Bq%7D%20%5Cdelta%20(1.618)%5E%7Bj%7D, https://chart.googleapis.com/chart?cht=tx&chl=q%3D0%2C1%2C2%2C%20%5Cdots
    比較相鄰2點函數值,直到https://chart.googleapis.com/chart?cht=tx&chl=f(%5Calpha_%7Bq-1%7D)%20%3C%20f(%5Calpha_%7Bq-2%7D)https://chart.googleapis.com/chart?cht=tx&chl=f(%5Calpha_%7Bq-1%7D)%20%3C%20f(%5Calpha_q)
    https://chart.googleapis.com/chart?cht=tx&chl=%5CRightarrowhttps://chart.googleapis.com/chart?cht=tx&chl=%5Calpha_u%20%3D%20%5Calpha_q, https://chart.googleapis.com/chart?cht=tx&chl=%5Calpha_l%20%3D%20%5Calpha_%7Bq-2%7D
    起始不確定區間為,https://chart.googleapis.com/chart?cht=tx&chl=I%20%3D%20%5Calpha_u%20-%20%5Calpha_l%20%3D%20%5Calpha_q%20-%20%5Calpha_%7Bq-2%7D
  2. 縮減區間
    舉例說明,
    https://ithelp.ithome.com.tw/upload/images/20190914/20119600rWDpM7on6y.jpg

上一篇
Day 12 : 無限制條件之非線性規劃問題
下一篇
Day 14 : 非線性規劃問題求解演算法 (1/2)
系列文
連接數學與現實世界的橋樑 -- 數學建模30

尚未有邦友留言

立即登入留言