当前在线人数16920
首页 - 分类讨论区 - 学术学科 - 数学版 - 同主题阅读文章

此篇文章共收到打赏
0

  • 10
  • 20
  • 50
  • 100
您目前伪币余额:0
未名交友
[更多]
[更多]
optimization问题请指教
[版面:数学][首篇作者:EM] , 2017年04月04日22:45:05 ,1065次阅读,6次回复
来APP回复,赚取更多伪币 关注本站公众号:
[分页:1 ]
EM
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 1 ]

发信人: EM (一个胖子), 信区: Mathematics
标  题: optimization问题请指教
发信站: BBS 未名空间站 (Tue Apr  4 22:45:05 2017, 美东)

Given mu_i, sigma_i, c_i, P_0, how to minimize the quantity over {P_i}

sum_{i=1}^n sigma_i^2 P_i^2 - sum_{i=1}^n mu_i P_i + sum_{i=1}^n c_i|P_i-P_{
i-1}| + c_{n+1}|P_
n|

The problem is related to a shortest path problem but I am not sure how to
solve it
elegantly using finite steps of calculation.

Any suggestion is appreciated.


--
※ 修改:·EM 於 Apr  5 15:20:51 2017 修改本文·[FROM: 74.]
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 24.]

 
bigearmouse
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 2 ]

发信人: bigearmouse ((o)), 信区: Mathematics
标  题: Re: optimization问题请指教
发信站: BBS 未名空间站 (Thu Apr  6 13:50:40 2017, 美东)

not familiar with shortest path problem but just from what you wrote down, 
you can convert to a standard quadratic optimization problem and any
optimization library could solve it.


【 在 EM (一个胖子) 的大作中提到: 】
: Given mu_i, sigma_i, c_i, P_0, how to minimize the quantity over {P_i}
: sum_{i=1}^n sigma_i^2 P_i^2 - sum_{i=1}^n mu_i P_i + sum_{i=1}^n c_i|P_i-P
_{
: i-1}| + c_{n+1}|P_
: n|
: The problem is related to a shortest path problem but I am not sure how to
: solve it
: elegantly using finite steps of calculation.
: Any suggestion is appreciated.



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 193.]

 
EM
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 3 ]

发信人: EM (一个胖子), 信区: Mathematics
标  题: Re: optimization问题请指教
发信站: BBS 未名空间站 (Thu Apr  6 23:46:18 2017, 美东)

Yeah the problem can be casted as a quadratic problem
itself is related to fused lasso if any one is interested where it came from
in fact i know the problem might be solved in finite steps (no checking
convergence or small steps etc.) but i don't know how :(

【 在 bigearmouse ((o)) 的大作中提到: 】
: not familiar with shortest path problem but just from what you wrote down,
 
: you can convert to a standard quadratic optimization problem and any
: optimization library could solve it.
: _{


--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 24.]

 
drburnie
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 4 ]

发信人: drburnie (专门爆料), 信区: Mathematics
标  题: Re: optimization问题请指教
发信站: BBS 未名空间站 (Fri Apr  7 08:40:38 2017, 美东)

Define X_i = P_i-P_{i-1}.

这问题最后变成一个L1 penalized QP,QP的Hessian不是diagonal矩阵,没有closed
form solution。

不过这个问题smooth而且strongly convex,用Proximal Gradient可以很容易的算出来
,线性收敛,速度非常快。

【 在 EM (一个胖子) 的大作中提到: 】
: Given mu_i, sigma_i, c_i, P_0, how to minimize the quantity over {P_i}
: sum_{i=1}^n sigma_i^2 P_i^2 - sum_{i=1}^n mu_i P_i + sum_{i=1}^n c_i|P_i-P
_{
: i-1}| + c_{n+1}|P_
: n|
: The problem is related to a shortest path problem but I am not sure how to
: solve it
: elegantly using finite steps of calculation.
: Any suggestion is appreciated.



--

