[線代] Dual of dual problem 線性規劃

[kusoayan (Bert)]

大家好，想請問要怎麼導出 dual problem 的 dual problem 呢？
一般 primal 是 minimize objective，但是 dual 是 maximize objective
這樣要先把 dual 換成 minimize 之後再推導嗎？

例如 Linear problem
Primal:

        min  (c^T)x
 subject to  Ax <= b  (這裏的 <= 是 element-wise 的小於等於)

那他的 Lagrangian 就是 L(x, v) = (c^T)x + v^T(Ax - b)
然後 dual function g(v) = inf L(x,v)
                           x

而他的 Dual:

        max -(b^T)v
 subject to (A^T)v + c = 0, v >= 0

這時候要怎麼算他的 dual function？是要先把 max -(b^T)v 換成 min (b^T)v 嗎？
還是直接照算 Lagrangian？
在算 dual function 的時候一樣是對 Lagrangian 取 inf 嗎？

謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.235.219.199
※ 文章網址: http://www.ptt.cc/bbs/Math/M.1397959239.A.40A.html
推 recorriendo :dual problem的dual就是原問題啊
Dual of dual problem 不一定都是原問題吧？
我知道這裏會是原問題，但是不知道怎麼照定義推導
※ 編輯: kusoayan (36.235.219.199), 04/20/2014 11:44:28
推 HmmHmm      :你可以把(A^T)v + c = 0, v >= 0都寫成一個不等式
→ HmmHmm      :[A]   <= -c    然後照原本方法算 Lagrangian
→ HmmHmm      :[-A^T]v<=c   min 或 max 換不換隨便
→ HmmHmm      :[-I] v<=0  反正記得 max is dual to min
→ HmmHmm      :然後這樣 dual 回去會有多的variable x_1, x_2, x_3
→ HmmHmm      :設 x=x_2-x_1 應該就沒問題了
→ mp19990920  :最好是推的出來啦，constrain function寫錯了...
→ mp19990920  :http://en.wikipedia.org/wiki/Linear_programming
→ mp19990920  :object function 也不對
推 HmmHmm      :他寫的不是 Standard form, 但是並沒有哪裡寫錯
→ HmmHmm      :我的確推導出來過上面也寫了方法
→ HmmHmm      :如果mp19990920覺得我哪裡寫錯請不吝指出
推 HmmHmm      :http://www.mpi-inf.mpg.de/departments/d1/teaching
→ HmmHmm      :ss11/OPT/lec8.pdf 第三頁中間可以找到他那種寫法
→ kusoayan    :謝謝，這的確是非 standard form，我會試着推推看！
→ sneak       : 他寫的不是 Stand https://daxiv.com
→ muxiv       : 設 x=x_2-x_1 https://moxox.com