EM 发帖数: 715 | 1 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 without using quadratic programming.
Any suggestion is appreciated. | b*********e 发帖数: 38 | 2 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 without using quadratic programming. : Any suggestion is appreciated.
| EM 发帖数: 715 | 3 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 :(
【在 b*********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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. : : _{
| d******e 发帖数: 7844 | 4 Define X_i = P_i-P_{i-1}.
这问题最后变成一个L1 penalized QP,QP的Hessian不是diagonal矩阵,没有closed
form solution。
不过这个问题smooth而且strongly convex,用Proximal Gradient可以很容易的算出来
,线性收敛,速度非常快。
_{
【在 EM 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 without using quadratic programming. : Any suggestion is appreciated.
| b*********e 发帖数: 38 | 5 exactly, if your n is not too big order of 10000, you should converge in
100ms
【在 d******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Define X_i = P_i-P_{i-1}. : 这问题最后变成一个L1 penalized QP,QP的Hessian不是diagonal矩阵,没有closed : form solution。 : 不过这个问题smooth而且strongly convex,用Proximal Gradient可以很容易的算出来 : ,线性收敛,速度非常快。 : : _{
| u*****e 发帖数: 88 | 6 re
_{
【在 EM 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 without using quadratic programming. : Any suggestion is appreciated.
| o*******w 发帖数: 349 | 7 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 without using quadratic programming. : Any suggestion is appreciated.
|
|