好的，那我們現在就開始為大家介紹最佳化理論。 大家如果以前學過類似的東西的話就當做是一個複習，那如果沒學過 的話呢，那就是我們會在這裡簡要地介紹在我們這 七週的課程之中會需要用到的基礎知識，好的 那首先我們得要幫大家做一些集合和函數相關的 知識的介紹，那我們先介紹一個重要的概念叫做 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
