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

Question

我正在考虑使用cvxopt来解决一些非线性网络流优化问题。为了理解基本原理，我用一个只有4个顶点和5条边的非常简单的测试网络进行了尝试。

我的网络看起来像这样。蓝色和红色节点分别是源节点和接收器。

每个边的成本为：

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

我不确定如何从这里开始。我假设这个html" target="_blank">优化问题可以用cvxopt来解决，因为手动找到最佳流是足够简单的。如果有人能告诉我如何纠正这个代码，或者告诉我为什么这种类型的问题不适合这个软件，我将不胜感激。

提前感谢。

Answer 1

今天遇到了同样的问题。

另一种解决方法是删除冗余约束。

取矩阵E的SVD：

E = U S V'

S具有与E相同的形状，最后一行将是全零（因为您的矩阵排名为3）。

让y=V'x并重新排列相等约束

E x = b
U S V' x = b
S V' x = U' b

U'b的最后一行必须为零，否则问题不可行。

设＜code＞T＜code＞为＜code＞S V‘

然后，您可以使用等式约束

T x = c

或者，cvxpy使用QR分解进行类似的操作

Answer 2

经过进一步的思考，我意识到这个问题是因为cvxopt要求等式约束中矩阵的秩不小于等式约束的个数。

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

我解决这个问题的方法是选择一个节点，并向其添加两条额外的边：一条从节点开始，但没有任何地方，另一条从任何地方开始，终止于节点。这实际上会在矩阵中添加两列。然后，我在矩阵中增加了一行，要求这两条新边上的流量之和为零。

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

这是一种有点老套的方法，但似乎很管用。