p******m
发帖数: 353 | 1 我想解N个线性联立方程组， 但是必须至少找到一组非负解， 里边共有m个未知变量，
m >> N。 这样的解一定存在吗？如果不存在如何尽量找到一个比较接近的解， 但是
解必须是非负的。望高手赐教。 |
A*******r
发帖数: 768 | 2 线性规划
【在 p******m 的大作中提到】
: 我想解N个线性联立方程组， 但是必须至少找到一组非负解， 里边共有m个未知变量，
: m >> N。 这样的解一定存在吗？如果不存在如何尽量找到一个比较接近的解， 但是
: 解必须是非负的。望高手赐教。
|
i*****e
发帖数: 68 | 3 A system like this in general has infinitely many solutions. However, non-
negative solutions may not exist. Here is an example.
x+y=0
x-y-2z=4.
The general solution of the system is
x=c, y=-c, z=c-2 for arbitrary c. Clearly there are no non-neg solutions.
【在 p******m 的大作中提到】
: 我想解N个线性联立方程组， 但是必须至少找到一组非负解， 里边共有m个未知变量，
: m >> N。 这样的解一定存在吗？如果不存在如何尽量找到一个比较接近的解， 但是
: 解必须是非负的。望高手赐教。
|
A*******r
发帖数: 768 | 4 two-phase method
【在 i*****e 的大作中提到】
: A system like this in general has infinitely many solutions. However, non-
: negative solutions may not exist. Here is an example.
: x+y=0
: x-y-2z=4.
: The general solution of the system is
: x=c, y=-c, z=c-2 for arbitrary c. Clearly there are no non-neg solutions.
|
p******m
发帖数: 353 | 5 我是这么想的。我想把m个未知数重新用x^2来参数化，这样保证他们必然为非负。然后
把N个约束方程写成一个方程： [F1(x^2)]^2 + [F2(x^2)]^2 + ... + [FN(x^2)]^2，
然后用无约束的最优化方法（牛顿或者类牛顿法）把该方程最小化。如果该方程逼近0
， 那么所有的F(x^2)也会自动逼近0， 即所有的约束都满足；否则我也可以得到一组
比较接近的满足非负条件的解。 请问这个方法有什么缺陷吗？
【在 A*******r 的大作中提到】
: two-phase method
|
r*****f
发帖数: 247 | 6 可以归结为convex optimization，
假设你的线性方程写成 Ax=0. A已知，x=[x_1,x_2...]未知
则你的优化问题是， min x^TA^TAx
s.t. x_i>=0.
此问题是convex的，可以用interior point method 解。
我目前没有找到closed form
谁找到的话给我说一声。 |
A*******r
发帖数: 768 | 7 找到了也告诉我这一声
你们研究的 问题怎么都用这么高级的办法解哈
【在 r*****f 的大作中提到】
: 可以归结为convex optimization，
: 假设你的线性方程写成 Ax=0. A已知，x=[x_1,x_2...]未知
: 则你的优化问题是， min x^TA^TAx
: s.t. x_i>=0.
: 此问题是convex的，可以用interior point method 解。
: 我目前没有找到closed form
: 谁找到的话给我说一声。
|
A*******r
发帖数: 768 | 8 Google two-phase method
or find a book on linear programming
e.g., Linear programming and extensions by G. Dantzig
，
0
【在 p******m 的大作中提到】
: 我是这么想的。我想把m个未知数重新用x^2来参数化，这样保证他们必然为非负。然后
: 把N个约束方程写成一个方程： [F1(x^2)]^2 + [F2(x^2)]^2 + ... + [FN(x^2)]^2，
: 然后用无约束的最优化方法（牛顿或者类牛顿法）把该方程最小化。如果该方程逼近0
: ， 那么所有的F(x^2)也会自动逼近0， 即所有的约束都满足；否则我也可以得到一组
: 比较接近的满足非负条件的解。 请问这个方法有什么缺陷吗？
|
g*******o
发帖数: 4 | 9 上面提到的办法都很弓虽啊。。。。
好久以前学过一点点，都忘记了^_^
我想这个结论应该是不对的，
很简单的凡例在三维空间中，找两个平面的交线就是解集。。。
如果这条交线不落在全正的Quadrant，自然就没有全正解了。。。。
我猜想这个解释可以推广的
【在 p******m 的大作中提到】
: 我想解N个线性联立方程组， 但是必须至少找到一组非负解， 里边共有m个未知变量，
: m >> N。 这样的解一定存在吗？如果不存在如何尽量找到一个比较接近的解， 但是
: 解必须是非负的。望高手赐教。
|
