python - 为什么 CVXOPT 会给出这种非线性网络流优化的排名误差？

Question

我正在考虑使用 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 解决，因为它很简单，可以手动找到最佳流程。如果有人能告诉我如何纠正此代码，或者告诉我为什么此类问题不适合此软件，我将不胜感激。

提前致谢。

Answer 1

再想了一下，发现这个问题是因为cvxopt要求等式约束中矩阵的秩不少于等式约束的个数而造成的。

在我的例子中，这意味着我的关联矩阵的秩必须等于网络中的节点数。然而，图论的一个结果是，任何具有 n 个节点的简单连通图都将具有一个秩为 n-1 的关联矩阵。这会产生排名错误。

解决这个问题的方法是选择一个节点，并向其添加两条额外的边:一条从该节点开始但无处通向，另一条从无处而来并终止于该节点。这实际上向矩阵添加了两列。然后，我向矩阵添加了一行，要求这两个新边上的流量之和为零。

通过这种方式，我增加了矩阵的秩，而不添加任何额外的节点。原始网络上的流量不受添加这些边的影响，因为我要求新边上的流量保持为零。

这是一种有点古怪的方法，但它似乎可以解决问题。