※ 来源:·BBS 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 24.]

 
bigearmouse
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 5 ]

发信人: bigearmouse ((o)), 信区: Mathematics
标  题: Re: optimization问题请指教
发信站: BBS 未名空间站 (Fri Apr  7 11:42:41 2017, 美东)

exactly, if your n is not too big order of 10000, you should converge in
100ms

【 在 drburnie (专门爆料) 的大作中提到: 】
: Define X_i = P_i-P_{i-1}.
: 这问题最后变成一个L1 penalized QP,QP的Hessian不是diagonal矩阵,没有closed
: form solution。
: 不过这个问题smooth而且strongly convex,用Proximal Gradient可以很容易的算出来
: ,线性收敛,速度非常快。
: _{



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 107.]

 
uglyOne
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 6 ]

发信人: uglyOne (我很丑), 信区: Mathematics
标  题: Re: optimization问题请指教
发信站: BBS 未名空间站 (Sun May 21 15:06:10 2017, 美东)

re


【 在 EM (一个胖子) 的大作中提到: 】
: Given mu_i, sigma_i, c_i, P_0, how to minimize the quantity over {P_i}
: sum_{i=1}^n sigma_i^2 P_i^2 - sum_{i=1}^n mu_i P_i + sum_{i=1}^n c_i|P_i-P
_{
: i-1}| + c_{n+1}|P_
: n|
: The problem is related to a shortest path problem but I am not sure how to
: solve it
: elegantly using finite steps of calculation.
: Any suggestion is appreciated.


--
你若口里认耶稣为主,心里信神叫他从死里复活,就必得救。因为人心里相信,就可以
称义。口里承认,就可以得救。(罗马书第十章第九、十节)



※ 来源:·BBS 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 141.]

 
oldwillow
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 7 ]

发信人: oldwillow (老柳树), 信区: Mathematics
标  题: Re: optimization问题请指教
发信站: BBS 未名空间站 (Mon May 22 10:28:13 2017, 美东)

I just tidy up your question as follows, Hope it helps.


Given μ_i, σ_i, c_i, X0, how to minimize the quantity over {Xi}
  
∑_i^n   σ_i^2 Xi^2 + ∑  (c_i - μ_i) Xi - ∑  c_i X(i-1) + c_{n+1}*X_n


=> 
           
∑_i^n  Ai (X_i - Bi)^2  -  ∑  c_i {X_{i-1} - B_{i-1}} + constant_i
  
where Ai, Bi are new known constants.


The original problem is thus reduced to optimization of this,
  
∑  Ai (X_i - bi)^2  - ∑  c_i (X_{i-1} - b_{i-1}) 
  

i.e. this
                   
∑  Ai X_i'^2 - ∑  c_i X_{i-1}'  := F


At least local mimimum (maximum) can be found by ∂F/∂Xi = 0.
=>

∑ [ 2*Ai*Xi' - c_{i+1) ] = 0
  

By the way, are you working on something related to "The Expectation-
Maximization (EM) Algorithm"?




【 在 EM (一个胖子) 的大作中提到: 】
: Given mu_i, sigma_i, c_i, P_0, how to minimize the quantity over {P_i}
: sum_{i=1}^n sigma_i^2 P_i^2 - sum_{i=1}^n mu_i P_i + sum_{i=1}^n c_i|P_i-P
_{
: i-1}| + c_{n+1}|P_
: n|
: The problem is related to a shortest path problem but I am not sure how to
: solve it
: elegantly using finite steps of calculation.
: Any suggestion is appreciated.





--
※ 修改:·oldwillow 於 May 22 11:21:56 2017 修改本文·[FROM: 198.]
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 198.]

[分页:1 ]
[快速返回] [ 进入数学讨论区] [返回顶部]
回复文章
标题:
内 容:

未名交友
将您的链接放在这儿

友情链接


 

Site Map - Contact Us - Terms and Conditions - Privacy Policy

版权所有,未名空间(mitbbs.com),since 1996