iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 5
0
AI & Data

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

Day 5 : 有限制條件之最佳化 - Lagrange multiplier theorem

今天來討論具有複雜結構的最佳化問題。在實際的問題中,勢必存在著對獨立變項的限制條件,比如說如何在有限的成本中,獲取最大利益,此時就須要考慮較複雜的模型。

限制條件可分為等式限制以及不等式限制(此處都以多變量函數為主),等式限制會談到Lagrange Multiplier Theorem,不等式限制則會提到Karnh-Kuhn-Tucker Theorem。

先來介紹限制條件的最佳化之一般化模型,
find a design vector https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%7BX%7D%20%3D%20(x_1%2C%20x_2%2C%20%5Cdots%20%2C%20x_n) to
min https://chart.googleapis.com/chart?cht=tx&chl=f(%5Cbar%7BX%7D)%20%3D%20f(x_1%2C%20x_2%2C%20%5Cdots%20%2C%20x_n)
s.t. https://chart.googleapis.com/chart?cht=tx&chl=h_i(%5Cbar%7BX%7D)%20%3D%200%2C%20i%3D1%2C%20%5Cdots%20%2C%20p
https://chart.googleapis.com/chart?cht=tx&chl=g_j(%5Cbar%7BX%7D)%20%5Cle%200%20%2C%20j%3D1%2C%20%5Cdots%20%2C%20m

限制條件會影響最佳解出現的位置。如下圖,限制條件就是藍色線,解就只能從X軸、Y軸以及藍色線所圍起來的空間中去選取,此空間稱為feasible region。
https://ithelp.ithome.com.tw/upload/images/20190906/20119600wUSiVukZx2.jpg

等式限制之必要條件

Find https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%7BX%7D to
min https://chart.googleapis.com/chart?cht=tx&chl=f(%5Cbar%7BX%7D)
s.t. https://chart.googleapis.com/chart?cht=tx&chl=h_i(%5Cbar%7BX%7D)%20%3D%200%2C%20i%3D1%2C%20%5Cdots%20%2C%20p

正則點(Regular point)

定義

https://chart.googleapis.com/chart?cht=tx&chl=h(%5Cbar%7BX%7D%5E%7B%5Cast%7D)%20%3D%200%2C%20i%3D1%2C%20%5Cdots%20%2C%20p,且在點https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%7BX%7D%5E%7B%5Cast%7D可使限制條件函數之梯度向量線性獨立,則點https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%7BX%7D%5E%7B%5Cast%7D稱為正則點

Lagrange Multiplier Theorem
https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%7BX%7D%5E%7B%5Cast%7D為一正則點,且為上述問題之區域最小點,則存在一組Lagrange multiplier https://chart.googleapis.com/chart?cht=tx&chl=%7B%5Cupsilon_j%7D%5E%7B%5Cast%7D%2C%20j%3D1%2C%20%5Cdots%20%2C%20p,使得
https://ithelp.ithome.com.tw/upload/images/20190906/201196004vHkk32WIR.jpg

定義

Lagrange function
https://ithelp.ithome.com.tw/upload/images/20190906/20119600Aw9vghXnHP.jpg

範例

https://ithelp.ithome.com.tw/upload/images/20190906/20119600fkN8ec3SGm.jpg
https://ithelp.ithome.com.tw/upload/images/20190906/20119600TqmmQi2YmS.jpg


上一篇
Day 4 : 無限制條件之最佳化
下一篇
Day 6 : 有限制條件之最佳化 - KKT定理
系列文
連接數學與現實世界的橋樑 -- 數學建模30

尚未有邦友留言

立即登入留言