iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 4
0
AI & Data

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

Day 4 : 無限制條件之最佳化

有了Day3基本的數學工具後,接著來看看怎麼去求解數學模型。整個最佳化求解可以分為,無限制條件及有限制條件,今天就先從無限制條件的最佳化求解開始。
根據函數變數的數量可將函數分為單變數函數與多變數函數,這兩種函數各有一些求解條件。

單變數函數

1. 一階必要條件

https://chart.googleapis.com/chart?cht=tx&chl=x%5E%7B%5Cast%7Dhttps://chart.googleapis.com/chart?cht=tx&chl=f(x)之局部最小點,則https://chart.googleapis.com/chart?cht=tx&chl=%5Cleft.%20%5Cfrac%7B%5Cpartial%20f(x%5E%7B%5Cast%7D)%7D%7B%5Cpartial%20x%7D%20%3D%200
由泰勒級數展開式來觀察,已知https://chart.googleapis.com/chart?cht=tx&chl=x%5E%7B%5Cast%7D為駐點(斜率為0的點)則,
https://chart.googleapis.com/chart?cht=tx&chl=%5CDelta%20f%3Df(x)-f(x%5E%7B%5Cast%7D)%3Df'(x%5E%7B%5Cast%7D)(x-x%5E%7B%5Cast%7D)%2B%5Cfrac%20%7B1%7D%7B2%7Df''(x%5E%7B%5Cast%7D)(x-x%5E%7B%5Cast%7D)%5E2%2BR
https://chart.googleapis.com/chart?cht=tx&chl=%5CDelta%20f%20%3E%200 or https://chart.googleapis.com/chart?cht=tx&chl=%5CDelta%20f%20%3C%200,取決於https://chart.googleapis.com/chart?cht=tx&chl=f''(x%5E%7B%5Cast%7D)%20%3E%200 or https://chart.googleapis.com/chart?cht=tx&chl=f''(x%5E%7B%5Cast%7D)%20%3C%200

2. 二階充分條件

https://chart.googleapis.com/chart?cht=tx&chl=f'(x%5E%7B%5Cast%7D)%20%3D%200https://chart.googleapis.com/chart?cht=tx&chl=f''(x%5E%7B%5Cast%7D)%20%3E%200,則 https://chart.googleapis.com/chart?cht=tx&chl=x%5E%7B%5Cast%7Dhttps://chart.googleapis.com/chart?cht=tx&chl=f(x)之局部最小值。
https://chart.googleapis.com/chart?cht=tx&chl=f'(x%5E%7B%5Cast%7D)%20%3D%200https://chart.googleapis.com/chart?cht=tx&chl=f''(x%5E%7B%5Cast%7D)%20%3C%200,則 https://chart.googleapis.com/chart?cht=tx&chl=x%5E%7B%5Cast%7Dhttps://chart.googleapis.com/chart?cht=tx&chl=f(x)之局部最大值。

3. 二階必要條件

https://chart.googleapis.com/chart?cht=tx&chl=x%5E%7B%5Cast%7Dhttps://chart.googleapis.com/chart?cht=tx&chl=f(x)之局部最小值,則https://chart.googleapis.com/chart?cht=tx&chl=f''(x%5E%7B%5Cast%7D)%20%5Cge%200
https://chart.googleapis.com/chart?cht=tx&chl=x%5E%7B%5Cast%7Dhttps://chart.googleapis.com/chart?cht=tx&chl=f(x)之局部最大值,則https://chart.googleapis.com/chart?cht=tx&chl=f''(x%5E%7B%5Cast%7D)%20%5Cle%200

實際操作步驟

  1. 先求駐點(stationary point),令https://chart.googleapis.com/chart?cht=tx&chl=f'(x)%20%3D%200,求出https://chart.googleapis.com/chart?cht=tx&chl=x%5E%7B%5Cast%7D
  2. 檢查https://chart.googleapis.com/chart?cht=tx&chl=f''(x%5E%7B%5Cast%7D)之值
    https://chart.googleapis.com/chart?cht=tx&chl=f''(x%5E%7B%5Cast%7D)%20%3E%200,則https://chart.googleapis.com/chart?cht=tx&chl=x%5E%7B%5Cast%7Dhttps://chart.googleapis.com/chart?cht=tx&chl=f(x)之區域最小值。
    https://chart.googleapis.com/chart?cht=tx&chl=f''(x%5E%7B%5Cast%7D)%20%3C%200,則https://chart.googleapis.com/chart?cht=tx&chl=x%5E%7B%5Cast%7Dhttps://chart.googleapis.com/chart?cht=tx&chl=f(x)之區域最大值。
    https://chart.googleapis.com/chart?cht=tx&chl=f''(x%5E%7B%5Cast%7D)%20%3D%200,則需進一步評估更高階的導數的值。

範例

https://ithelp.ithome.com.tw/upload/images/20190905/20119600bFe9Nlbcku.jpg

