[分析] 發問 simplex解最小絕對值(norm1)問題

[lazyblack (懶黑)]

想將數量約20個左右的量測數據(xi,yi) i=1~20以多項式擬合最小絕對值誤差
已找到相關文獻資料但卻看不懂其中部分推導過程

google有Numerical Linear Approximation in C這本書的PDF檔
p146~p148 5.4節說明Dual Simplex解norm1問題的步驟

目前的問題是,第一個步驟先假設所有zi-fi(MarginalCost) < 0
的變數皆為UpperBound的原因為何?

因網上看了一些simplex教學，裡面變數會變成UpperBound
幾乎都是在求解過程中判斷，為何在這個地方能直接將
所有MarginalCost<0的變數全判別為UpperBound呢...

另外由於小弟數學底子薄弱(機械系)，希望能用非數統相關科系也
懂的語言來說明...

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.230.23.20
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1478674787.A.124.html
→ lazyblack   : 本書網址連結
→ lazyblack   : http://tinyurl.com/oo8y8xq
→ LiamIssac   : 解simplex要用到approximation? L1-norm算是標準題
→ LiamIssac   : 直接用matlab解吧 矩陣帶進去就好了 linprog
→ lazyblack   : 工程上比較普遍用L2-norm  L1-norm好像沒解析解
→ lazyblack   : WIKI上是說L1-norm推薦用simplex但要用
→ lazyblack   : Simplex Method for Bounded Variables這種方式
→ lazyblack   : 不過有點不同就是L1的simplex目標是RHS要在0<=b<=2
→ lazyblack   : 才被判斷是最佳解  不是單純看目標式能否繼續增長?
→ lazyblack   : 如果我理解錯誤的話還煩請糾正...說實話不太了解...
→ lazyblack   : 或者是否有其他用simplex解norm-1的例題能供參考?
→ lazyblack   : 多看幾種說法可能會理解比較快
→ lazyblack   : wiki中關於最小絕對值的說明
→ lazyblack   : https://goo.gl/YZzEPS
→ LiamIssac   : 應該先把問題轉換成LP form 再用simplex解
→ LiamIssac   : 至於怎麼轉換 Linear Programming 專書裡面都有
→ LiamIssac   : 看一下Bertsimas Tsitsiklis的書 linear optim