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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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.
|
|
