我正在考虑使用 cvxopt 来解决一些非线性网络流量优化问题。为了了解基础知识，我尝试使用一个非常简单的测试网络，只有 4 个顶点和 5 个边。
我的网络看起来像 this 。蓝色和红色节点分别是源节点和汇节点。
每条边的成本为:
alpha*x**2
其中 x 是包含每条边上的流的向量，alpha 是某个系数。那么我的优化问题是:
min sum(alpha*x**2)
subject to:
E*x = b
x >= 0
其中 E 是边弧关联矩阵，b 是包含源和汇的向量。因此，矩阵向量方程 Ex = b 应该只执行基尔霍夫定律(即每个节点处的流量守恒)。
我执行此操作的 python 脚本是:
from cvxopt import matrix, spdiag, solvers
#Four vertices, five edges
E = matrix(0.0, (4,5))
E[0,0] = 1.0
E[0,1] = 1.0
E[1,0] = -1.0
E[1,2] = 1.0
E[1,3] = 1.0
E[2,1] = -1.0
E[2,2] = -1.0
E[2,4] = 1.0
E[3,3] = -1.0
E[3,4] = -1.0
#Source-sink vector
b = matrix(0.0, (4,1))
b[0] = 0.5
b[3] = -0.5
#Coefficient in the quadtratic
alpha = 1.0
#Function to pass to cvxopt
def F(x=None, z=None):
if x is None:
return 0, matrix(0.05, (5,1))
if min(x) <= 0.0:
return None
f = sum(alpha*(x**2))
Df = (2.0*alpha*x).T
if z is None:
return f, Df
D2f = 2.0*alpha*matrix(1.0, (5,1))
H = spdiag(z[0]*D2f)
return f, Df, H
#Solve
x = solvers.cp(F, A=E, b=b)['x']
我得到的错误是:
pcost dcost gap pres dres
0: 0.0000e+00 1.2500e-02 1e+00 1e+00 2e-01
Traceback (most recent call last):
File "simple_network.py", line 45, in <module>
x = solvers.cp(F, A=E, b=b)['x']
File "/usr/local/lib/python2.7/dist-packages/cvxopt/cvxprog.py", line 1966, in cp
xdot_e, xaxpy_e, xscal_e, options = options)
File "/usr/local/lib/python2.7/dist-packages/cvxopt/cvxprog.py", line 782, in cpl
raise ValueError("Rank(A) < p or "\
ValueError: Rank(A) < p or Rank([H(x); A; Df(x); G]) < n
我不确定如何从这里继续。我认为这个优化问题可以用 cvxopt 解决，因为它很简单，可以手动找到最佳流程。如果有人能告诉我如何纠正此代码，或者告诉我为什么此类问题不适合此软件，我将不胜感激。
提前致谢。
最佳答案
再想了一下，发现这个问题是因为cvxopt要求等式约束中矩阵的秩不少于等式约束的个数而造成的。
在我的例子中，这意味着我的关联矩阵的秩必须等于网络中的节点数。然而，图论的一个结果是，任何具有 n 个节点的简单连通图都将具有一个秩为 n-1 的关联矩阵。这会产生排名错误。
解决这个问题的方法是选择一个节点，并向其添加两条额外的边:一条从该节点开始但无处通向，另一条从无处而来并终止于该节点。这实际上向矩阵添加了两列。然后，我向矩阵添加了一行，要求这两个新边上的流量之和为零。
通过这种方式，我增加了矩阵的秩，而不添加任何额外的节点。原始网络上的流量不受添加这些边的影响，因为我要求新边上的流量保持为零。
这是一种有点古怪的方法，但它似乎可以解决问题。
关于python - 为什么 CVXOPT 会给出这种非线性网络流优化的排名误差？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/43850745/