为什么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

我不确定该如何继续下去。我以为这个优化问题可以用cvxopt解决，因为手动找到最佳流量非常简单。如果有人告诉我如何纠正代码，或者告诉我为什么这种类型的问题不适合这种软件，我将不胜感激。

提前致谢。

- Olly

Answer 1

今天遇到了同样的问题。

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

对矩阵E进行奇异值分解：

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 = c

to check if the problem is feasible. If the last element of c is not zero, then the problem is infeasible.

T x = c

另外，cvxpy使用QR分解执行类似操作

- user357269

Answer 2

经过再次思考，我意识到这个问题是由于cvxopt要求等式约束中矩阵的秩不小于等于等式约束的数量所引起的。

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

我解决这个问题的方法是选择一个节点，并向其添加两条额外的边：一条从节点开始但没有目的地，另一条从无处来到节点。这实际上添加了两列到矩阵中。然后我添加了一行额外的约束条件，要求这两条新边上的流量之和为零。

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

这是一种有点hacky的方法，但似乎能解决问题。

- Olly