好的,那有了剛剛的知識以後,我們接下來為大家介紹最佳化條件。 我們先從最佳化問題開始介紹起,比如說啊如果大家 想像一下這個問題,我今天有一個問題是說我想要在二維平面上 討論怎麼樣的x1,x2可以來最大化我的這個目標函數x1+ x2,那這個時候呢我遇到了幾個限制是,就是我的x1+2x2必須要小於等於6, 2x1+x2必須要小於等於6,以及x1跟x2都要 nonnegative,這樣子。 那麼呢,對這個問題我們介紹幾個關鍵字 比如說我們說我們有兩個決策變數,分別是x1跟x2,那是我要決定的數字。 決定數字是爲了要最大化,在這個例子里最大化我的目標式也就是x1+x2。 然後,我遇到了四個限制,這四個限制分別地會再告訴我說 我的x1跟x2不能太大不能太小,不能偏這裡不能偏那裡,就是這個x1+2x2小於等於6 等這四個人,所以這幾個限制是合起來 包含住的範圍我們稱爲feasible region或者說可行解區域。 那我們把它畫成圖的話呢會像右手邊這個樣子,大家可以看到x1 跟x2都得要是nonnegative的,所以是第一象限的部份,然後 兩條不等式2x1+x2小於等於6和x1+2x2小於等於6 分別地就把這個區域做了一個切割,導致最後只有中間的 這一小塊的這個四邊形的部份是所謂的feasible region,我想要在這個region裏面找一個點 讓它能最大化我的x1+x2,是這樣子的一個問題。 那麼對於一個最佳化問題呢,我想做的事情就是我想找出最佳解。 那麼以這個問題來說,我知道最佳解就是所謂的(2,2) 我怎麼知道呢?我知道我要maximize(x1+x2)嘛,那 x1越大越好,x2越大越好,而且我基本上有一個intuition就是說我想要把這個 我的點往右上方推,我的點越靠近右上方基本上就是越理想啦, 好,那麼你就推呀推呀推推推推推,推到底你就發現,誒,這個 兩個的交叉點就是最佳解,那這個細節我們在這裡就不多談了,但是總之 (2,2)這個點,我們把它在這個題目里稱為最佳解,optimal solution,也就是我們這個problem的solution 好,那有時候我們討論最佳解是否唯一,也就是有沒有其他 的點一樣都是最佳解呢,在這個例子里是沒有的,你找不到任何一個 另一個可行解,它能夠達到跟(2,2)一樣好的 程度,那所謂的程度是指什麽?就是目標式值 (2,2)代進去目標式你會得到4,z*會是4,這個是你最理想能做到的事情 沒有任何一個其他點能做到4這麼好,那麼你的(2,2)就是唯一的最佳解。 在我們的一個最佳化問題裏面呢,偶爾我們會遇到像現在這個 模式,這個描述下的這個題目,就是目標式和限制式通通都是線性函數。 沒有二次式,沒有開根號,沒有取log,沒有三角函數,等等,什麽都沒有。 就只有線性函數,這個時候我們就稱呼這個問題為一個線性規劃問題,okay,linear programming 那很多時候我們會遇到非線性規劃問題,事實上在這門課里絕大部份的問題都是非 線性的,那原因是什麽?原因是因爲這個世界本來就是非線性的,特別是跟人有關的議題 很多時候都是非線性的,那我們之後會有例子,所以這裡先不談。 那我們就來談談非線性規劃有一些什麽性質或是會長什麽感覺吧? 所以比如說這裡有個問題一,問題一呢我們來試著先把 這個feasible region畫出來看看,它是說 x1跟x2合起來,x1平方加x2平方小於等於16,okay,所以我們知道,基本上就是 一個半徑為4的圓,只能落在這個圓裏面。 其次呢,是說x1+x2要大於等於-1, 哦,那基本上就會是一條這樣子的線,對吧,然後呢,要大於 等於那就是要靠右上方,所以我們知道feasible region是我現在 畫斜線的這一塊,好的,這是feasible region。 那如果我在這裡要最大化x1+x2呢,那一樣,我想要把 我的點盡可能的往右上方移動,那麼最後我會得到最佳解,就是 現在這個邊邊上的這個點,大概是2√2和2√2,大家有興趣的話可以verify一下 好的,那麼這是問題一,問題二我們也試著把 feasible region先畫出來看看,我呢有兩條限制式, 第一條是x1,x1+2x2要小於等於4,所以大概是長這樣。 okay,這個是4,這個是2,第二條呢 是2x1+x2要小於等於4,那就長得有點像,有點對稱,大概是這樣, 好,這個是2,這個是4,然後呢必須要比這兩條都來得小,或者是來得低 那就是這個區域 是我的feasible region,好,那回來看目標式 目標式呢基本上只有兩種,要麼你選這些value來最大化目標式,要麼 就是最小化目標式,在我們的問題二這個例子里我們就是想要最小化目標式 所以我想要最小化x1平方加x2平方,可能 這個問題,嗯,你一開始可能不知道怎麼解,不過你仔細想想 平方一定是nonnegative的對吧,你再怎麼樣,平方項 不可能會是負的,所以最理想的狀態下就是x1跟x2都是零 那你的最佳解就是,那你得到的值就是零,不會有這個點,不會有點比零來得更好 對吧,因為你是平方項相加,那這個時候呢,你就想,哎喲 (0,0)看起來不錯,(0,0)是feasible的嗎?(0,0)在這兒 它確實是feasible的,對吧,(0,0)符合這些限制式,而且沒有點比(0,0)好 那(0,0)就是最佳解。 所以這兩個問題呢我們都可以靠我們的intuition來把最佳解求出來 那它大概也描述了所謂的非線性,要麼就是限制式裏面有非線性 的東西,不然就是目標式裏面有非線性的東西,okay? 那麼剛剛那兩個問題啊,它 被設計來在這個課裡要作介紹的其中一個理由是因為我們想要告訴大家說最佳解 有兩種,有一種題目的最佳解是所謂的interior solution,或者說是內點解 它什麽意思呢?就是它落在可行解區域的,我們就roughly說吧,就是 裏面而不是邊界上,比如說以剛剛的問題來說,問題2 的最佳解就是內點解,因為它是落在區域的裏面而不是邊界上 反之,最佳解可能是一個邊界解或者說boundary solution 它的意思就是我要你落在邊界上嘛,像剛剛的問題一,你的最佳解不是落在那個圓的邊邊上嗎? 那東西就是boundary solution,那老是這樣子模糊地講也不是辦法,所以我們來定義一個所謂的 叫做有效限制式binding constraint的概念,這個概念在我們之後未來的課程求解很長會需要用到 那有了它我們就可以嚴謹的定義所謂的interior solution和boundary solution 好,binding constraint是什麽意思呢?它的意思是這樣 我給你一個不等式的限制式g(-) ≤b,以及一個candidate solution x bar, 這個時候,我把x bar代進去g試試看,如果代進去了以後恰好 讓這個不等式以等式的方式被滿足,那我們就說這個 不等式在x bar是一個binding constraint或者是active contraint,意思就是說 哦,我呢這條限制式確實有限制到這個點 okay?那反之如果代進去其實是小於 而不是≤也不是=,代進去如果是strictly的less than的話 我們就說這個constraint在這個點上是無效的,因為沒有真的限制到它 我還可以再往我們的邊界再跨一步,那這個時候就是nonbinding或是inac- tive 所以看幾個例子就很容易謄清楚啦,我x1+x2≤10,在 (2,8)這個點是binding的,因為(2,8)一代進去就等於10嘛,那反之呢2- x1+x2 ≥6 在(2,8)是nonbinding。 因為(2,8)代進去了以後,2、 2得4,4+8是12,12比6大。 最後(6,1)把它代進x1+3x2 ≤9呢,我們會發現,誒,它binding,因為6+3=9。 好,所以就是要verfify就是代進去,算算是不是變成等式就可以啦 那有的時候你的題目,本來你的限制式就是equality constraint,那如果是這樣子的話,任何 的可行解對那個等式限制式當然都是binding,畢竟你代進去要成立,成立就是等號,- 那它就算是binding 這樣子,好,所以我們通常沒事我們不會討論等式限制式的binding 與否,畢竟沒什麼好討論的嘛,通常都是討論不等式 那邊界解和內點解,我們現在 就知道它有什麽差別啦,在一個boundary solution上 一定有至少一條限制式是binding的,這樣子才叫做落在邊界上了,對吧,那如果你沒- 有落在任何 的constrained的邊界上,那就叫做interior solution,所以一個interior solution上是沒有任何binding constraint的 這樣子,有了binding constraint你就可以定義這兩個東西啦!