b******v
发帖数: 1493 | 1 min 1/2 x'H x + f'x
s.t. \sum_{i~j} max{|x_i|, |x_j|} <= C
其中i,j是一个网络中的节点编号，而i~j表示节点i,j是有边相连的
这样的问题该如何求解？（可以假定H是正定矩阵） |
d*****1
发帖数: 1837 | 2 绝对值和max相当于整型变量，你可以引入binary variable to eliminate max and
absolute |
b******v
发帖数: 1493 | 3 带binary variable的quadratic programming容不容易求解？
感觉引入太多binary variable的话，计算量会变得很大?
【在 d*****1 的大作中提到】
: 绝对值和max相当于整型变量，你可以引入binary variable to eliminate max and
: absolute
|
i******t
发帖数: 370 | 4 你的constraint不就是
\sum_{i~j}t_ij <= C
x_i,-x_i,x_j,-x_j <= t_ij
每条edge多1个variable，4条constraint
【在 b******v 的大作中提到】
: min 1/2 x'H x + f'x
: s.t. \sum_{i~j} max{|x_i|, |x_j|} <= C
: 其中i,j是一个网络中的节点编号，而i~j表示节点i,j是有边相连的
: 这样的问题该如何求解？（可以假定H是正定矩阵）
|
b******v
发帖数: 1493 | 5 我也是这样做的，可是引入新变量后H矩阵就变成半正定了
用matlab的quadprog求解时经常不收敛
【在 i******t 的大作中提到】
: 你的constraint不就是
: \sum_{i~j}t_ij <= C
: x_i,-x_i,x_j,-x_j <= t_ij
: 每条edge多1个variable，4条constraint
|
c*m
发帖数: 1114 | 6 这个很正常哇。带约束的quadratic program在H正定的情况下不保证收敛，因为增加拉
格朗日乘子后Hessian就不是H了。
【在 b******v 的大作中提到】
: 我也是这样做的，可是引入新变量后H矩阵就变成半正定了
: 用matlab的quadprog求解时经常不收敛
|
b******v
发帖数: 1493 | 7 那应该怎样做才能提高收敛的概率？
我把迭代次数已经由默认的200改成50,000，还是经常不收敛
【在 c*m 的大作中提到】
: 这个很正常哇。带约束的quadratic program在H正定的情况下不保证收敛，因为增加拉
: 格朗日乘子后Hessian就不是H了。
|
b******v
发帖数: 1493 | 8 update: 改用CVXhttp://cvxr.com/cvx/就没有不收敛的问题了
【在 b******v 的大作中提到】
: 那应该怎样做才能提高收敛的概率？
: 我把迭代次数已经由默认的200改成50,000，还是经常不收敛
|
c*m
发帖数: 1114 | 9 hehe, 理论上讲QP方法无法避免你上面的不收敛问题。
CVX能够解决很大程度上是因为它用的不再是传统的QP, 这样的软件比较著名的市面上
还有很多。而且对于复杂的约束CVX也未必收敛，因为可能没有解或有无穷多组解。
【在 b******v 的大作中提到】
: update: 改用CVXhttp://cvxr.com/cvx/就没有不收敛的问题了
|
i******t
发帖数: 370 | 10 对阿，用cvx就好了，如果担心效率可以考虑mosek。
matlab的linprog, quadprog就是一陀s**t.
【在 b******v 的大作中提到】
: update: 改用CVXhttp://cvxr.com/cvx/就没有不收敛的问题了
|
