iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 12
0
AI & Data

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

Day 12 : 無限制條件之非線性規劃問題

今天我們將討論非線性規劃問題,這類問題更接近實際物理世界,缺乏較好的一般性方法,也就是說,每一個問題都是"客製化"的,也因此就算想用非常複雜的一般化方法來建立模型供大量情境使用也是很難的。

接下來幾天我們會從無限制條件的問題出發,並介紹一些相關的數值方法,然後就結束最佳化模型這個主題。

General algorithm

求解的基本概念

利用搜尋的方式逐步找到最佳解
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%5CDelta%20%5Cbar%20X%5E%7B(k)%7D
https://chart.googleapis.com/chart?cht=tx&chl=k%3D0%2C%201%2C%202%2C%20%5Cdots(遞迴次數)
以分量表示,
https://chart.googleapis.com/chart?cht=tx&chl=x_%7Bi%7D%5E%7B(k%2B1)%7D%20%3D%20x_%7Bi%7D%5E%7B(k)%7D%20%2B%20%5CDelta%20x_%7Bi%7D%5E%7B(k)%7D
https://chart.googleapis.com/chart?cht=tx&chl=i%3D1%2C%20%5Cdots%20%2C%20n(設計變數的數目)
https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20X%5E%7B(0)%7D : 代表數值法的起始點,通常會以合理猜測來取得。
https://chart.googleapis.com/chart?cht=tx&chl=%5CDelta%20%5Cbar%20X%5E%7B(k)%7D : 當前設計變數https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20X%5E%7B(k)%7D之改變量

https://chart.googleapis.com/chart?cht=tx&chl=%5CDelta%20%5Cbar%20X%5E%7B(k)%7D可以分解成兩個部分 https://chart.googleapis.com/chart?cht=tx&chl=%5CRightarrow%20%5CDelta%20%5Cbar%20X%5E%7B(k)%7D%20%3D%20%5Calpha_k%20%5Cbar%20d%5E%7B(k)%7D, https://chart.googleapis.com/chart?cht=tx&chl=%5Calpha_k%20%3E%200
https://chart.googleapis.com/chart?cht=tx&chl=%5Calpha_k : 決定在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 : 決定搜尋的方向

演算法步驟

  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
  2. 檢查演算法是否滿足終止條件,是的話停止運算,否的話則繼續。
  3. 計算下一搜尋方向https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20d%5E%7B(k)%7D
  4. https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20d%5E%7B(k)%7D方向上計算最佳步長https://chart.googleapis.com/chart?cht=tx&chl=%5Calpha_k, https://chart.googleapis.com/chart?cht=tx&chl=%5Calpha_k%20%3E%200
  5. 更新設計變數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%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

descent direction(https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20d)的判斷

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=%5Cbar%20d%5E%7B(k)%7D 必須滿足,https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20C%5E%7B(k)%7D%20%5Cbar%20d%5E%7B(k)%7D%20%3C%200
ex:
檢驗在點(0, 0),方向https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20d%20%3D%20(1%2C%202)是否為https://chart.googleapis.com/chart?cht=tx&chl=f(%5Cbar%20X)%20%3D%20x_%7B1%7D%5E%7B2%7D%20-%20x_%7B1%7Dx_%7B2%7D%20%2B%202x_%7B2%7D%5E%7B2%7D%20-%202x_%7B1%7D%20%2B%20e%5E%7B(x_%7B1%7D%20%2B%20x_%7B2%7D)%7D之descent direction
[sol]:
https://chart.googleapis.com/chart?cht=tx&chl=%5Cnabla%20f%20%3D%20%5Cleft%20%5B%20%5Cbegin%7Barray%7D%7Bll%7D%202x_%7B1%7D%20-%20x_%7B2%7D%20-%202%20%2B%20e%5E%7B(x_%7B1%7D%20%2B%20x_%7B2%7D)%7D%20%5C%5C%20-x_%7B1%7D%20%2B%204x_%7B2%7D%20%2B%20e%5E%7B(x_%7B1%7D%20%2B%20x_%7B2%7D)%7D%20%5Cend%7Barray%7D%20%5Cright%20%5D%20%5CRightarrow%20%5Cnabla%20f(0%2C%200)%20%3D%20%5Cbar%20%7BC%7D%20(0%2C0)%20%3D%20(-1%2C%201)
https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20C%20%5Ccdot%20%5Cbar%20d%20%3D%20(-1%2C%201)%20%5Ccdot%20(1%2C%202)%20%3D%201%20%3E%200
https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20d不是descent direction

求解descent step(https://chart.googleapis.com/chart?cht=tx&chl=%5Calpha_k)

  1. 解析法
    https://ithelp.ithome.com.tw/upload/images/20190914/20119600jIe7SOKzx1.jpg
    https://ithelp.ithome.com.tw/upload/images/20190914/20119600R5scLhhlNK.jpg
    https://ithelp.ithome.com.tw/upload/images/20190914/20119600dsfXFwZucm.jpg
    https://ithelp.ithome.com.tw/upload/images/20190914/20119600ViAVj0FTDQ.jpg

  2. 數值法
    前提條件與概念

  • 單峰函數(unimodal function)
    一般情況而言,需先進行"劃界"(註1),以確定函數在https://chart.googleapis.com/chart?cht=tx&chl=%5Ba%2C%20b%5D為單峰。
    https://ithelp.ithome.com.tw/upload/images/20190914/2011960026y1DoRneJ.jpg
  • 不確定區間(interval of uncertainty)
    https://chart.googleapis.com/chart?cht=tx&chl=I%20%3D%20%5Calpha_u%20-%20%5Calpha_l https://chart.googleapis.com/chart?cht=tx&chl=%5Cequiv https://chart.googleapis.com/chart?cht=tx&chl=%5Calpha的上限 - https://chart.googleapis.com/chart?cht=tx&chl=%5Calpha的下限
    大部分的一維搜尋法經由迭代持續縮小https://chart.googleapis.com/chart?cht=tx&chl=I,直到https://chart.googleapis.com/chart?cht=tx&chl=I%20%3C%20%5Cepsilon(收斂參數)。此時,https://chart.googleapis.com/chart?cht=tx&chl=%5Calpha%5E%7B%5Cast%7D%20%3D%20%5Cfrac%7B%5Calpha_l%20%2B%20%5Calpha_u%7D%7B2%7D,以此方程式找到https://chart.googleapis.com/chart?cht=tx&chl=%5Calpha%5E%7B%5Cast%7D,稱為Interval reducing method

註解

  1. https://reurl.cc/pDyjGb


上一篇
Day 11 : 單形法(simplex method)的概念與解題步驟
下一篇
Day 13 : 一維搜尋法(line search)
系列文
連接數學與現實世界的橋樑 -- 數學建模30

尚未有邦友留言

立即登入留言