iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 6
0
AI & Data

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

Day 6 : 有限制條件之最佳化 - KKT定理

上次我們提到了針對有限制條件之最佳化中的等式限制條件,可以利用Lagrange multiplier theorem來求解。今天更一進步討論不等式限制條件該如何計算。

不等式限制條件的型式為,
https://chart.googleapis.com/chart?cht=tx&chl=g_i(%5Cbar%7BX%7D)%20%5Cle%200%2C%20%20i%3D1%2C%20%5Cdots%20%2C%20m

一旦遇到不等式限制條件,第一步就是轉成等式限制條件
https://chart.googleapis.com/chart?cht=tx&chl=g_i%20%2B%20%7BS_i%7D%5E2%20%3D%200%2C%20i%3D1%2C%20%5Cdots%20%2C%20m
其中https://chart.googleapis.com/chart?cht=tx&chl=S_i為鬆弛變數(slack variable)
https://chart.googleapis.com/chart?cht=tx&chl=%7BS_i%7D%5E2%20%3D%200 or https://chart.googleapis.com/chart?cht=tx&chl=S_i%20%3D%200 https://chart.googleapis.com/chart?cht=tx&chl=%5CRightarrow%20g_i%20%3D%200,此時https://chart.googleapis.com/chart?cht=tx&chl=g_i(%5Cbar%7BX%7D)為Active constraint
https://chart.googleapis.com/chart?cht=tx&chl=%7BS_i%7D%5E2%20%3E%200 or https://chart.googleapis.com/chart?cht=tx&chl=S_i%20%20%5Cne%20%200 https://chart.googleapis.com/chart?cht=tx&chl=%5CRightarrow%20g_i%20%3C%200,此時https://chart.googleapis.com/chart?cht=tx&chl=g_i(%5Cbar%7BX%7D)為Inactive constraint

Karnh-Kuhn-Tucker必要條件

KKT定理

https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%7BX%7D%5E%7B%5Cast%7D為可行區域內之一正則點,且為https://chart.googleapis.com/chart?cht=tx&chl=f(%5Cbar%7BX%7D)滿足https://chart.googleapis.com/chart?cht=tx&chl=h_i(%5Cbar%7BX%7D)%20%3D%200%2C%20i%3D1%2C%20%5Cdots%20%2C%20phttps://chart.googleapis.com/chart?cht=tx&chl=g_i(%5Cbar%7BX%7D)%20%5Cle%200%2C%20i%3D1%2C%20%20%5Cdots%20%2C%20m的局部最小點,若定義該最佳化問題之Lagrange function如下:
https://ithelp.ithome.com.tw/upload/images/20190907/20119600W7logKfYwW.jpg
Note:(4)式稱為switching conditions。一般而言,有m個不等式限制條件,則可產生https://chart.googleapis.com/chart?cht=tx&chl=2%5Em個不同的正常解組合。
例如:
https://chart.googleapis.com/chart?cht=tx&chl=m%20%3D%202,則(4)式為https://chart.googleapis.com/chart?cht=tx&chl=u_1S_1%20%3D%200%2C%20%20u_2S_2%20%3D%200,故有https://chart.googleapis.com/chart?cht=tx&chl=2%5E2%20%3D%204種答案組合

https://chart.googleapis.com/chart?cht=tx&chl=(a)%20%20u_1%20%3D%200%2C%20u_2%20%3D%200
https://chart.googleapis.com/chart?cht=tx&chl=(b)%20%20u_1%20%3D%200%2C%20S_2%20%3D%200
https://chart.googleapis.com/chart?cht=tx&chl=(c)%20%20S_1%20%3D%200%2C%20u_2%20%3D%200
https://chart.googleapis.com/chart?cht=tx&chl=(d)%20%20S_1%20%3D%200%2C%20S_2%20%3D%200

https://ithelp.ithome.com.tw/upload/images/20190907/2011960011lbZTVJmG.jpg
本題https://chart.googleapis.com/chart?cht=tx&chl=m%20%3D%201,有https://chart.googleapis.com/chart?cht=tx&chl=2%5E1%20%3D%202種答案組合
https://ithelp.ithome.com.tw/upload/images/20190907/20119600GOuD8HtJDd.jpg
https://ithelp.ithome.com.tw/upload/images/20190907/20119600gRO5RwmEfy.jpg

https://ithelp.ithome.com.tw/upload/images/20190907/20119600FnlIHc5nOY.jpg
https://ithelp.ithome.com.tw/upload/images/20190907/20119600O4sSIU1SmI.jpg
https://ithelp.ithome.com.tw/upload/images/20190907/20119600ZhOmJ53rfW.jpg
https://ithelp.ithome.com.tw/upload/images/20190907/201196001c29Q2qwv2.jpg
https://ithelp.ithome.com.tw/upload/images/20190907/20119600A0qkrYQ5XK.jpg
https://ithelp.ithome.com.tw/upload/images/20190907/201196003KmvxCCgI0.jpg

Note:

  1. 不等式限制條件在active constraint的情況下要去檢驗是否為正則點,但是只有一個限制條件時無需檢驗,因為它必為正則點。
  2. 檢驗方法為,確認https://chart.googleapis.com/chart?cht=tx&chl=%5Cnabla%20g_i(%5Cbar%7BX%7D%5E%7B%5Cast%7D)彼此是否為線性獨立。

上一篇
Day 5 : 有限制條件之最佳化 - Lagrange multiplier theorem
下一篇
Day 7 : 當方程組無法用手算怎麼辦 -- 數值分析
系列文
連接數學與現實世界的橋樑 -- 數學建模30

尚未有邦友留言

立即登入留言