為什麼這篇convex function定義鄉民發文收入到精華區：因為在convex function定義這個討論話題中，有許多相關的文章在討論，這篇最有參考價值！作者raki237 (Raki)看板Math標題[其他] 如何證明convex function?時...
我是工科的學生，本身沒學過linear programming和nonlinear programming
現在想要解一個nonlinear programming的問題
聽說如果objective function如果是convex function會比較容易解
但是我不知道要怎麼證明一個很複雜的function是convex
function的樣子
一部分是x1*x2+x3*x4+...+xn*xn+1
另一部分是線性的，大概這樣的形式x1+x2+...+xn
objective function=x1*x2+x3*x4+...+xn*xn+1+x1+x2+...+xn
請問這種形式的functionc是不是convex?
要怎麼檢驗或證明呢?
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.34.221.212
※ 文章網址: http://www.ptt.cc/bbs/Math/M.1419056832.A.9F6.html
→ yyc2008 : 不是有定義嗎? 12/20 14:40
→ wohtp : 你的二次項都是 x_(2n-1) * x_(2n) 這樣子，每一對 12/20 17:26
→ wohtp : 確定不會有相同的x_i出現在不同兩項裡面嗎？ 12/20 17:27
→ wohtp : 如果這樣的話你還真幸福，好簡單的函數 12/20 17:28
→ wohtp : 總之先換個變數，例如你不要用 x_1, x_2，改用 12/20 17:29
→ wohtp : (x_1 + x_2), (x_1 - x_2) 12/20 17:30
→ wohtp : 然後你就可以看到，本來纏在一起的 x_1 * x_2 12/20 17:31
→ wohtp : 被拆開了，可喜可賀 12/20 17:31
→ wohtp : 後面的比照辦理 12/20 17:32
糟糕，會有相同的x_i出現在不同項Orz
這樣會困難很多嗎?
我再描述的詳細一點好了
objective function=x_1*x_2+x_2*x_3+x_4*x_5+x_5*x_6+...+x_(n-2)*x_(n-1)+x_(n-1)*x_n
+x_1+x_2+...+x_n
以上是忽略每項的係數啦，我想系數應該是沒啥大影響?
這樣還有可能是convex嗎?
※ 編輯: raki237 (1.34.221.212), 12/21/2014 00:42:49
→ recorriendo : 你這是quadractic programming啊 算很簡單的情況了 12/21 08:37
→ recorriendo : quadratic programming屬convex optimization的特例 12/21 08:39
謝謝樓上，我看懂了!XD
變數兩兩相乘+變數相加，這樣的型式應該都算是quadratic programming對吧?
雖然兩兩相乘的部分可能有些項是我不需要的，但沒差，該項係數是0就行了
不知道我理解的對不對?
畢竟我都是自己找原文資料看的，也沒學過這些，可能不太會XD
不過我的變數都是binary，所以算起來也不太快Orz
※ 編輯: raki237 (1.34.221.212), 12/21/2014 16:19:38
→ recorriendo : 你的變數是binary? 那你這是integer programming 12/22 02:17
→ recorriendo : 一般來說最佳化理論是建立在連續函數上 只限定某些 12/22 02:18
→ recorriendo : 整數的問題是一個更麻煩的層次的問題 12/22 02:19
其實我只想知道這樣的function會不會是convex function
因為我有一個可以解convex MINLP的solver
但是我必須確定一下，我的objective是不是convex
還是說binary型態的問題，有更好的方法可以使用？
※ 編輯: raki237 (140.113.88.41), 12/22/2014 15:29:52
→ recorriendo : 我後來又查過發現記錯了 quadratic要正定才是convex 12/23 03:31
→ recorriendo : 看你的solver是用什麼方法 如果是gradient descent 12/23 03:32
→ recorriendo : 那麼不convex的問題也可以丟下去解 不過有可得到的 12/23 03:33
→ recorriendo : 只是局部最佳解 如果是其他方法(SDP、subgradient) 12/23 03:33
→ recorriendo : 那麼不一定能解不convex的問題 不過你應該找integer 12/23 03:34
→ recorriendo : programming的solver才是你需要的 12/23 03:35