好的,那我們現在就開始為大家介紹最佳化理論。 大家如果以前學過類似的東西的話就當做是一個複習,那如果沒學過 的話呢,那就是我們會在這裡簡要地介紹在我們這 七週的課程之中會需要用到的基礎知識,好的 那首先我們得要幫大家做一些集合和函數相關的 知識的介紹,那我們先介紹一個重要的概念叫做 convex set 那中文叫做凸集合,它的意思是什麼?假設我今天給你一個集合,就是一堆點的集合 那我們會考慮在這個集合裡面,如果我任意取兩個點 任意取兩個點,並且考慮所有把這兩個點做一個連線的方式 那麼我想問這個連線有沒有在這個 set 裡面?那我們先看 底下的圖好了。 底下的圖呢,我這裡左邊有一個 set,就是這個圈圈 圈圈裡面我任取兩個點,x1 跟 x2,然後我把這兩個點像這樣子連線起來 我會發現,這條線落在這個集合裡面,對吧?那大家可以試試看,你在這個集合里任取兩個- 點連起來 那個連線的線段一定落在這個集合裡面,那麼我們就說左邊這個集合是一個凸集合 是一個 convex set。 那反例就是右邊這個,右邊這個有缺一角的,如果我把 x1 跟 x2 連起來 我就會發現有一部分的點落在這個集合以外,這個時候它就是不是一個 convex set 了 那數學上來說呢,就是我要把 x1 跟 x2 這兩個向量做一個 convex combination,也就是我用 λ 是 0 或 1 來在這兩個量之間做調整,λ 是 0 的時候 就是 x2,λ 是 1 的時候就是 x1,λ 是 1/2 的時候就是兩個點中間,所以對所有的 λ,如果 這個 convex combination 都落在 F 裡面,那這就是 所謂的線段都落在這個 set 裡面,那麼 F 就是一個 convex set 好的,所以我們來看看這幾個例子,我 x1 如果是 10 到 20,豎線上 10 到 20 的封閉集合,也就是包含 10 到 20 的話 是 convex set 嗎?是,因為我在裡面任取兩點,比如說 12 跟 16 連起來,都在 10 到 20 裡面嘛,好,所以沒有問題。 如果是 10 到 20 的開區間呢? 也是,只不過就是我現在不能取 10 跟 20 罷了,但是我取 13 到 18 依然是在 10 到 20 裡面。 x3 是自然數 的集合,正整數的集合,這個時候它就不是 convex set 啦,為什麼? 比如說你有 1 2 3 4 5 6 7 8,你取 5 跟 6 這兩個點連線 中間包含了 5.5,5.2,5.8,5.35 等等這些數字都不是自然數 所以這個時候呢,自然數的集合,就中間有洞了,它就不是 convex set x4 這個 set 是所有的自然數,這個時候就沒問題了,對不起 所有的實數,這個時候就沒有問題啦,因為你任意兩個實數連起來,中間連線 都是實數,所以這樣子是 OK 的 那再來,x5 跟 x6 這個時候是兩個這個二維的平面上 的一個區間,那我們試著把它畫出來看看。 以 x5 來說,就是你的 x,y 這兩個二維坐標 要符合 x2+y2<=4,那我們知道它大概是什麼意思。 它就是在說 x 跟 y 合起來必須要落在這個圓裡面,圓的半徑呢就是 2 這樣子,所以比如說 (2,0) 這個點恰好是 4,落在邊上,那 (0,2) 也恰好落在邊上 然後這個 x,y 要讓 x2+y2<=4 那比如說 0 好了,(0,0) 這個點帶進去是成立的,那我們就知道 OK,所以就是裡面這一圈,所以就是這個圓裡面 那你就想想剛剛的定義,任取兩個點連起來,落在這個 圓裡,所以 x5 就是 convex set。 那 x6 呢? x6 幾乎長得一模一樣,一樣是一個圓,只是它是要取外面 那很顯然地,它就不是 convex set 了,因為比如說我取這個點 和這個點,把它們連起來的話,有好大一段都 落在這個 set 以外,所以這個時候 x6 就不是 convex set 啦 大概就是這麼一回事,好的。 那跟 convex set 很像的一個東西呢 我們稱呼它是一個 convex function,所以這個時候我們不談論集合了,我們談論的是一個函數 函數有所謂的 convex function,那我們來看看它是什麼樣的定義 大家先瞄一眼這個框框,你會覺得,長得 跟剛剛的 convex set 的定義的這個形態有點像 都是有什麼 λ,1-λ 在那邊弄來弄去的,所以這就是為什麼它們是相類似的概念。 我們來考慮一個 函數 f,並且考慮一個 convex set F 這個 convex set 是所謂的定義域,就是我們在這個 F 裡面 討論這個函數 f 的行為,好。 我在這個 set 裡面呢任意挑兩點 x1 跟 x2,那比如說,假設是這個點和這個點好了 這個是我的 x1,這個是我的 x2,我現在幹嘛呢? 我現在問,x1 跟 x2,對應到的函數 值有多高?以 x1 來說就是這裡嘛 這個高度是 f(x1) 那以 x2 來說呢是這裡,這個是 f(x2) 對吧?函數值就是它有多高,那麼 看一下不等式的右手邊。 右手邊我用 λ 跟 1-λ 來幫 f(x1) 和 f(x2) 做一個加權平均嘛 那這個時候我得到的東西是什麼?就是這一段 OK?就是這兩個高度的連線,所以我現在呢 right hand side 就是這個紅色的這個粗的線條,那麼不等式的左手邊是什麼?左手邊是我把 x1 跟 x2 先做一個加權平均了以後 再去對應到它的函數值有多高,這樣子 那麼這整個不等式在講什麼呢?在講說,如果你有一個函數 f 它呢,任取兩點,放到函數值上的連線比那個函數值高,那這個時候它就是一個 convex function,你的函數長得像一個碗 你在這個碗的邊邊上任取兩個點連線 比這個碗高,它就是 convex function 啦 那你看右邊這個,右邊這個就不行,為什麼?比如說這是 x1,這是 x2 的話,x1 對應到這個點 x2 對應到這個點,然後你一連線 發現有的時候比函數值高,有的時候比函數值低 那這個就不是 convex function 了,就是這一段,這一段呢,我們發現 它連線是比函數值低的,就不符合 convex function 的定義,所以右邊這個函數就不是 convex function 好,那我們來看一些例子,f1 這個函數 f1 是 x+2,所以你看,如果我這個是 x 那 x 是 0 的時候就是 2,然後是一條線性的函數嘛,這個是 f1,這個顯然是沒有問題,為什麼? 你取一個點,取一個點,任取兩個點,連線,都沒有比這個函數值來的低 對吧?那這個時候它就是一個 convex function 那 f2 呢,f2 大家知道是個拋物線,長得很像前一頁 投影片的左手邊那個圖,所以 f2 也是一個 convex function 那 f3 呢?f3 的圖,這個倒是得要畫一下 我們知道它是一個三次式,三次式長什麼樣子? x 是正的的時候,長的是像這樣子,當 x 是負的時候呢長得像是這個樣子 畫的這個有點不精確,不過大家知道大概是呈現一個某種 s 形狀態,是這個 x3 的這個函數 這個時候,我考慮的定義域,也就是剛剛前一頁的 F 是什麼?就顯得很重要了。 如果我考慮的是 正的 x 的話,那就是我只在看右手邊的這個區段 這個時候這個函數是 convex 的,OK,因為在這個區段裡面你任意地連兩條線 連兩個點,它的線段是在函數值上面的,所以這個 OK 但我如果考慮的是從 -2 到 2 的這個範圍的話 那就不行了,因為左手邊這一段顯然就不符合 convex function 的定義,所以這個時候就不行 這樣。 好,那 f5,f5 它在幹嘛呢? 它現在看起來是一個二次式,對吧?而且我沒有告訴你 a 跟 b 跟 c 是多少,我只跟你說函數是 ax2+bx+c 所以你知道它是拋物線,但你不知道它怎麼拋的,對吧 不過,大家可能對二次式或者拋物線有一些簡單的了解的話 我們大家知道,關鍵是看 x2 的係數 x2 的係數如果是正的,也就是說如果 a 大於 0 那這個函數就是向上開,拋物線的底是在下面的,所以這個長得 像是一個往上放的碗,但如果 a 呢是小於 0 的,你知道這個函數是向下開的嗎? 所以這樣子一來,你就知道答案是什麼。 a 如果是正的,它就是 convex function a 如果是負的,它就不是 convex function,那如果 a 是 0 呢?a 是 0 的話,這個 term 就不用看了嘛,那你就只剩下 bx + c,那跟 f1 豈不是長得很像嗎? 所以它這個時候就是 convex function 了,OK