iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 8
1
AI & Data

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

Day 8 : 全域最佳化 - 凸函數

我們在前面談了一堆求最佳解的條件與解法,但其實真正的最佳解"有可能"一直沒有被找到,這是甚麼意思。最佳解有兩種,一種是區域最佳解,另一種是全域最佳解,用白話一點的說法就是,班上的第一名(區域最佳解)未必是全校第一名(全域最佳解)。那為什麼我們要花時間在學習求區域最佳解,因為"有些情況"無法求得全域最佳解,只能退而求其次,而且取得區域最佳解已經可以滿足目標了。但是,還是有一些情況是可以解得全域最佳解,只要函數被判定為凸函數。

凸函數的一個重要性質,也就是可以由局部信息推導出全域信息。在數學分析中,我們大都是分析函數的局部信息(微分),以此分析函數特性,而凸函數的特性可使我們只需分析函數的局部性質就可以獲知全局特性。因此,接下來幾天我們圍繞在凸函數上。

凸集合

https://chart.googleapis.com/chart?cht=tx&chl=S為凸集合https://chart.googleapis.com/chart?cht=tx&chl=%5CLeftrightarrow%20 https://chart.googleapis.com/chart?cht=tx&chl=S內之任意2點https://chart.googleapis.com/chart?cht=tx&chl=P_1%2C%20P_2之連接線段上的所有點也在https://chart.googleapis.com/chart?cht=tx&chl=S內。
https://ithelp.ithome.com.tw/upload/images/20190909/20119600NlndbIt1Z8.jpg

凸函數

先複習一下,線段之參數式:
* 單變數:https://chart.googleapis.com/chart?cht=tx&chl=x%20%3D%20%5Calpha%20x_2%20%2B%20(1-%20%5Calpha)x_1 ; https://chart.googleapis.com/chart?cht=tx&chl=0%5Cle%20%5Calpha%20%20%5Cle%201
* 多變數:https://chart.googleapis.com/chart?cht=tx&chl=f(%5Calpha%20%5Cbar%20X%5E%7B(2)%7D%20%2B%20(1%20-%20%5Calpha)%20%5Cbar%20X%5E%7B(1)%7D)%20%5Cle%20%5Calpha%20f(%5Cbar%20X%5E%7B(2)%7D)%20%2B%20(1%20-%20%5Calpha)%20f(%5Cbar%20X%5E%7B(1)%7D)%20%3B%200%20%5Cle%20%5Calpha%20%5Cle%201
https://chart.googleapis.com/chart?cht=tx&chl=%5Calpha%20%3D%200, https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20X%20%3D%20%5Cbar%20X%5E%7B(1)%7D
https://chart.googleapis.com/chart?cht=tx&chl=%5Calpha%20%3D%201, https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20X%20%3D%20%5Cbar%20X%5E%7B(2)%7D

凸函數必須定義在凸集合上,其充要條件為,

  • 單變數函數https://chart.googleapis.com/chart?cht=tx&chl=f(x):
    https://chart.googleapis.com/chart?cht=tx&chl=f(%5Calpha%20x_2%20%2B%20(1-%5Calpha)x_1)%20%5Cle%20%5Calpha%20f(x_2)%20%2B%20(1-%5Calpha)f(x_1) ; https://chart.googleapis.com/chart?cht=tx&chl=0%20%5Cle%20%5Calpha%20%5Cle%201
  • 多變數函數https://chart.googleapis.com/chart?cht=tx&chl=f(%5Cbar%20X):
    https://chart.googleapis.com/chart?cht=tx&chl=f(%5Calpha%20%5Cbar%20X%5E%7B(2)%7D%20%2B%20(1%20-%20%5Calpha)%20%5Cbar%20X%5E%7B(1)%7D)%20%20%5Cle%20%20%5Calpha%20f(%5Cbar%20X%5E%7B(2)%7D)%20%2B%20(1%20-%20%5Calpha)%20f(%5Cbar%20X%5E%7B(1)%7D)%20%3B%200%20%5Cle%20%5Calpha%20%5Cle%201

檢驗函數的凸性(convexity)

由定義來下手,
在凸集合https://chart.googleapis.com/chart?cht=tx&chl=S上之函數https://chart.googleapis.com/chart?cht=tx&chl=f(%5Cbar%20X)為凸函數 https://chart.googleapis.com/chart?cht=tx&chl=%5CLeftrightarrowhttps://chart.googleapis.com/chart?cht=tx&chl=S內之所有點的https://chart.googleapis.com/chart?cht=tx&chl=%5Cbar%20H(%5Cbar%20X)皆為正定或半正定

範例

https://ithelp.ithome.com.tw/upload/images/20190909/20119600QKvat1gWDi.jpg
https://ithelp.ithome.com.tw/upload/images/20190909/20119600EIwSaMSmfE.jpg

凸性規劃問題

由等式限制條件https://chart.googleapis.com/chart?cht=tx&chl=h_i(%5Cbar%20X)%20%3D%200 , https://chart.googleapis.com/chart?cht=tx&chl=i%3D1%2C%20%5Cdots%2C%20p與不等式限制條件https://chart.googleapis.com/chart?cht=tx&chl=g_j(%5Cbar%20X)%20%5Cle%200 , https://chart.googleapis.com/chart?cht=tx&chl=j%3D1%2C%20%5Cdots%2C%20m 所定義之Constraint set(a feasible set)https://chart.googleapis.com/chart?cht=tx&chl=S

  1. 如所有https://chart.googleapis.com/chart?cht=tx&chl=h_i為線性函數,且https://chart.googleapis.com/chart?cht=tx&chl=g_j為凸函數,則https://chart.googleapis.com/chart?cht=tx&chl=S為凸集合
  2. 如所有https://chart.googleapis.com/chart?cht=tx&chl=h_ihttps://chart.googleapis.com/chart?cht=tx&chl=g_j皆為線性函數,則https://chart.googleapis.com/chart?cht=tx&chl=S為凸集合
  3. 如任何一個https://chart.googleapis.com/chart?cht=tx&chl=h_i為非線性函數,則 S為非凸集合

若一個最佳化問題的https://chart.googleapis.com/chart?cht=tx&chl=S為凸集合,且目標函數在https://chart.googleapis.com/chart?cht=tx&chl=S內也為凸函數,則此最佳化問題屬於凸性規劃問題。其好處為,前述的KKT必要條件,可以同時為充分條件且找到的區域最小值即為全域最小值。

範例

https://ithelp.ithome.com.tw/upload/images/20190909/20119600LyVOMdZV8r.jpg
https://ithelp.ithome.com.tw/upload/images/20190909/20119600mjeJ0ZkiU0.jpg


上一篇
Day 7 : 當方程組無法用手算怎麼辦 -- 數值分析
下一篇
Day 9 : 線性規劃問題(linear programming problem)
系列文
連接數學與現實世界的橋樑 -- 數學建模30

尚未有邦友留言

立即登入留言