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

看板Math作者 (懶黑)時間9年前 (2016/11/09 14:59), 編輯推噓0(0017)
留言17則, 2人參與, 最新討論串1/1
想將數量約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

11/09 15:06, , 1F
本書網址連結
11/09 15:06, 1F

11/09 15:11, , 2F

11/09 17:05, , 3F
解simplex要用到approximation? L1-norm算是標準題
11/09 17:05, 3F

11/09 17:05, , 4F
直接用matlab解吧 矩陣帶進去就好了 linprog
11/09 17:05, 4F

11/09 17:10, , 5F
工程上比較普遍用L2-norm L1-norm好像沒解析解
11/09 17:10, 5F

11/09 17:14, , 6F
WIKI上是說L1-norm推薦用simplex但要用
11/09 17:14, 6F

11/09 17:14, , 7F
Simplex Method for Bounded Variables這種方式
11/09 17:14, 7F

11/09 17:16, , 8F
不過有點不同就是L1的simplex目標是RHS要在0<=b<=2
11/09 17:16, 8F

11/09 17:16, , 9F
才被判斷是最佳解 不是單純看目標式能否繼續增長?
11/09 17:16, 9F

11/09 17:27, , 10F
如果我理解錯誤的話還煩請糾正...說實話不太了解...
11/09 17:27, 10F

11/09 17:32, , 11F
或者是否有其他用simplex解norm-1的例題能供參考?
11/09 17:32, 11F

11/09 17:33, , 12F
多看幾種說法可能會理解比較快
11/09 17:33, 12F

11/09 17:38, , 13F
wiki中關於最小絕對值的說明
11/09 17:38, 13F

11/09 17:39, , 14F
11/09 17:39, 14F

11/10 07:59, , 15F
應該先把問題轉換成LP form 再用simplex解
11/10 07:59, 15F

11/10 08:00, , 16F
至於怎麼轉換 Linear Programming 專書裡面都有
11/10 08:00, 16F

11/10 08:03, , 17F
看一下Bertsimas Tsitsiklis的書 linear optim
11/10 08:03, 17F
文章代碼(AID): #1O8ibZ4a (Math)