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

第 11 屆 iThome 鐵人賽

DAY 4

AI & Data

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

11th鐵人賽工程最佳化

spidyjames

2019-09-05 23:54:29

2258 瀏覽

分享至

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

單變數函數

1. 一階必要條件

若 $x^{\ast}$ 為 $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$
由泰勒級數展開式來觀察，已知 $x^{\ast}$ 為駐點(斜率為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$
$\Delta f > 0$ or $\Delta f < 0$ ，取決於 $f''(x^{\ast}) > 0$ or $f''(x^{\ast}) < 0$

2. 二階充分條件

若 $f'(x^{\ast}) = 0$ 且 $f''(x^{\ast}) > 0$ ，則 $x^{\ast}$ 為 $f(x)$ 之局部最小值。
若 $f'(x^{\ast}) = 0$ 且 $f''(x^{\ast}) < 0$ ，則 $x^{\ast}$ 為 $f(x)$ 之局部最大值。

3. 二階必要條件

若 $x^{\ast}$ 為 $f(x)$ 之局部最小值，則 $f''(x^{\ast}) \ge 0$
若 $x^{\ast}$ 為 $f(x)$ 之局部最大值，則 $f''(x^{\ast}) \le 0$

實際操作步驟

先求駐點(stationary point)，令 $f'(x) = 0$ ，求出 $x^{\ast}$
檢查 $f''(x^{\ast})$ 之值
若 $f''(x^{\ast}) > 0$ ，則 $x^{\ast}$ 為 $f(x)$ 之區域最小值。
若 $f''(x^{\ast}) < 0$ ，則 $x^{\ast}$ 為 $f(x)$ 之區域最大值。
若 $f''(x^{\ast}) = 0$ ，則需進一步評估更高階的導數的值。

範例

多變數函數

1. 一階必要條件

若 $\bar{X}^{\ast}$ 為 $f(\bar{X})$ 的局部最小點，則 $\nabla f(\bar{X}^{\ast}) = 0$ 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. 二階充分條件

若 $\nabla f(\bar{X}^{\ast}) = 0$ 且 $\bar{H}(\bar{X}^{\ast})$ 為正定，則 $\bar{X}^{\ast}$ 為 $f(\bar{X})$ 的局部最小點。
若 $\nabla f(\bar{X}^{\ast}) = 0$ 且 $\bar{H}(\bar{X}^{\ast})$ 為負定，則 $\bar{X}^{\ast}$ 為 $f(\bar{X})$ 的局部最大點。
多變數函數 $f(\bar{X})$ 在 $\nabla f(\bar{X}^{\ast}) = 0$ 之泰勒展開式，
$\Delta f = f(\bar{X}) - f(\bar{X}^{\ast})$
$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$
其中 $\bar{d} = \bar{X} - \bar{X}^{\ast}$
$\bar{H}(\bar{X}^{\ast}) = \nabla ^{2}f(\bar{X}^{\ast})$
則 $\Delta f$ 的大小(>0, 0<, 或=0)，取決於二次式之正、負或者 $\bar{H}(\bar{X}^{\ast})$ 之形式。