Re: [分析] Lagrange乘數法是否saddle (500p)

[LiamIssac (Madchester是這群人壓根)]

※ 引述《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，我沒看過不知道有沒有)
: 第二個困難一樣是很難判斷正負定。
: 也許這題可以用不等式去算出來，不過我沒想到。
其實這問題很簡單

就是判斷最佳化問題的convexity

至於什麼是convex function

這部分讓原po去了解一下


所以每遇到一個optimization問題

首先要檢查的部分有兩個

1. objective function

檢查是否為convrx function

2. feasible domain S

檢查是否為convex set



如果兩個都是convex

那就代表這問題是convex

所求的的解就保證是global optimal

但如果其中一個不是

那你找到的解就只能說是local optimal

即便你真的找到global解

在最佳化領域還是會稱之為local

(在小問題可以這樣 但我們討論general problem)

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.227.9.73
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1514522212.A.5EA.html
推 znmkhxrw    : L大你的convex function on convex set
→ znmkhxrw    : 有定理完整敘述可以參考嗎
推 znmkhxrw    : 至於你說的要檢查f是否在限制條件下是convex函數
→ znmkhxrw    : 照定義很難做吧...
→ LiamIssac   : 不會 分開判斷就好 objective function就看2階微分
→ LiamIssac   : 的hessian matrix是否為正定postivie definite
→ LiamIssac   : 而你的domain是否為convex set 就是看這個集合內任
→ LiamIssac   : 兩點的連線是不是全部都在這個集合裡面 最簡單的例
→ LiamIssac   : 子就是正圓
→ LiamIssac   : 你畫一個圓 在圓裡面隨便找兩個點 然後畫一條直線連
→ LiamIssac   : 起來 這條線上的點如果都在這個圓內 那就是convex s
→ LiamIssac   : et
→ LiamIssac   : 假設你今天畫的是個凹的圖形 你會發現你一定可以找
→ LiamIssac   : 到兩個點的連線 會超出這個圖形外面 那我們統稱nonc
→ LiamIssac   : onvex set 這種問題就是Np hard 只能求近似解
→ LiamIssac   : 而你的問題中的S在2維 就是個單位為1的正方形 落在
→ LiamIssac   : 第一象限 你就按照上面的方法去check就知道是不是co
→ LiamIssac   : nvex