作者chemmachine (chemmachine)
看板Math
標題Re: [分析] Lagrange乘數法是否saddle (500p)
時間Fri Dec 29 13:52:41 2017
※ 引述《chemmachine (chemmachine)》之銘言:
: 剛剛想到一件事,在wiki的Hessian matrix 的broaden matrix有一句話
: x_1+...x_n=1可以代入f(x_1,x_2,...x_n)變為
: f(x_1,x_2,.....,1-x_1-x_2-...x_n-1)這樣你的f就沒有restrian了。
: 這樣二維的鞍點可以說明為何變為極大值。
: f變為4x_1^2*(1-x_1)^2
: f'=8(x_1-x_1^2)(1-2x_1)
: 0,1,1/2是critical point
: 代入f"=8-48x_1+48x_1^2
: 可得f"(1/2)=-4故1/2變為極大值。
: 如果我f(1/6,1/6,1/6,1/6,1/6,1/6)<f(1/6,1/6,1/6,1/6,1/12,1/4)沒算錯
: ,6維時它不是極大值。然後我的圖片文章那裏高維度h(f)算錯,因為它沒算
: broaden matrix。真的要算就要算broaden hesssian或是將x_n=1-x_1-x_2-...x_(n-1)
: 代入算。
: 流程圖:
: restrain是等式
: 檢查邊界值代入,檢查拉格朗日方程組,盡量用方程組的單調性或只有一實數解
: 讓方程組只有對稱解。檢查不可微分點。你的原函數0.5微分後會跑到分母,所以也會有不可
: 可微分點,但剛好它是邊界點0,1。找出所有臨界點後,用broaden hessian或消去
: restrain的hessian觀察是極大,極小或鞍點。這個方法在觀察hessain會遇到瓶頸,因為
: 正定,負定很難判斷,大部分用z^tHz>0或z^tHz<0或找出所有的lammda的正負,只要
: lammda有正有負就很難判斷。高維度時手算不太可能算出所有lammda值。三次微分以上
: 的判別我不會,wiki說有。但是計算應該更複雜。(最主要缺點是海森很難判斷正負定)
: restrain是不等式
: 網路上線代啟示錄或k-k-t條件或一些網路文章有例題,你這題0,1我就直接用邊界點
: 代入,不用不等式做。不等式它列式會有不等式的拉格朗日方程組。通常也會有對稱
: 解,但第一個困難是你很難說明它只有對稱解,比restrain是等式的情形更複雜。
: 解出三種臨界點(邊界點、微分0、不可微分)後一樣代入hessian matrix或broaden
: matrix(這個broaden matrix是不等式restrian的broaden,我沒看過不知道有沒有)
: 第二個困難一樣是很難判斷正負定。
: 也許這題可以用不等式去算出來,不過我沒想到。
六維的情形突然想到比較好的解釋。(1/6,1/6,1/6,1/6,1/6,1/6)算出來是區域極
小,可用excel觀察(1/6,1/6,1/6,1/6,1/12,1/4)、
(1/6,1/6,1/6,1/6,1/3,0)。 那區域極大在哪?
(1,0,0,0,0,0)也是極小=0但若計算(1/2,1/2,0,0,0,0)發現這個值比較大
(1/2,1/2,0,0,0,0)是邊界值。所謂邊界值是只要某x_i=0就是
(x_j=1會讓某個x_i=0)所以極大極小也會藏在邊界。
海森矩陣能判斷你要的臨界點是區域極大極小或鞍點。但這題邊界點太多,所以
想消去邊界點,或許就要把0<=x_i<=1看作不等式,用k-k-t的條件消去邊界點不等式。
這個計算很複雜,我就不做了,你可以試試看。
我能提供的參考資料就是網路上的k-k-t condition 、推廣形
拉格朗日、線代啟示錄、hessian matrix;marsden、fridberg的hessian
裡面很多例題你做熟之後應該可以看懂大部分的拉格朗日乘子的文章。
像統計學裡likelihood function我用上面流程圖觀察之後是沒有什麼問題,網路上
的例題通常題目也很簡單,幾乎都等式,或不等式在邊界,算出來結果沒啥問題。
這篇文章論文目標函數太複雜,在極大極小sup那邊結論也許有點武斷。
還有一個觀念很重要,大部分給你的domain都是compact,這題就是。
給你的函數大部分都是多變量連續,這題也是。連續函數會將compact
映射成compact。extreme value theorem就是講這個,所以它一定有極大和極小點
,我們又知道極值一定在邊界點、微分零、不可微分三選一。所以不會都是鞍點。
一定有極大和極小。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 218.161.61.7
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1514526764.A.CC7.html
→ LiamIssac : KKT with constraints不難 就是我上傳的圖的算法 可 12/29 14:03
→ LiamIssac : 以參考 12/29 14:03
推 JI1 : medium 12/29 14:05
→ chemmachine : 推L大,你是我遇到第一個懂KKT的。覺得KKT三個人 12/29 14:12
→ chemmachine : 應該很寂寞。論文沒人看。KKT和KMT應該有點不同,懂 12/29 14:13
→ chemmachine : KMT的人應該很多,懂KKT的人應該很少。(逃~~) 12/29 14:14
推 LiamIssac : KKT很有名阿 有學operations research的這算是必修( 12/29 14:15
→ LiamIssac : nonlinear optimization) C大看起來應該是數學系統 12/29 14:15
→ LiamIssac : 訓練出來的 所以比較少接觸這部分 12/29 14:15
推 LiamIssac : 舉凡 管理科系 甚或 工業工程這些都是必修 所以KKT 12/29 14:17
→ LiamIssac : 不算寂寞啦 哈哈 12/29 14:17
→ chemmachine : 對耶,我是學純數的碩士生XD一猜就中。 12/29 14:18