https://ithelp.ithome.com.tw/upload/images/20190905/20119600ictnqE4wBQ.jpg

多變數函數

1. 一階必要條件

https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%7BX%7D%5E%7B%5Cast%7Dhttps://chart.googleapis.com/chart?cht=tx&chl=f(%5Cbar%7BX%7D)的局部最小點 ,則https://chart.googleapis.com/chart?cht=tx&chl=%5Cnabla%20f(%5Cbar%7BX%7D%5E%7B%5Cast%7D)%20%3D%200 or https://chart.googleapis.com/chart?cht=tx&chl=%5Cleft.%20%5Cfrac%7B%5Cpartial%20f(%5Cbar%7BX%7D%5E%7B%5Cast%7D)%7D%7B%5Cpartial%20x_i%7D%20%3D%200%2C%20%20%20%20i%3D1%2C%20%5Cdots%20%2Cn

2. 二階充分條件

https://chart.googleapis.com/chart?cht=tx&chl=%5Cnabla%20f(%5Cbar%7BX%7D%5E%7B%5Cast%7D)%20%3D%200https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%7BH%7D(%5Cbar%7BX%7D%5E%7B%5Cast%7D)為正定,則https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%7BX%7D%5E%7B%5Cast%7Dhttps://chart.googleapis.com/chart?cht=tx&chl=f(%5Cbar%7BX%7D)的局部最小點。
https://chart.googleapis.com/chart?cht=tx&chl=%5Cnabla%20f(%5Cbar%7BX%7D%5E%7B%5Cast%7D)%20%3D%200https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%7BH%7D(%5Cbar%7BX%7D%5E%7B%5Cast%7D)為負定,則https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%7BX%7D%5E%7B%5Cast%7Dhttps://chart.googleapis.com/chart?cht=tx&chl=f(%5Cbar%7BX%7D)的局部最大點。
多變數函數https://chart.googleapis.com/chart?cht=tx&chl=f(%5Cbar%7BX%7D)https://chart.googleapis.com/chart?cht=tx&chl=%5Cnabla%20f(%5Cbar%7BX%7D%5E%7B%5Cast%7D)%20%3D%200之泰勒展開式,
https://chart.googleapis.com/chart?cht=tx&chl=%5CDelta%20f%20%3D%20f(%5Cbar%7BX%7D)%20-%20f(%5Cbar%7BX%7D%5E%7B%5Cast%7D)
https://chart.googleapis.com/chart?cht=tx&chl=%3D%20%5Cnabla%20f(%5Cbar%7BX%7D%5E%7B%5Cast%7D)%5ET%5Cbar%7Bd%7D%20%2B%20%5Cfrac%7B1%7D%7B2%7D%20%5Cbar%7Bd%7D%5E%7BT%7D%5Cbar%7BH%7D(%5Cbar%7BX%7D%5E%7B%5Cast%7D)%5Cbar%7Bd%7D%20%2B%20%5Cbar%7BR%7D
其中https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%7Bd%7D%20%3D%20%5Cbar%7BX%7D%20-%20%5Cbar%7BX%7D%5E%7B%5Cast%7D
https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%7BH%7D(%5Cbar%7BX%7D%5E%7B%5Cast%7D)%20%3D%20%5Cnabla%20%5E%7B2%7Df(%5Cbar%7BX%7D%5E%7B%5Cast%7D)
https://chart.googleapis.com/chart?cht=tx&chl=%5CDelta%20f的大小(>0, 0<, 或=0),取決於二次式之正、負或者https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%7BH%7D(%5Cbar%7BX%7D%5E%7B%5Cast%7D)之形式。

3. 二階必要條件

https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%7BX%7D%5E%7B%5Cast%7Dhttps://chart.googleapis.com/chart?cht=tx&chl=f(%5Cbar%7BX%7D)的局部最小點,則https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%7BH%7D(%5Cbar%7BX%7D%5E%7B%5Cast%7D)為正定或半正定。

實際操作步驟

  1. 先求駐點,
    https://chart.googleapis.com/chart?cht=tx&chl=%5Cnabla%20f(%5Cbar%7BX%7D)%20%3D%200,求出https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%7BX%7D%5E%7B%5Cast%7D
  2. 檢查https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%7BH%7D(X%5E%7B%5Cast%7D)之形式

[提醒]當遇到非線性方程式時,駐點未必可用解析方式求得

範例

https://ithelp.ithome.com.tw/upload/images/20190905/20119600yEHzJNEw5D.jpg
https://ithelp.ithome.com.tw/upload/images/20190905/201196008icL2LM4E4.jpg


上一篇
Day 3 : 常用的數學工具
下一篇
Day 5 : 有限制條件之最佳化 - Lagrange multiplier theorem
系列文
連接數學與現實世界的橋樑 -- 數學建模30

尚未有邦友留言

立即登入留言