我正在考虑使用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解决,因为手动找到最佳流量非常简单。如果有人告诉我如何纠正代码,或者告诉我为什么这种类型的问题不适合这种软件,我将不胜感激。
提前致谢。