關於 KKT 2
λg(x) = 0
我想在補充一個例子...可以讓大家對 KKT 更有直覺一點
前面已經舉過
Example1:
min x
s.t. x^2 - 4 <= 0
在這個例子中 最小值發生在 x = -2 ;
在該點上 λ =/= 0; g(x) = 0
Example2:
min x^2
s.t. x^2 - 4 <= 0
直觀上可以看出...最小值發生在 x = 0
該點同時也是 min x^2 無限制條件的解
因此...直覺上，就可以感覺得出來 λ 應該要是 0
在 x = 0 點上 λ = 0 ; g(x) =/= 0
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
到此，大家可以想想看...
有沒有怎樣的例子中...λ會等於0 而且 g(x) 也會等於 0 呢？
不妨試試看
Example3:
min (x-2)^2
s.t. x^2 - 4 <= 0
把限制式拿掉
可以看到 min (x-2)^2 的解...就正好在 x = 2
而 x = 2 這點...也剛好在 g(x) 的邊界上 ！！！
大家可以試著算算看...說不定可以獲得一些感覺
希望這三個例子，可以幫助大家對於 KKT 能有更進一步的認識！
※ 引述《Cayley (水色天藍)》之銘言：
: 其實 RAINDD 講得很對
: λ的正負號...扮演著極為重要的角色！！
: 簡單的嘗試看看這題就知道了：
: min x
: s.t. x^2 - 4 < = 0
: 很值觀可以看得出來
: 最大值在 x = 2 最小值在 x = -2
: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
: min f(x)
: s.t. g(x) < = 0
: 的 KKT Condition 有三組:
: (1) dL/dx = 0
: (2) λg(x) = 0
: (3) λ > = 0
: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
: 套用到例題中：
: f(x) = x
: g(x) = x^2 - 4
: L(x) = x + λ( x^2 - 4 )
: (KKT 1) dL/dx = 1 + 2λx = 0
: => x = -1/(2λ)
: (KKT 2&3)
: λg(x) = 0 =>
: Case1 :
: λ= 0 (內點) & g(x) =/= 0
: λ = 0 => x = -1 / 0 (不存在 / 或是說，超越了 g(x)<0 的限制範圍)
: (不過，眼尖的人應該不難發現，這個 x = -1/0 = -Inf
: 這...正好是無限制條件下 min x 的正解...從這邊也可以看出
: 當 λ = 0 時...所解出來的...就正好會是無限制條件的狀況...)
: Case2 :
: λ>0 (邊界撞到) & g(x) = 0
: 所以可以把 x = -1/(2λ) 帶入 g(-1/(2λ)) = 0
: 可以解出 λ = 1/4 or -1/4
: 分別對應到 x = -2 or 2
: 剛好一個是最大值一個是最小值！
: 這不是巧合...不然 KKT 就不用加上第三條要求 λ > = 0 了
: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
: 如果把題目換一換
: min x^2
: s.t. x^2 - 4 < = 0
: L(x) = x^2 + λ( x^2 - 4 )
: (KKT 1) dL/dx = 2x + 2λx = 2x(1+λ) = 0
: => x = 0 or λ = -1
: (KKT 2: λg(x) = 0 ) 告訴我們
: Case1 :
: 如果 x = 0
: => g(0) = -4 =\= 0
: => λ = 0 (這代表...在g(x) <= 0 的內點，不在邊界)
: Case 2:
: 如果 λ = -1 =\= 0 (這代表...撞到 g(x) 的邊界...不再內點...)
: 則 g(x) = 0 => x = 2 or -2
: 事實上...這兩個點都是最大值 而非題目要的 最小值！！
: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
: 在這兩個例子中，我們可以很清楚地感覺到 λ 所扮演的角色
: 當 λ = 0 的時候，就代表 g(x) < = 0 這個限制
: 並不會影響到 f(x) 求極值
: 而當 λ =\= 0 的時候...就代表限制式產生了一些影響力
: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
: 真正的解讀上...可以從兩個方向來思考
: (1) 可以讓 f 變更好的方向
: (2) 可以走的方向
: 如果 f 是可微分的，不論單變數或多變數...
: 基本上就是 讓 < Df , d > 內積小於 0 的方向 d 就是了
: 比方說在第一個例子中
: f(x) = x => Df(x) = 1
: => < 1 , a > = a < 0
: => a < 0
: 意思是說...
: ** 只要往左走...就會變小
: 用數學來說就是 ...... f(x+a) < f(x) for some a < 0
: 在第二個例子中
: f(x) = x^2 => Df(x) = 2x
: => <2x , a > = 2xa < 0
: => Case 1: x>0 => a<0 / Case 2: x<0 => a > 0
: 和我們所認知的拋物線一樣...
: 在x<0 的地方要往右走才會變小 / x>0 的地方則往左走
: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
: 如果沒有限制式的話...也就是說 x 可以是任何實數的話
: 極值始終會滿足： ** 沒有任何方向可以讓 f 變小的那種 x 點！！
: 也就是說 如果 x* 是極小值的話
: 會滿足 < Df(x*) , a > = 0 for all (a向量)
: 所以 可以導出 Df(x*) = (0向量)
: 因此，如果沒有限制式的話...
: min x 並沒有極小值... 因為所有的實數 x 都滿足 Df(x) = 1
: 不過...加上限制式...就有極小值囉......！！！
: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
: 加上限制式後...就會出現
: f 在 x* 點...有可以變小的方向 ... 但是受到 g 的影響...所以不能走！！！
: 因此...那些點可以走？ 那些點不能走？ ...這就是個有趣的問題了！
: 對於那些 g(x) < 0 的點來說，基本上任何能讓 f 變小的方向，都是可以走的！
: 因此，只有在 g(x) = 0 時...會對方向造成限制
: 從上面兩個例子的限制式來看
: g(x) = x^2 - 4
: 邊界點是 x = 2 or -2
: 計算一下在邊界上的微分
: Dg(x) = 2x
: => Dg(2) = 4 > 0 and Dg(-2) = -4 < 0
: 不難發現 .......
: 在 g(x*) = 0 這種邊界上的點
: 它可以移動的方向 ... 也只有 <Dg(x*) , d > < 0 的 d 方向
: 才會保持 g(x*+d) < g(x*) = 0 的限制式
: 在上面的例子...就是 在 x = 2 時....只能往左移...才會回到 x^2 - 4 < 0
: 另外一邊是 在 x = -2 時，因為 Dg(-2) = -4
: => <Dg(-2) , d > = -4d < 0 => d > 0 只能往右移
: 從第一個例子( min x s.t. x^2-4<=0 )來看...就可以看得很清楚了
: 在 x = 2 時，維持 g < 0 的範圍的方向是 "向左"
: 讓 f 變小的方向也是 "向左" ... 因此 f 有方向可以再繼續變小
: 但是在 x = -2 的地方，維持 g < 0 的方向是 "向右"
: 但是讓 f 變小的方向還是 "向左" ... 因此 f 沒有方向可以再繼續變小
: 也就是達到最小值了！
: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
: 最後...嚴格來說
: 你的題目應該是：
: min xy
: s.t.
: g1(x,y) = -x <= 0
: g2(x,y) = -y <= 0
: h1(x,y) = x^2 + y^2 - 8 = 0
: 或是
: min -xy (就是 max xy 的case)
: s.t.
: g1(x,y) = -x <= 0
: g2(x,y) = -y <= 0
: h1(x,y) = x^2 + y^2 - 8 = 0
: 也就是說
: 真正的 Lagrange 應該寫成
: L1(x,y) = xy + λ1(-x) + λ2(-y) + λ3(x^2 + y^2 - 8 )
: L2(x,y) = -xy + λ1(-x) + λ2(-y) + λ3(x^2 + y^2 - 8 )
: (因為 x =/= 0 ; y =/=0 所以......
: 解的時候要注意： λ1 = 0 ; λ2 = 0 才行！ ... )
: 但這樣的話...就會回到原本的 Lagrange
: L1(x,y) = xy + 0*(-x) + 0*(-y) + λ3(x^2 + y^2 - 8 )
: L2(x,y) = -xy + 0*(-x) + 0*(-y) + λ3(x^2 + y^2 - 8 )
: 所以...直接用原本的上面兩種 Lagrange 也是 ok 的
: ※ 引述《RAINDD (I'm Kenino.)》之銘言：
: : 原PO你好，你是初學微積分嗎？
: : 這題其實不難，甚至也不需要用到Lagrange Multiplier就可以解了。
: : 我這麼說吧，個人以為困難的地方在於初學時"正確"而且"完整"建立觀念。
: : 個人分享一些當初學習時的心得與經驗，
: : 不敢講我說得很對，但提出來供你做參考。
: : 1. 首先，先想想，什麼叫最大值？最小值？極大值？極小值？
: : 既然叫"大"、叫"小"，就意味著是經過比較得到的結果。
: : 依我看，你困擾的點在於，經過求解方法得到只有一個極值時，
: : 我怎麼知道它是最大或最小？
: : 然而，以這題來看，只有一個極值存在嗎？其實還有，只是你缺視了，
: : 2. 即使，真的只有一個極值發生時，你又如何得知它是最大、最小值呢？
: : 舉個例： y = x^2 - 2x + 3，我們知道 x = 1 時， y 有最小值 2。
: : 如何知道的？用配方法呀，一階微分求極值點、二階微分求開口，
: : 甚至算幾不等式、柯西不等式…等任何可應用的方法，
: : 都能幫助找maxima,minima,extrema，且看各憑本事。
: : 3. 再說Lagrange Multiplier方法，▽f = λ * ▽g，
: : 聯立求解時，常常不是那麼地在意特徵乘數值 λ 。
: : 若你練習的題目做多了，會發現λ值的大小與"+""-"符號，
: : 似乎能猜知該點是極大值或是極小值。
: : 而微積分課本也並不討論λ值與extrema的關連性。
: : 於此，我們並不多做討論，有興趣的話不妨自行研究或多找題目練習。
: : 4. 開始解題：
: : 依題意，我們先弄清楚目標函數、和限制函數。
: : 目標函數： f(x,y) = x*y
: : 限制函數： x^2 + y^2 = 8、 x > 0 、 y > 0
: : {依題意，限制函數為在xy平面上，x^2 + y^2 = 8，且 x > 0 , y > 0
: : 為第一象限的四分之一圓弧曲線。
: : 注意，題目並非x^2 + y^2 ≦ 8，所以並不包含圓內的區間}
: : 極值發生的地方：(1)端點 (2)邊界上 {勿忘端點}
: : (1)端點：(x,y) = (2√2,0) 及 (0,2√2)
: : (2)邊界上：應用Lagrange Multiplier解得 (x,y) = (2,2)有一極值
: : 代入 (2√2,0)、(0,2√2)、(2,2)求f(x,y)並比較大小，
: : 得知最大值為 f(2,2) = 2*2 = 4
: : 最小值為 f(2√2,0) = f(0,2√2) = 0
: : 於此，作答即完成。
: : 若你不放心 4 是否為最大值，就將限制函數x^2 + y^2 = 8參數化再
: : 用單變數函數求極值的方法解看看。
: : 若你能將題目轉化成解析幾何的意義進一步瞭解此題那又更好。
: : 5. 補充：
: : 若限制函數為：x^2 + y^2 ≦ 8、x>0、y>0
: : 極值發生的地方：(1)端點 (2)邊界上 (3)區間內
: : (1)端點有三：(x,y) = (2√2,0)、(0,2√2)、(0,0)
: : (2)邊界有三：y=0時，0≦x≦2√2、
: : x=0時，0≦y≦2√2、
: : x^2 + y^2 = 8。
: : (3)區間內：解 df/dx = 0
: : df/dy = 0 之聯立方程式。
: : 詳細的解答內容，就留給你自己發揮囉。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 203.74.126.44